Reconstruct call stacks from enter and exit traces: Frontier Interview's solution

Question: Reconstruct call stacks from enter and exit traces

Companies: Anthropic

Difficulty: Medium

Problem statement

A profiler gives you call stacks sampled over time, outermost frame first. Turn them into function start and end events, then go the other way: replay start/end events into stacks and the time spent on each. Follow-ups cover noisy samples (ignore frames seen in fewer than k consecutive samples), recursion, malformed traces, and traces where only recent frames are visible.

def events_from_samples(samples, min_samples=1):
    """samples: [(timestamp, ["main", "f", ...])] -> [("start" | "end", timestamp, name)]"""


def folded_stacks(events):
    """events -> {"main;f": time spent with exactly that stack}; raise ValueError on a bad trace"""

Approach

This question comes in two directions, and interviewers often ask one then the other: turn sampled call stacks into start/end events (what a sampling profiler does to draw a timeline), and turn events back into stacks with time spent (what a flame graph needs). The follow-ups add noise filtering and recursion. The format used here:

A sample is (timestamp, ["main", "parse", "read"]), outermost frame first.
An event is ("start" | "end", timestamp, name).

Clarify first. Are frames compared by name only, or by position (by position: main;f;f is two live calls of f)? When a frame disappears between samples at t=10 and t=20, does it end at 10 or 20 (we only know it ended in between; this answer uses the later sample's timestamp, which matches how profilers draw it)? Are the frames still on the stack after the last sample closed at its timestamp (yes here, so every start has an end)? Should a malformed trace raise or be repaired (raise in the strict replay; repair is a follow-up)?

Level 1: samples to events. Between two consecutive samples, find the length p of the common prefix, comparing frame by frame. Frames above p in the old stack ended: emit their end events innermost first. Frames above p in the new stack started: emit start events outermost first. Comparing by position is what makes recursion work: [main, f] to [main, f, f] is one new call, not "f is already running".

A subtle case: [main, a, b] to [main, c, b]. A name-set diff says only a changed. The prefix diff correctly says b and a ended and c and a new b started, because a b under c is a different call.

Level 2: events to stacks with time. Replay events onto a stack. Between two event timestamps, the current stack was live, so add the elapsed time to its folded key "main;parse;read". An end whose name is not on top of the stack means the trace is broken; raise with the position.

Level 3: drop noise. A function seen in just one sample is often sampling noise (the sample caught a 2 µs call). Rule: a frame counts only if the same frame (same prefix up to and including it) appears in at least k consecutive samples. Because a frame's prefix includes its callers, a frame's run is never longer than its parent's run. So for each sample, the filtered stack is simply its longest prefix whose run length is at least k. Compute run lengths per depth in one pass, cut each sample, then reuse Level 1.

Worked example. Samples at t=0 [main], t=10 [main, f], t=20 [main, f, g], t=30 [main, h].

0: start main. 10: start f. 20: start g. 30: end g, end f, start h. Closing at 30: end h, end main.
With k=2: g appears once, so it is dropped; f (2 samples) stays; h appears once and is dropped.

Code

def _common_prefix(a, b):
    n = 0
    while n < len(a) and n < len(b) and a[n] == b[n]:
        n += 1
    return n


def events_from_samples(samples, min_samples=1):
    """[(ts, [outer..inner])] -> [("start"|"end", ts, name)].

    A frame must appear in min_samples consecutive samples (same callers)
    to count; shorter runs are treated as noise.
    """
    stacks = _filter_noise([s for _, s in samples], min_samples)
    events, prev = [], []
    for (ts, _), cur in zip(samples, stacks):
        p = _common_prefix(prev, cur)
        for name in reversed(prev[p:]):
            events.append(("end", ts, name))
        for name in cur[p:]:
            events.append(("start", ts, name))
        prev = cur
    if samples:
        last_ts = samples[-1][0]
        for name in reversed(prev):
            events.append(("end", last_ts, name))
    return events


def _filter_noise(stacks, k):
    if k <= 1:
        return [list(s) for s in stacks]
    n = len(stacks)
    keep = [0] * n  # how many frames of each sample survive
    depth = max((len(s) for s in stacks), default=0)
    for d in range(depth):
        i = 0
        while i < n:
            if len(stacks[i]) <= d:
                i += 1
                continue
            prefix = stacks[i][: d + 1]
            j = i
            while j < n and stacks[j][: d + 1] == prefix:
                j += 1
            if j - i >= k:  # this frame instance lasted long enough
                for m in range(i, j):
                    if keep[m] == d:  # its parent survived too
                        keep[m] = d + 1
            i = j
    return [list(s[: keep[m]]) for m, s in enumerate(stacks)]


def folded_stacks(events):
    """Replay events; return {"main;f;g": time on that exact stack}."""
    stack, totals, last_ts = [], {}, None
    for pos, (kind, ts, name) in enumerate(events):
        if last_ts is not None and stack and ts > last_ts:
            key = ";".join(stack)
            totals[key] = totals.get(key, 0) + ts - last_ts
        last_ts = ts
        if kind == "start":
            stack.append(name)
        elif kind == "end":
            if not stack or stack[-1] != name:
                raise ValueError(f"event {pos}: end {name!r} but top is {stack[-1] if stack else None!r}")
            stack.pop()
        else:
            raise ValueError(f"event {pos}: unknown kind {kind!r}")
    if stack:
        raise ValueError(f"unclosed frames: {stack}")
    return totals

_filter_noise compares prefixes with slices for clarity, which costs O(depth) per comparison. If depth is large, compare one frame at a time and carry "parent unchanged" from the previous depth instead.

Complexity

Let S be the number of samples and D the maximum stack depth.

events_from_samples without filtering: O(S × D) time, O(S × D) output in the worst case (every frame changes every sample).
Noise filter: O(S × D²) as written because of prefix slices, O(S × D) with per-frame comparison.
folded_stacks: O(E × D) for E events, because each time slice builds its key; O(E) if the key is maintained incrementally.

Test cases

from solution import events_from_samples


def test_basic_timeline():
    samples = [(0, ["main"]), (10, ["main", "f"]), (20, ["main", "f", "g"]), (30, ["main", "h"])]
    assert events_from_samples(samples) == [
        ("start", 0, "main"),
        ("start", 10, "f"),
        ("start", 20, "g"),
        ("end", 30, "g"), ("end", 30, "f"), ("start", 30, "h"),
        ("end", 30, "h"), ("end", 30, "main"),
    ]


def test_recursion_is_positional():
    samples = [(0, ["main", "f"]), (5, ["main", "f", "f"]), (9, ["main", "f"])]
    ev = events_from_samples(samples)
    assert ev[:3] == [("start", 0, "main"), ("start", 0, "f"), ("start", 5, "f")]
    assert ev[3] == ("end", 9, "f")


def test_same_name_under_a_new_parent_is_a_new_call():
    samples = [(0, ["main", "a", "b"]), (1, ["main", "c", "b"])]
    ev = events_from_samples(samples)
    assert ev[3:7] == [("end", 1, "b"), ("end", 1, "a"), ("start", 1, "c"), ("start", 1, "b")]


def test_empty_input():
    assert events_from_samples([]) == []

from solution import events_from_samples, folded_stacks


def test_folded_time():
    samples = [(0, ["main"]), (10, ["main", "f"]), (25, ["main"]), (30, ["main"])]
    assert folded_stacks(events_from_samples(samples)) == {"main": 15, "main;f": 15}


def test_mismatched_end_raises():
    try:
        folded_stacks([("start", 0, "a"), ("start", 1, "b"), ("end", 2, "a")])
    except ValueError as e:
        assert "event 2" in str(e)
    else:
        assert False, "expected ValueError"

from solution import events_from_samples


def test_single_sample_frames_are_noise():
    samples = [(0, ["main"]), (10, ["main", "f"]), (20, ["main", "f", "g"]), (30, ["main", "h"])]
    assert events_from_samples(samples, min_samples=2) == [
        ("start", 0, "main"),
        ("start", 10, "f"),
        ("end", 30, "f"),
        ("end", 30, "main"),
    ]


def test_child_needs_its_own_run_under_the_same_parent():
    samples = [(0, ["m", "a", "x"]), (1, ["m", "b", "x"]), (2, ["m", "b", "x"])]
    ev = events_from_samples(samples, min_samples=2)
    assert ("start", 0, "a") not in ev
    assert ("start", 1, "b") in ev and ("start", 1, "x") in ev

Follow-ups

Only the top N frames are captured. Deep stacks get truncated at the root end, so two samples can look different only because the bottom fell off. Align from the innermost frame instead: compare suffixes, and treat the missing outer frames as unknown rather than ended. This is suffix matching, and it is the "only recent frames are visible" variant.
Repairing a broken event trace. When an end does not match the top, check whether the name is deeper in the stack. If so, assume the frames above it lost their exits and close them at this timestamp. If not, drop the event and count it. Report how many repairs were made; silent repair hides bugs in the tracer.
Multiple threads. Samples carry a thread id. Keep one previous stack per thread and run the same diff per thread; events carry the thread id too.
Streaming. Level 1 only needs the previous sample, so it runs in O(D) memory on an endless stream. The noise filter needs a lookahead of k - 1 samples before it can decide whether a new frame is real, so output is delayed by k - 1 samples.
Turning it into a flame graph. The folded output of Level 2 is exactly the input flame graph tools read (stack value per line). Merging identical keys is what turns a timeline into a profile.

Interviewer expectations

Mid-level (L4)

Gets the prefix diff right and emits ends innermost first and starts outermost first.
Handles recursion by comparing frames by position, and closes open frames at the end.
Replays events with a stack and detects a mismatched end.

Senior (L5)

Asks the clarifying questions (timestamp of an end, closing at the end, strict or repairing) before coding.
Explains why name-set diffs are wrong (a frame with the same name under a new parent is a new call).
Implements the noise filter correctly, using the fact that a child's run cannot outlast its parent's.

Staff (L6+)

Handles truncated stacks with suffix alignment and explains the ambiguity it leaves.
Designs for streaming (bounded memory, k - 1 delay) and for many threads.
Connects the output to real tooling (timelines, folded stacks, flame graphs) and to the profiler's sampling error.