Convert Sampled Call Stacks into Timestamped Function Start and End Events

A sampling profiler periodically records the call stack of a running program. Each sample is a pair `(timestamp, stack)`, where `stack` is the list of function names currently on the call stack, ordered from the outermost frame (for example `main`) to the innermost frame, the function executing at that moment. Samples arrive in increasing timestamp order. A trace viewer does not want samples. It wants **events**: a `start` event when a function call begins and an `end` event when it returns, each with a timestamp. Since the profiler only sees snapshots, use this rule: a call is considered to start at the timestamp of the first sample in which it appears, and to end at the timestamp of the first later sample in which it is no longer on the stack. A frame counts as the same call across consecutive samples only if it is at the same depth and every frame beneath it (its callers) is also unchanged. For example, these samples: ```text t=0 [main] t=1 [main, foo] t=2 [main, foo, bar] t=3 [main, baz] t=4 [main] ``` produce `start main @0`, `start foo @1`, `start bar @2`, then at `t=3` the events `end bar`, `end foo`, `start baz`, and at `t=4` the event `end baz`. ### Clarifying Questions - What should happen to calls that are still on the stack after the last sample: close them at the last timestamp, or leave them open? - Is recursion possible, so that the same function name appears more than once in a stack? - Can two consecutive samples share a timestamp, and what should the events look like if they do? - What exact output format does the trace viewer expect for each event? - Are frames identified only by function name, or also by something that distinguishes separate calls of the same function? ### Part 1 — Convert a list of samples into events Implement a function that takes the full list of samples and returns the list of events in the order a trace viewer should receive them. Handle recursion and empty stacks correctly. ```hint Compare neighbors, not the whole history Each new sample only needs to be compared with the one immediately before it; think about what part of the two stacks tells you nothing changed. ``` #### What This Part Should Cover - A correct way to find which frames ended and which began between two consecutive samples - Correct handling of recursion (repeated names) and of empty stacks - A stated policy for calls still open after the last sample - Time and space complexity in terms of the number of samples and the stack depth ### Part 2 — Justify the diff and the event order Explain why comparing consecutive stacks in the way you chose gives the right set of starts and ends. Then explain why, when several calls end at the same timestamp, their `end` events must be emitted from the innermost frame outward, while several `start` events at the same timestamp must be emitted from the outermost frame inward, and what goes wrong in a trace viewer if either order is reversed. ```hint Think about what the viewer reconstructs A viewer rebuilds nested spans from the event stream; consider what nesting it would infer if a caller's end arrived before its callee's end. ``` #### What This Part Should Cover - Why frames below the first difference are unchanged and every frame above it changed - The nesting (stack discipline) invariant that the event order must preserve - Concrete failure cases when the order is wrong - What sampling cannot observe, such as a function returning and being called again between two samples ### Part 3 — Streaming input The samples now arrive as an unbounded stream, and the full list cannot be stored. Redesign the converter so that it emits events incrementally as each sample arrives, and state how much memory it needs. ```hint Minimal state Ask what the conversion of the next sample actually depends on, then keep only that. ``` #### What This Part Should Cover - An incremental API (for example, add a sample, and close the stream) that emits events as soon as they are known - Memory bounded by stack depth rather than by stream length - Behavior at end of stream and on malformed input, such as timestamps going backward - Latency: how soon after a call actually ends its end event is emitted ### What a Strong Answer Covers - Clean, correct code that produces exactly the events in the example - A crisp explanation connecting the diff, the event order and the nesting invariant - Honest limits of sampling-based reconstruction - A streaming design whose memory does not grow with the number of samples ### Follow-up Questions - Samples come from many threads, each with its own stack, interleaved in one stream. What changes? - How would you merge very short calls, or drop calls seen in only one sample, to reduce noise? - If each frame also carried a unique call identifier, how would the algorithm and its guarantees change? - How would you compute total and self time per function from the event stream?