Compute Exclusive Time from Stack Events
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Compute Exclusive Time from Stack Events
Given entry and exit events from one thread, compute the total exclusive running time of each function. The interview report preserves only the topic "Stack Trace" and notes that it had follow-ups; the event encoding and time semantics below are explicit practice assumptions, not a reconstruction of those missing follow-ups.
```python
def exclusive_function_times(
events: list[list[object]],
) -> list[list[object]]:
...
```
Each event is exactly `[function_name, kind, timestamp]`:
- `function_name` is a nonempty string;
- `kind` is exactly `"start"` or `"end"`; and
- `timestamp` is a nonnegative integer.
Events are listed in nondecreasing timestamp order. A start event pushes a function onto the active call stack. An end event must name the currently active top function and pops it. Recursion is allowed.
Treat time as continuous and intervals as half-open. If function A starts at time 2, calls B at time 5, B ends at time 8, and A ends at time 10, then B receives `8 - 5 = 3` units and A receives `(5 - 2) + (10 - 8) = 5` units. Events sharing a timestamp consume no time between them and are applied in list order.
Return one `[function_name, exclusive_time]` record per distinct function name, sorted by function name lexicographically. An empty input returns `[]`.
## Example
```text
Input:
events = [
["main", "start", 0],
["work", "start", 2],
["work", "end", 7],
["main", "end", 10]
]
Output: [["main", 5], ["work", 5]]
```
## Constraints and Errors
- `0 <= len(events) <= 500_000`
- `0 <= timestamp <= 10**18`
- Timestamps must be nondecreasing.
- The trace must begin from an empty stack and end with an empty stack.
- An end event with an empty stack or a name different from the active function is invalid.
- A malformed event, invalid field type, empty name, invalid kind, Boolean timestamp, decreasing timestamp, or unbalanced trace raises `ValueError`.
- Do not mutate the input.
## Hints
- Maintain the active function stack and the timestamp of the previous event.
- Before applying each event, charge elapsed time to the function currently at the top, if any.
- Aggregate by function name even when the same function is called recursively or from several callers.
Overview: Compute aggregate exclusive execution time for each function from nested start and end events, including recursive calls. Use a stack over a validated single-threaded trace, apply half-open time intervals, and return deterministic sorted results.
Read the full Anthropic Software Engineer interview experience this question came from
Aggregate exclusive continuous execution time by function name from one well-nested thread trace. Charge each half-open interval between consecutive events to the currently active top frame, support recursion and equal timestamps, and return lexicographically sorted records.
Constraints
- Events are nondecreasing by nonnegative integer timestamp.
- Each end must match the active top function.
- The trace starts and ends with an empty stack.
- Recursion is allowed.
- Malformed or unbalanced traces raise ValueError.
Examples
Input: ([['main','start',0],['work','start',2],['work','end',7],['main','end',10]],)
Expected Output: [['main', 5], ['work', 5]]
Explanation: The supplied nested-call example.
Input: ([],)
Expected Output: []
Explanation: An empty trace has no functions.
Hints
- Before applying each event, charge elapsed time to the current top frame.
- Use a stack for nesting and a dictionary for totals.