[ OK ]e1b18a69-2327-4609-aef2-491a3c92522a — full content available
[ INFO ]category: Coding difficulty: medium freq: Must first seen: 2026-01-31
[MEDIUM][CODING][MUST]High Frequency
$catproblem.md
The "Converting Stack Samples to Trace Events" problem is a common technical interview question at Anthropic that requires you to reconstruct a execution timeline from periodic snapshots of a call stack. It tests your ability to handle stateful stream processing and precise temporal logic. YouTube +2 051
Problem Statement
Implement a function, typically named convertToTrace(samples), that takes a chronologically ordered list of stack samples and outputs a sequence of start and end events. PracHub +1 21
Input: A list of samples, where each sample contains a timestamp (integer/float) and a stack (list of function names from root to leaf).
Output: A list of event records. Each record should include the timestamp, the event type (start or end), and the function name. YouTube +2
Core Logic & Rules
The conversion is driven by finding the Longest Common Prefix (LCP) between the current sample and the previous one: PracHub +1 367
Divergence Point: Compare the current stack to the previous stack. The index where they first differ (or where one ends) is the divergence point.
End Events: For every function in the previous stack that is not in the current stack's common prefix, emit an end event. These must be emitted from the innermost (deepest) to outermost.
Start Events: For every new function in the current stack starting from the divergence point, emit a start event. These must be emitted from outermost to innermost.
Initial State: The first sample is compared against an empty stack.
Final State: Usually, functions remaining on the stack after the last sample do not produce end events unless specifically requested. YouTube +5
Key Technical Challenges
Recursion: You cannot track frames by function name alone, as the same name may appear at multiple depths. You must track them by their position (index) in the stack.
Stability Follow-up: A common follow-up asks you to only emit events if a frame appears in at least Ncap N𝑁 consecutive samples to filter out "jitter" or very short-lived calls.
Temporal Precision: You must decide whether to use the timestamp of the first sample where a function appeared or the Nthcap N raised to the t h power𝑁𝑡ℎ sample (for stability) as the official start time. Reddit +3
Example Visual Logic
If the previous stack was [A, B, C] and the current stack is [A, D]:
End C at current timestamp.
End B at current timestamp.
Start D at current timestamp.(Note: A remains on the stack and triggers no event). PracHub +1
Would you like to see a Python implementation of this logic with the recursion and stability edge cases handled?