DSA problem
Exclusive Time of Functions
On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n - 1. Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with its ID, whether it started or ended, and the timestamp.
You are given a list logs, where logs[i] represents the i-th log message formatted as a string "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means a function call with function ID 0 started at the beginning of timestamp 3, and "1:end:2" means a function call with function ID 1 ended at the end of timestamp 2. Note that a function can be called multiple times, possibly recursively.
A function's exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice — once running for 2 units of time and once running for 1 unit — then the exclusive time is 2 + 1 = 3. Return the exclusive time of each function in an array, where the value at the i-th index represents the exclusive time for the function with ID i.
The natural data structure is the call stack itself: push function IDs on start, pop on end. To compute exclusive time correctly, we also track the time at which the currently running function (the top of the stack) "resumed" execution. Whenever a function starts (entering a deeper call), the currently running function pauses, so we credit it with now - resumeTime and reset resumeTime to now. Whenever a function ends, we credit it now - resumeTime + 1 (end is inclusive of the entire now timestamp) and then resume the function beneath it at now + 1. This is O(n) time and O(n) space where n is the number of logs.
Examples
n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"][3,4]n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:end:6"][8]n = 2, logs = ["0:start:0","0:end:0","1:start:1","1:end:1"][1,1]Constraints
- 1 <= n <= 100
- 1 <= logs.length <= 500
- 0 <= function_id < n
- 0 <= timestamp <= 10^9
- No two start events will happen at the same timestamp.
- No two end events will happen at the same timestamp.
- Each function has an "end" log for each "start" log.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.