Solution: Exclusive Execution Time of Functions
Let's solve the Exclusive Execution Time of Functions problem using the Stacks pattern.
We'll cover the following
Statement
We are given an integer number, n
, representing the number of functions running in a single-threaded CPU, and an execution log, which is essentially a list of strings. Each string has the format {function id}:{"start" | "end"}:{timestamp}
, indicating that the function with function id
either started or stopped execution at the time identified by the timestamp
value. Each function has a unique ID between and . Compute the exclusive time of the functions in the program.
Note: The exclusive time is the sum of the execution times for all the calls to a specific function.
Constraints:
-
n
-
logs.length
-
function id
n
-
timestamp
- No two start events and two end events will happen at the same
timestamp
. - Each function has an
end
log entry for eachstart
log entry.
Solution
To find out the exclusive execution time of functions, we will use a stack. Just as a single-threaded CPU uses a stack to manage function execution, preemption, and resumption, we can use a stack to perform our calculation. Every time we see a new start event, we’ll push the information regarding the previously running function onto the stack. When we see an end event, we’ll pop the currently running function from the stack. That way, all end events will be matched with the corresponding start event, and the execution time is correctly computed.
The stack will contain the starting time of all functions in the program. Here’s how the algorithm would work:
- First, we’ll read a line of text from the log and tokenize it to separate the function ID, the event type, and the timestamp.
- If the event type is “start”, push the current log details to the stack.
- Otherwise, we pop the log details from the stack and add the execution time of the current function in the actual exclusive time.
- If the stack is not empty, the current function is a nested function call. Therefore, we subtract the execution time of this called function from the calling function. We decrease the time in the calling function, in advance.
- We store the execution time of each function at the index equal to the function ID in the
result
array. - When the same function is called recursively, we add the function’s execution time to the current value at the specific index.
The following slides show how this solution works:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.