Convert Streaming Call-Stack Samples into Function Events

## Problem A profiler periodically samples one thread's call stack. Each stack lists frames from outermost to innermost. Convert the samples into timestamped function start and end events. For two adjacent samples, their longest common prefix represents frames that remained active. At the newer sample's timestamp: 1. Emit `end` events for frames in the old suffix, from innermost to outermost. 2. Emit `start` events for frames in the new suffix, from outermost to innermost. Frames are identified by both function name and depth, so recursive occurrences with the same name remain distinct. The first sample starts all of its frames at its timestamp. After the last sample, close every remaining frame at `endTimestamp`, innermost first. ### Portable Function Contract Implement `stackSamplesToEvents(samples, endTimestampText)`. `samples` is a list of string rows. Each row has the form: ```text [timestampText, outermostFunction, ..., innermostFunction] ``` The first field is the sample timestamp. Any later fields are the sampled stack frames in outermost-to-innermost order. A row containing only `timestampText` represents an empty stack. `timestampText` and `endTimestampText` are canonical signed decimal integers: `"0"`, a nonzero digit followed by digits, or `"-"` followed by a nonzero digit and then zero or more digits. Their parsed values are in the JavaScript-safe interval `[-(2^53 - 1), 2^53 - 1]`. Sample timestamps are strictly increasing, and `endTimestampText` is at least the final sample timestamp. Function names are arbitrary nonempty strings and equality is exact. Return a list of string rows. Each event row has exactly four fields: ```text [eventType, timestampText, functionName, depthText] ``` - `eventType` is exactly `"start"` or `"end"`. - `timestampText` is the canonical input timestamp string at which that event is emitted. - `functionName` is the exact frame name. - `depthText` is the canonical nonnegative decimal depth, with outermost depth `"0"`. The string-only row encoding is part of the portable console interface. ### Constraints & Assumptions - `0 <= len(samples) <= 200,000`. - Sample timestamps are strictly increasing integers in the JavaScript-safe interval, encoded in canonical string form. - `endTimestampText` is canonical and at least the last sample timestamp; for empty input it is ignored. - A stack contains at most `10,000` frames and the total number of sampled frames is at most `500,000`. - Function names are arbitrary nonempty strings and equality is exact, with no case folding or normalization. - Sampling reveals only transitions between observations; emitted times are observation times, not claims about the exact instant a call occurred. ### Clarifying Questions to Ask - Are stacks outermost-first or innermost-first? Outermost-first. - At one timestamp, do ends precede starts? Yes. - In what order are multiple ends and starts emitted? Ends inner-to-outer, then starts outer-to-inner. - How is recursion represented? Equal names at different depths are separate frames; prefix comparison remains positional. - Why are timestamps and depths returned as strings? Uniform string rows preserve the exact timestamp text and map directly to all four console languages. ```hint Compare only until the first difference The longest common prefix length partitions both stacks into unchanged frames and transition suffixes. ``` ```hint The transformation can be streamed Only the previous stack and the output sink are needed; all earlier samples can be discarded after their transition is emitted. ``` ### Example ```text samples = [ ["10", "main", "a", "b"], ["15", "main", "a", "c"], ["20", "main"] ] endTimestampText = "25" ``` Return: ```text [ ["start", "10", "main", "0"], ["start", "10", "a", "1"], ["start", "10", "b", "2"], ["end", "15", "b", "2"], ["start", "15", "c", "2"], ["end", "20", "c", "2"], ["end", "20", "a", "1"], ["end", "25", "main", "0"] ] ``` ### Evaluation Focus - Parses and compares exact JavaScript-safe timestamp strings without coercive or lossy conversion. - Computes transitions from the positional longest common prefix. - Emits uniform string events in the required nesting-safe order. - Handles recursion, empty stacks, identical adjacent samples, and final closure. - Processes a stream using memory proportional to one stack, apart from returned events. ### Extensions to Discuss 1. If a new frame must appear in `n` consecutive samples before being confirmed, what candidate state and buffered timestamp are needed? 2. How would temporary missing samples affect confidence and event timing? 3. How could events be emitted incrementally without storing the full result?