Convert Sampled Call Stacks into Start and End Events

Convert a sequence of sampled call stacks into inferred function start and end events. Compare adjacent stacks by their common prefix, ending frames that disappeared and starting frames that appeared.

Implement stack_samples_to_events(times: int[], stacks: string[][]) -> string[][]. Each output is [time,event,functionName], with time as a decimal string and event START or END.

Constraints & Assumptions

• Times are strictly increasing nonnegative integers at most 1000000000, one per stack. At most 100000 samples and 1000000 total frames.
• Each stack is ordered outermost to innermost. Names are nonempty ASCII identifiers. Recursive calls may repeat the same name at different depths; these are separate frames.
• Treat the stack before the first sample as empty. At sample time t, emit END events for the previous stack's non-common suffix from innermost to outermost, then START events for the current non-common suffix from outermost to innermost.
• Frames in the common prefix continue. Empty samples are valid. Do not deduplicate repeated function names within a stack.
• Do not invent an end time after the final sample. Frames still present remain open in the returned trace. Empty input returns an empty list.
• This is an inferred transition trace at sample times, not a reconstruction of every actual function call between samples.

Example

times = [10,20,30]
stacks = [["main","f"],["main","f","f"],["main","g"]]
result = [["10","START","main"],["10","START","f"],
 ["20","START","f"],["30","END","f"],["30","END","f"],
 ["30","START","g"]]

Explain recursion, event ordering, and the common-prefix comparison. For the reported last-N-samples follow-up, discuss which prior stack/state a streaming converter needs, what can still be emitted prospectively, and why an arbitrary retained suffix cannot recover transitions or true start times before its first retained sample.