Convert stack samples to execution trace
Company: Anthropic
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given sampling-profiler output: a list of Sample objects ordered by timestamp ascending. Each Sample has (t: float, stack: list[str]) where stack[0] is the outermost currently executing function and stack[-1] is the innermost. An arbitrary number of calls/returns may occur between samples. Convert this into a trace of start/end events suitable for visualization. Define precise rules to infer events between consecutive samples using the longest common prefix of stacks: emit end events for frames present in the earlier stack but not in the later one (from deepest up to the divergence point), then emit start events for frames present in the later stack but not in the earlier one (from the divergence point down to deepest). Also handle the initial sample (emit starts for its whole stack) and the finalization at the end of the last sample if required. Implement a function samples_to_trace(samples) -> list[tuple[float, str, str]] that returns events as (timestamp, 's'|'e', function_name) in the correct temporal and nesting order. Discuss how you would:
1) treat duplicate function names appearing at different depths,
2) compress consecutive identical samples,
3) handle empty stacks, invalid inputs, or equal timestamps, and
4) optionally add a synthetic root to simplify logic. Provide time and space complexity and justify correctness. Example to ground the rules: for samples [Sample(0.0, ['a','b','a','c']), Sample(1.0, ['a','a','b','c'])], the emitted sequence should reflect at t=0.0: start a, start b, start a, start c; at t=1.0: end c, end a, end b; then start a, start b, start c (or an equivalent ordering consistent with your rules).
Quick Answer: This question evaluates understanding of sampled stack traces, event reconstruction, handling ambiguous or incomplete profiling data, and algorithmic reasoning about correctness and time/space complexity.
Convert sampling-profiler stack snapshots into a flat, properly nested trace of function **start** and **end** events suitable for a flame-graph–style visualization.
## What to implement
Implement `solution(samples)` (equivalent to `samples_to_trace(samples)`).
- **Input** — `samples` is a list (or tuple) of snapshots ordered by timestamp ascending. Each snapshot is a 2-item pair `(t, stack)`:
- `t` is a numeric timestamp (`int` or `float`).
- `stack` is a list of function names (strings). `stack[0]` is the **outermost** active function and `stack[-1]` is the **innermost**.
- **Output** — a list of events. Each event is a tuple `(timestamp, kind, function_name)` where:
- `timestamp` is the event's time as a **float** (each input `t` is coerced to `float` in the output, so an integer input timestamp appears as a float).
- `kind` is `'s'` (the function starts) or `'e'` (the function ends).
## Rules
Process the samples in input order and emit events using **exactly** these rules:
1. **First sample.** Emit a start event (`'s'`) for every frame in its stack, from **outermost to innermost**, all at that sample's timestamp.
2. **Each transition.** For each consecutive pair of samples `(prev_t, prev_stack)` → `(curr_t, curr_stack)`:
- Compute the **longest common prefix** length `k`: scan the two stacks position by position and stop at the first index where the frames differ (or where one stack runs out). Frames are matched **only by position**.
- Emit end events (`'e'`) at `curr_t` for the frames in `prev_stack[k:]`, ordered **deepest frame first**, up to the divergence point.
- Then emit start events (`'s'`) at `curr_t` for the frames in `curr_stack[k:]`, ordered from the **divergence point down to the deepest frame**.
3. **End of capture.** The capture is assumed to end at the last sample's timestamp. After all transitions, close every frame still open in the **last** stack by emitting end events, **deepest first**, all at the last sample's timestamp.
## Important details
- **Duplicate names are distinct frames.** The same function name at different depths is a different frame; match frames only by position when computing the longest common prefix.
- **Empty stacks are allowed** and mean no function is active at that sample.
- **Identical consecutive stacks produce no events.** When two adjacent stacks are equal, `k` equals their length, so both the end and start loops are empty (an implicit compression step).
- **Equal timestamps are allowed** and must be processed in the given input order.
- **Empty input** (`samples` is empty) returns an empty list.
## Validation
Raise `ValueError` for malformed input, specifically when:
- `samples` is not a list or tuple.
- A sample is not a 2-item sequence `(timestamp, stack)`.
- A timestamp is not a number (note: `bool` is **not** accepted as a number).
- A stack is not a `list`.
- Any frame name is not a string.
- Timestamps decrease (each timestamp must be **≥** the previous one; equal timestamps are fine).
## Why this works
The longest common prefix is exactly the portion of the call stack still active across both samples. Everything below that prefix in the earlier sample must have ended, and everything below that prefix in the later sample must have started. Emitting ends bottom-up and starts top-down keeps every frame properly nested.
> You may imagine a synthetic root frame that is always present, but do **not** emit any events for it.
## Constraints
- `0 <= len(samples) <= 200000`
- `0 <= len(stack_i) <= 100000`, and the sum of all stack lengths is at most `400000`
- Timestamps must be non-decreasing; equal timestamps are allowed
- Each stack element must be a string; malformed input must raise `ValueError`
Constraints
- 0 <= len(samples) <= 200000
- 0 <= len(stack_i) <= 100000, and the sum of all stack lengths is at most 400000
- Timestamps must be non-decreasing; equal timestamps are allowed
- Each stack element must be a string; malformed input should raise ValueError
Examples
Input: [(0.0, ['a', 'b', 'a', 'c']), (1.0, ['a', 'a', 'b', 'c'])]
Expected Output: [(0.0, 's', 'a'), (0.0, 's', 'b'), (0.0, 's', 'a'), (0.0, 's', 'c'), (1.0, 'e', 'c'), (1.0, 'e', 'a'), (1.0, 'e', 'b'), (1.0, 's', 'a'), (1.0, 's', 'b'), (1.0, 's', 'c'), (1.0, 'e', 'c'), (1.0, 'e', 'b'), (1.0, 'e', 'a'), (1.0, 'e', 'a')]
Explanation: The common prefix is only the first 'a'. So at t=1.0, end c, a, b; then start a, b, c. After the last sample, close the remaining stack c, b, a, a at t=1.0.
Input: []
Expected Output: []
Explanation: No samples means no events.
Hints
- For two adjacent samples, the frames before the first differing depth are the only ones guaranteed to still be running.
- Emit ends before starts at each transition, and treat duplicate function names as different frames if they occur at different depths.