636. Exclusive Time of Functions
Asked at Anthropic, Visa
Difficulty
Medium
Time
O(m)
Space
O(n)
Pattern
Array
Companies
2
Problem
A single-threaded CPU runs a program with n functions, each with a unique id from 0 to n - 1. Calls form a stack: a starting call is pushed on top, and the function on top is the one currently running. When a call ends, it is popped and its parent resumes.
You are given logs, a list of strings in the form "{id}:{start|end}:{timestamp}". A start log means the call begins at the beginning of that timestamp; an end log means the call finishes at the end of that timestamp. So a call that starts and ends on the same timestamp still uses 1 unit of time. A function may be called many times, including recursively.
Return an array result of length n, where result[i] is the exclusive time of function i: the total time it ran on the CPU, not counting time spent inside functions it called. Time spent by a child call belongs only to the child.
Nested calls share one CPU
Constraints
- ●
1 <= n <= 100 - ●
2 <= logs.length <= 500 - ●
0 <= function_id < n - ●
0 <= timestamp <= 10^9 - ●
No two start events share the same timestamp - ●
No two end events share the same timestamp - ●
Every start log has a matching end log for the same function
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:start:6","0:end:6","0:end:7"][8]n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"][7,1]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Anthropic | Medium | View all Anthropic questions → |
| Visa | Medium | View all Visa questions → |
How to Think About It
Brute force: simulate the entire timeline tick by tick, marking which function is active at each tick. Time is O(total_time) which can be very large.
Use a stack to track currently executing functions. On a start log, push the function. On an end log, pop it. The time spent is end - start + 1.
When a child function starts, pause the parent. The child's execution time should not count toward the parent. Use the stack to manage this nesting.
Key insight: when processing a start log, if the stack is not empty, the previous function's time should be updated up to (start - 1). When processing an end log, update the current function's time and resume the parent at (end + 1).
Use a variable prevTime to track the last timestamp processed. On start: result[stack.top()] += start - prevTime. On end: result[stack.top()] += end - prevTime + 1, then prevTime = end + 1.
Example: logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]. Stack operations: push 0 at 0, push 1 at 2 (0 gets time 0-1=2), pop 1 at 5 (1 gets 5-2+1=4), pop 0 at 6 (0 gets 6-5+1=2). Result: [3,4].
Optimal Approach
Step 1: Parse each log into (id, type, timestamp). Use a stack to track active function IDs.
Step 2: Maintain a prevTime variable initialized to 0, and a result array.
Step 3: For a start log (id, "start", t): if the stack is not empty, add t - prevTime to result[stack.top()]. Push id onto the stack. Set prevTime = t.
Step 4: For an end log (id, "end", t): add t - prevTime + 1 to result[stack.top()]. Pop the stack. Set prevTime = t + 1.
Step 5: After processing all logs, return the result array.
Step 6: Example walkthrough with logs = ["0:start:0","1:start:2","1:end:5","0:start:6","0:end:7","0:end:8"]:
start 0 at t=0: stack=[], prevTime=0. result unchanged. stack=[0], prevTime=0.
start 1 at t=2: stack=[0], add 2-0=2 to result[0]. stack=[0,1], prevTime=2.
end 1 at t=5: stack=[0,1], add 5-2+1=4 to result[1]. stack=[0], prevTime=6.
start 0 at t=6: stack=[0], add 6-6=0 to result[0]. stack=[0], prevTime=6.
end 0 at t=7: stack=[0], add 7-6+1=2 to result[0]. stack=[], prevTime=8.
end 0 at t=8: stack=[], add 8-8+1=1 to result[0]. Result: [5,4].
Time: O(n) where n is the number of logs. Space: O(n) for the stack and result.
One pass with a stack and prevTime
What Trips People Up in Real Interviews
Confusing exclusive time with inclusive time. Exclusive time means a function only counts time when it is directly on the CPU, not when waiting for children.
Forgetting to handle the timestamp correctly. If function A starts at 0 and child B starts at 2, A gets 2 units (ticks 0 and 1), not 3.
Off-by-one errors on end timestamps. The end log means the function finishes at that timestamp, so it should count that tick.
Not updating the parent function's time when a child starts. The parent should be credited for time before the child kicked in.
Trying to solve with a single pass without a stack. The stack is essential for tracking the nesting of function calls.
Solution Code
O(m) timeclass Solution:
def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:
result = [0] * n
stack = []
prev_time = 0
for log in logs:
parts = log.split(':')
fid = int(parts[0])
typ = parts[1]
ts = int(parts[2])
if typ == 'start':
if stack:
result[stack[-1]] += ts - prev_time
stack.append(fid)
prev_time = ts
else:
result[stack[-1]] += ts - prev_time + 1
stack.pop()
prev_time = ts + 1
return resultFrequently Asked Questions
What is the Exclusive Time of Functions problem?
Given logs of function calls with start and end timestamps, compute the exclusive time each function spent on the CPU, excluding time spent in child calls.
How do you solve Exclusive Time of Functions?
The optimal approach runs in O(m) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Exclusive Time of Functions?
Exclusive Time of Functions is asked at Anthropic, Visa. It is a medium difficulty problem.
What are common mistakes on Exclusive Time of Functions?
- Confusing exclusive time with inclusive time. Exclusive time means a function only counts time when it is directly on the CPU, not when waiting for children.
- Forgetting to handle the timestamp correctly. If function A starts at 0 and child B starts at 2, A gets 2 units (ticks 0 and 1), not 3.
- Off-by-one errors on end timestamps. The end log means the function finishes at that timestamp, so it should count that tick.
- Not updating the parent function's time when a child starts. The parent should be credited for time before the child kicked in.
- Trying to solve with a single pass without a stack. The stack is essential for tracking the nesting of function calls.