Exclusive Time of Functions
Asked at Anthropic
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anthropic | Medium | View all Anthropic 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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Exclusive Time of Functions?
Exclusive Time of Functions is asked at Anthropic. 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.