Convert stack samples to trace events
Quick Overview
This question evaluates a candidate's ability to convert chronologically ordered stack samples into start/end trace events, testing stateful stream processing, stack diffing, correct temporal ordering, and frame identity handling in the presence of recursion.
Question
Implement convertToTrace(samples) that, given a chronologically ordered vector of stack samples (each sample contains a timestamp and a call-stack of function names), outputs a list of start/end Event records so that:
A start event is emitted the first time a function appears deeper in the stack than in the previous sample.
An end event is emitted when a function disappears from the stack; for multiple disappearances at the same timestamp, emit inner functions’ end events before outer ones.
Assume calls still on the stack in the last sample have not yet ended.
Correctly handle identical successive stacks and recursive frames (the same function re-appearing deeper must be treated as distinct frames). Follow-up: Modify the solution so an event is emitted for a function only if that frame appears in at least N consecutive identical positions in consecutive samples (configurable N). Decide whether to use the 1st or Nth sample’s timestamp as the start time, and retain the same definition of a single call, including proper handling of recursion.