Compute exclusive times and call stack from logs
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's ability to process single-threaded execution logs and compute per-function exclusive durations while reconstructing the call stack at a given timestamp, testing stack simulation, interval reasoning, timestamp tie-handling, parsing of time-stamped events, and algorithmic complexity analysis.
Constraints
- 0 <= m <= 10^5
- 0 <= len(logs) <= 2 * 10^5
- Each log entry is a valid string "t,event,id" with event in {BEGIN, END} and 0 <= id < m
- The log sequence is well-formed, properly nested, and sorted by timestamp; for equal timestamps, END entries appear before BEGIN entries
- q can be any integer, including values outside all execution intervals
- Use half-open intervals [start, end) when computing both durations and the active stack
Examples
Input: (2, ['0,BEGIN,0', '2,BEGIN,1', '5,END,1', '6,END,0'], 3)
Expected Output: ([3, 3], [0, 1])
Explanation: Function 0 runs exclusively during [0,2) and [5,6), for 3 total. Function 1 runs during [2,5), for 3 total. At time 3, the active stack is [0, 1].
Input: (2, ['0,BEGIN,0', '4,END,0', '4,BEGIN,1', '6,END,1'], 4)
Expected Output: ([4, 2], [1])
Explanation: Function 0 is active on [0,4), so it is not active at time 4. Function 1 begins at time 4 and is active on [4,6). The tie at timestamp 4 is handled by processing END before BEGIN.
Input: (1, ['0,BEGIN,0', '1,BEGIN,0', '3,END,0', '5,END,0'], 2)
Expected Output: ([5], [0, 0])
Explanation: This is a recursive call. The outer call contributes 1 ms from [0,1) and 2 ms from [3,5). The inner call contributes 2 ms from [1,3). Total exclusive time for function 0 is 5, and both frames are active at time 2.
Input: (3, [], 10)
Expected Output: ([0, 0, 0], [])
Explanation: There are no log entries, so all exclusive times are 0 and no function is active at any query time.
Input: (2, ['5,BEGIN,0', '7,END,0'], 4)
Expected Output: ([2, 0], [])
Explanation: Function 0 runs on [5,7), so it contributes 2 ms. The query time 4 is before any function begins, so the active stack is empty.
Solution
def solution(m, logs, q):
durations = [0] * m
def parse(entry):
t_str, event, id_str = entry.split(',')
return int(t_str), event, int(id_str)
# Pass 1: compute exclusive durations.
stack = []
prev_time = None
for entry in logs:
t, event, fid = parse(entry)
if prev_time is None:
prev_time = t
if stack:
durations[stack[-1]] += t - prev_time
if event == 'BEGIN':
stack.append(fid)
else:
stack.pop()
prev_time = t
# Pass 2: reconstruct the active stack at time q.
stack = []
i = 0
n = len(logs)
while i < n:
t, _, _ = parse(logs[i])
# If q is before this timestamp, the current stack is active at q.
if q < t:
return durations, stack[:]
# Process all events that happen at timestamp t.
while i < n:
curr_t, event, fid = parse(logs[i])
if curr_t != t:
break
if event == 'BEGIN':
stack.append(fid)
else:
stack.pop()
i += 1
# With half-open intervals [start, end), the stack after processing
# all events at time t is exactly the stack active at time t.
if q == t:
return durations, stack[:]
return durations, stack[:]Time complexity: O(n), where n = len(logs). Space complexity: O(m + d), where d is the maximum call depth.
Hints
- Use a stack to represent the active calls. Between two consecutive event timestamps, only the function on top of the stack can accumulate exclusive time.
- For the query timestamp q, think about what the stack should look like after processing all events with timestamp <= q. With half-open intervals, END at time t removes a function before checking activity at t, while BEGIN at time t adds a function that is active at t.