Generate Function Profiling Events from Stack Samples

You receive timestamped call-stack samples in increasing timestamp order. Each sample is (timestamp, stack), where stack lists function names from the outermost call to the currently executing function.

Implement profiling_events(samples, n) and return events (timestamp, type, function) where type is START or END.

For n = 1, compare each accepted stack with the previous accepted stack: end functions removed from the suffix, deepest first, then start functions added to the suffix, outermost first. A function still in the common prefix emits no event.

For n > 1, debounce each frame independently rather than waiting for an identical complete stack. Identify a frame by its depth and function name under normal stack-prefix semantics. A candidate frame becomes active after it appears at the same depth, with the same ancestor prefix, in at least n consecutive samples; emit its START at the first timestamp in that run. The same run may confirm multiple previously inactive frames in a stable prefix at once: if a new stack [A, B] persists for n samples, both A and B start at the first sample's timestamp. An active frame ends after it is absent or replaced for at least n consecutive samples; emit its END at the first timestamp of that absence, deepest first. A shorter appearance or absence is transient and emits nothing. A deeper frame cannot remain active after an ancestor ends. At end of input, emit END events for every still-active frame at the last sample timestamp, deepest first.

Constraints

• 1 <= n <= len(samples) <= 100000
• Timestamps are strictly increasing integers.
• A stack contains unique non-empty function names and has depth at most 1000.
• The first accepted stack transitions from an empty stack.

Example

With n = 1, samples (10, [A, B]), (20, [A, C]), (30, []) produce:

(10, START, A), (10, START, B),
(20, END, B), (20, START, C),
(30, END, C), (30, END, A)

With n = 2, samples (10, [A, B]), (20, [A, C]), (30, [A, C]), (40, []), (50, []) start A at timestamp 10 even though its deeper frame changes, start C at timestamp 20, and end C then A at timestamp 40. B never becomes active.

Clarifications

For a confirmed per-frame run, retain its first timestamp even though confirmation arrives later. When several events share a timestamp, emit ends deepest first and then starts outermost first.

Hints

Track consecutive presence or absence per stack depth. Common prefixes identify surviving ancestors, but changing a deeper suffix must not reset an unchanged outer frame's confirmation count.

Extensions

• Process samples online while delaying output until a run is confirmed.
• Support a time-duration threshold instead of a sample-count threshold.
• Bound memory when stack depth is large.