Convert stack samples to trace events

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.

Part 1: Convert Stack Samples to Trace Events

Convert a chronologically ordered list of stack samples into a flat list of trace events that mark when each function frame starts and ends.

Input

samples is a list of (timestamp, stack) pairs, already ordered by time, where:

• timestamp is a non-decreasing integer.
• stack is a list of active function names ordered from outermost (caller) to innermost (most recently called), i.e. stack[0] is the bottom of the call stack and the last element is the top.

What to implement

def solution(samples):
    ...

Return a list of trace events, where each event is a triple (type, timestamp, name):

• type is the string 'start' or 'end'.
• timestamp is the timestamp of the sample being processed.
• name is the function name.

How to produce events

Process the samples in order. Compare each sample's stack to the previous sample's stack. Treat the previous stack as empty ([]) before the first sample, so every frame in the first sample is a fresh start.

For each sample, find the longest common prefix (LCP) of the previous stack and the current stack — the leading frames that match by both depth and name. These frames were running and are still running, so they produce no events. Then:

1. Ended frames — Every frame in the previous stack after the common prefix has ended at the current timestamp. Emit an ('end', timestamp, name) event for each, ordered from innermost to outermost (a callee ends before its caller).

2. Started frames — Every frame in the current stack after the common prefix has started at the current timestamp. Emit a ('start', timestamp, name) event for each, ordered from outermost to innermost (a caller starts before its callee).

Within a single sample, emit all of its end events first, then its start events.

Rules and edge cases

• Identical consecutive stacks produce no events (the common prefix covers both stacks entirely).
• The same function name may appear multiple times at different depths; each occurrence is a distinct recursive frame. Because the prefix is matched by position, repeated names (e.g. ['A', 'A']) are handled correctly.
• Do not emit end events for frames that are still present in the last sample — only frames that actually disappear between consecutive samples are ended.
• An empty samples list produces an empty list of events.

Example

Input:

[(1, ['A']), (2, ['A', 'B']), (3, ['A', 'C']), (4, ['A'])]

Output:

[('start', 1, 'A'), ('start', 2, 'B'), ('end', 3, 'B'), ('start', 3, 'C'), ('end', 4, 'C')]

A starts at time 1 and never ends (it is still active in the last sample). B starts at 2; at time 3 the stack changes from ['A', 'B'] to ['A', 'C'], so B ends and C starts; at time 4 C ends as the stack returns to ['A'].

Constraints

• 0 <= len(samples) <= 200000
• Timestamps are non-decreasing integers.
• Each stack is ordered from outermost to innermost.
• The total number of function names across all samples is at most 200000.
• Function names are non-empty strings.

Hints

1. For each pair of consecutive samples, find the longest common prefix of their stacks.
2. Everything removed from the old stack after that prefix ends first, from the back toward the front.

Approach

This is a diffing problem: we turn a sequence of stack snapshots into start/end events by comparing each snapshot to the one before it.

Key idea — the longest common prefix (LCP). Two consecutive stacks share a common outermost prefix of frames that were already running and are still running. Everything in the previous stack below that prefix has ended; everything in the current stack below it has just begun. So the whole transition is captured by one number: how many leading frames match.

Walkthrough of the code:

• prev_stack starts empty, so the first sample is diffed against [] (every frame is a fresh start).
• We scan up to limit = min(len(prev_stack), len(stack)) positions, incrementing lcp while prev_stack[lcp] == stack[lcp]. Comparing by depth+name correctly treats repeated names at different depths (e.g. recursion ['A','A']) as distinct frames.
• Ends: iterate prev_stack from the last index down to lcp (range(len(prev_stack)-1, lcp-1, -1)), emitting ('end', timestamp, name) — innermost-first, as required (a callee must end before its caller).
• Starts: iterate stack from lcp upward, emitting ('start', timestamp, name) — outermost-first (a caller starts before its callee).
• prev_stack = stack carries state forward.

Correctness: identical stacks give lcp == len, so both loops are empty (no events). Frames still present in the final sample are never popped, so no spurious end events are emitted — exactly the required behavior.

• Time complexity: O(S), where S is the total number of stack entries across all samples. Each frame is touched a constant number of times (once during the LCP scan, once when emitted as start or end).
• Space complexity: O(D) auxiliary, where D is the maximum stack depth (the prev_stack/stack copy), excluding the output list. The output itself is O(S).

Part 2: Emit Trace Events Only for Frames Lasting at Least N Samples

Given a sequence of stack samples from a profiler, emit start/end trace events only for stack frames that stay visible for at least N consecutive samples.

This is Part 2 of the trace-event problem. It uses the same input format and the same frame-identity rule as Part 1, but adds the N-consecutive-samples qualification and backdates start times.

Function signature

def solution(samples, n):

Input

• samples — a list of (timestamp, stack) pairs, in sampling order.
  • timestamp is an integer; timestamps are nondecreasing.
  • stack is a list of function-name strings ordered outermost first, innermost last (index 0 is the outermost frame).
• n — an integer; a frame must persist for at least n consecutive samples to produce events.

Output

Return a list of events, each a tuple (kind, timestamp, name):

• kind is 'start' or 'end'.
• timestamp is an integer.
• name is the function name of the frame.

If there are no qualifying frames (including when samples is empty), return an empty list.

Frame identity

A frame is identified by its position within the longest common prefix (LCP) shared with the previous sample. Concretely, a frame at depth d continues from one sample to the next only while every depth 0..d has the same function name in both stacks (i.e. depth d lies inside the LCP of the two stacks).

The moment the names diverge at some depth, every frame at that depth and deeper is considered gone, even if the same name reappears later or at a different depth.

Recursion note: because identity is tied to depth position, the same function name appearing at two different depths counts as two distinct frames.

Qualification rule (N consecutive samples)

• Track, for each currently-live frame, how many consecutive samples it has been visible at its depth (its streak) and the timestamp of the first sample of that streak.
• A frame qualifies (produces a start event) the first time its streak reaches n.
• The start event's timestamp is backdated to the timestamp of the first sample of the qualifying streak — i.e. when the frame was first seen — not the sample on which it reached n. (When n == 1, a frame qualifies on its very first sample.)
• If a frame disappears before its streak reaches n, emit nothing for it (no start and no end).

End events

• When a frame that had already produced a start event disappears, emit exactly one end event at the timestamp of the sample in which it disappeared.
• Frames that are still on the stack in the last sample are unfinished, so they receive no end event.

Same-timestamp ordering

When multiple events share the same timestamp:

• End events come before start events.
• Among end events at the same timestamp, emit inner frames before outer frames (deeper depth first).
• Among start events at the same timestamp, emit outer frames before inner frames (shallower depth first).

Example

For samples = [(1, ['A']), (2, ['A']), (3, ['A', 'B']), (4, ['A', 'B']), (5, ['A']), (6, [])] and n = 2:

• A is visible at samples ts 1 and 2 → streak reaches 2 at ts 2 → start backdated to ts 1.
• B first appears at ts 3 and is visible again at ts 4 → streak reaches 2 → start backdated to ts 3.
• B disappears at ts 5 → end at ts 5.
• A disappears at ts 6 → end at ts 6.

Result: [('start', 1, 'A'), ('start', 3, 'B'), ('end', 5, 'B'), ('end', 6, 'A')]

Constraints

• 0 <= len(samples) <= 200000
• 1 <= n <= 200000
• Timestamps are nondecreasing integers.
• Each stack is ordered from outermost to innermost.
• The total number of function names across all samples is at most 200000.
• Function names are non-empty strings.

Hints

1. Track each active depth as a frame record: function name, first seen timestamp, current streak length, and whether its start event has already been emitted.
2. When two consecutive samples diverge, only the longest common prefix continues. Everything deeper is either ending now or starting a new pending streak.

Approach

The solution simulates a stack profiler in one linear pass, deciding which frames live long enough to deserve events.

State. active is the current logical call stack, one entry per depth: [name, first_seen_ts, streak_length, started]. streak_length counts consecutive samples this exact frame has stayed at this depth; started records whether we've already emitted its (backdated) start.

Per sample:

1. Longest common prefix (LCP). Walk depths while active[d].name == stack[d]. Everything up to lcp is the same frame continuing; anything below it is a new/different frame. This implements the "frame identity = position in the LCP with the previous sample" rule, so same-named recursive calls at different depths stay distinct.
2. Disappearances. Frames at depth >= lcp in active are gone. For each (innermost first), if it had started, push an end keyed (ts, 0, -depth).
3. Survivors. Truncate active to lcp, then increment each survivor's streak. When a survivor's streak first reaches n and isn't started yet, emit a start backdated to its first_seen_ts, keyed (first_ts, 1, depth).
4. New frames. Append frames for depths lcp..len(stack). With n == 1 a frame qualifies on first sight, so its start is emitted immediately.

Ordering. Events sort by (timestamp, phase, tiebreak). phase 0=end before phase 1=start; ends use -depth so inner-before-outer; starts use +depth so outer-before-inner — exactly the spec's same-timestamp rules. Frames still active after the final sample are simply never closed, so they get no end event.

• Time complexity: O(S + E log E)
• Space complexity: O(D + E)