When multiple tasks are executed on a single-threaded CPU, the tasks are scheduled based on the principle of pre-emption. When a higher-priority task arrives in the execution queue, then the lower-priority task is pre-empted, i.e. its execution is paused until the higher-priority task is complete. There are n functions to be executed with each function on a single-having a unique ID between 0 and n - 1. Given an integer n, representing the number of functions to be executed, and an execution log as an array of strings, logs, of size m, determine the exclusive times of each of the functions. Exclusive time is the sum of execution times for all calls to a
function. Any string representing an execution log is of the form {function_id}{"start" "end"):(timestamp), indicating that the function with ID function_id, either starts or ends at a time identified by the timestamp value. 4 = Note: While calculating the execution time of a function call, both the starting and ending times of the function call have to be included. The log of the form

Question

When multiple tasks are executed on a single-threaded CPU, the tasks are scheduled based on the principle of pre-emption. When a higher-priority task arrives in the execution queue, then the lower-priority task is pre-empted, i.e. its execution is paused until the higher-priority task is complete. There are n functions to be executed with each function on a single-having a unique ID between 0 and n - 1. Given an integer n, representing the number of functions to be executed, and an execution log as an array of strings, logs, of size m, determine the exclusive times of each of the functions. Exclusive time is the sum of execution times for all calls to a
function. Any string representing an execution log is of the form {function_id}{"start" "end"):(timestamp), indicating that the function with ID function_id, either starts or ends at a time identified by the timestamp value. 4 = Note: While calculating the execution time of a function call, both the starting and ending times of the function call have to be included. The log of the form

Accepted Answer

```python # define a function to calculate exclusive times of functions def exclusive_times(n, logs): # Initialize a stack to keep track of function calls stack = [] # Initialize a list to store exclusive time of each function exclusive_time = [0] * n # Process each log entry for log in logs: # Split the log into function_id, action, and timestamp function_id, action, timestamp = log.split(':') function_id, timestamp = int(function_id), int(timestamp) # If the action is "start", push the function_id and timestamp onto the stack if action == "start": stack.append((function_id, timestamp)) else: # The action is "end" # Pop the last function from the stack and calculate the time it took prev_function_id, start_time = stack.pop() time_taken = timestamp - start_time + 1 # Add the time taken to the exclusive time of the function exclusive_time[prev_function_id] += time_taken # If the stack is not empty, subtract the time taken from the function on top of the stack if stack: exclusive_time[stack[-1][0]] -= time_taken # Return the exclusive times of each function return exclusive_time ``` ```python # main function that tests exclusive_times function def main(): # test the exclusive_times function # use case 1 assert exclusive_times(2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) == [3, 4] # use case 2 assert exclusive_times(1, ["0:start:0", "0:end:0"]) == [1] # Call the main function to execute the tests main() ``` ∻Explanation∻ ⚹The code defines a function `exclusive_times` that calculates the exclusive times of functions based on the logs provided. It uses a stack to keep track of the active function calls and an array to store the exclusive times. The main function `main` tests the `exclusive_times` function with two use cases to ensure it works correctly.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the main function `exclusive_times` to calculate the exclusive times of functions. ‖ ‖ ▪ ⋮ Use a stack to keep track of the active function calls and their start times. ‖ ‖ ▪ ⋮ Use an array `exclusive_time` to store the exclusive time for each function. ‖ ‖ ▪ ⋮ Iterate over each log entry, parse it, and update the stack and `exclusive_time` accordingly. ‖ ‖ ▪ ⋮ Define concrete use cases and testing cases for the function: when user calls `exclusive_times(n, logs)`, it should return the correct exclusive times. ‖ ∻Time Complexity∻ ⚹The time complexity is O(m), where m is the size of the logs array, because we iterate through each log entry once.⚹ ∻Space Complexity∻ ⚹The space complexity is O(n), where n is the number of functions, due to the stack and the exclusive_time array.⚹

Sia