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 ```python 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.

def solution(samples):
    events = []
    prev_stack = []

    for timestamp, stack in samples:
        stack = list(stack)
        lcp = 0
        limit = min(len(prev_stack), len(stack))
        while lcp < limit and prev_stack[lcp] == stack[lcp]:
            lcp += 1

        for i in range(len(prev_stack) - 1, lcp - 1, -1):
            events.append(('end', timestamp, prev_stack[i]))

        for i in range(lcp, len(stack)):
            events.append(('start', timestamp, stack[i]))

        prev_stack = stack

    return events

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 ```python 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.

def solution(samples, n):
    events = []
    active = []  # [name, first_seen_timestamp, streak_length, started]

    for timestamp, stack in samples:
        stack = list(stack)

        lcp = 0
        limit = min(len(active), len(stack))
        while lcp < limit and active[lcp][0] == stack[lcp]:
            lcp += 1

        for depth in range(len(active) - 1, lcp - 1, -1):
            name, first_ts, streak, started = active[depth]
            if started:
                events.append((timestamp, 0, -depth, 'end', name))

        active = active[:lcp]

        for depth in range(lcp):
            active[depth][2] += 1
            if not active[depth][3] and active[depth][2] >= n:
                active[depth][3] = True
                events.append((active[depth][1], 1, depth, 'start', active[depth][0]))

        for depth in range(lcp, len(stack)):
            started = (n == 1)
            frame = [stack[depth], timestamp, 1, started]
            active.append(frame)
            if started:
                events.append((timestamp, 1, depth, 'start', stack[depth]))

    events.sort(key=lambda e: (e[0], e[1], e[2]))
    return [(kind, timestamp, name) for timestamp, _, _, kind, name in events]