Exclusive Time of Functions
Medium · Stack & Strings · Array · Stack
Problem
A single-threaded CPU runs a program of n functions with ids 0 to n - 1. Calls are tracked with a stack: when a function starts, its id is pushed, and when it ends, its id is popped. The function on top of the stack is the one running. A function may call others, including itself recursively.
You are given logs, where each entry has the form "{id}:{start|end}:{timestamp}". "3:start:4" means function 3 started at the beginning of time unit 4, and "3:end:6" means it finished at the end of time unit 6.
A function’s exclusive time is the total time it spends running, not counting time spent in the functions it calls. If a function is called several times, add up all of its calls. Return an array whose i-th entry is the exclusive time of function i.
Examples
Input: n = 2, logs = ["0:start:0","1:start:3","1:end:5","0:end:7"] Output: [5,3]
Function 1 runs during units 3-5, and function 0 runs during units 0-2 and 6-7.
Input: n = 1, logs = ["0:start:0","0:start:1","0:end:2","0:end:4"] Output: [5]
Both calls belong to function 0, which occupies all five units 0 through 4.
Constraints
- 1 <= n <= 100
- 1 <= len(logs) <= 500
- 0 <= function id < n
- 0 <= timestamp <= 10^9
- no two start events share a timestamp, and no two end events share a timestamp
- every start has a matching end, and the log is a valid single-threaded run
Approaches
- Each call’s span minus its direct children — time O(L²), space O(L)
Follow-up
What if you also wanted each function’s inclusive time (callees included)? Push the start time with the id; on an end, the call’s span is t - start + 1. And with several threads, keep one stack per thread id and charge each thread’s time separately.
Related problems
Start free on Cariara · Coding problems · System design studio
