Stack Samples → Trace Events

Q: Stack Samples → Trace Events

A sampling profiler captures call stacks at fixed intervals. Convert those snapshots into start/end span events. Three phases - basic diff, recursion, then a min-consecutive-count debounce.

PracticalhardFree

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

A sampling profiler periodically snapshots the entire call stack of a running program. You will convert those snapshots into start/end trace events - the input to a flame-graph renderer. Each sample is (timestamp: float, stack: list[str]) with the stack outermost-first. Each output event is (timestamp: float, kind: str, function_name: str) where kind is 's' (start) or 'e' (end).

Implement samples_to_trace(samples, min_count=1) in solution.py. The three phases below are independent test suites.

Level 1 - Basic trace

The shape of the diff:

A function in the current sample but not in the previous one → emit a start event
A function in the previous sample but not the current → emit an end event
At the same timestamp, end events come before start events (the old call site closes before the new one opens)
End events are emitted deepest-first; start events are emitted shallowest-first
After the last sample, flush any still-open frames as end events (deepest-first)

Example:

samples = [
    (1.0, ["main", "foo"]),
    (2.0, ["main", "bar"]),
    (3.0, []),
]
 
samples_to_trace(samples) == [
    (1.0, 's', 'main'),
    (1.0, 's', 'foo'),
    (2.0, 'e', 'foo'),
    (2.0, 's', 'bar'),
    (3.0, 'e', 'bar'),
    (3.0, 'e', 'main'),
]

Level 2 - Recursive frames

The same function name can appear at multiple depths in one stack - that's recursion:

samples = [
    (1.0, ["main", "fib", "fib"]),   # fib at depth 1 AND depth 2
    (2.0, ["main", "fib"]),           # only fib at depth 1 remains
]

Treat the same function name at different depths as distinct frames - the depth-2 fib ends before the depth-1 fib does.

Example:

samples = [
    (1.0, ["main", "fib", "fib"]),   # fib at depth 1 AND depth 2
    (2.0, ["main", "fib"]),           # depth-2 fib ends
    (3.0, []),
]
# depth-2 fib gets its own start and end events

Level 3 - Minimum consecutive count

Sampling profilers see noise. A frame that appears in one sample and then vanishes might be a real but very short call - or it might be sampling jitter you don't want in the output.

Add a min_count: int = 1 parameter. A frame must appear in min_count consecutive samples at the same depth before its start event is emitted.

The start event timestamp is the first appearance, not when it was confirmed.
If a frame disappears before reaching min_count, discard it silently - no start, no end.
End events are only emitted for frames whose start was already emitted.

Example:

samples_to_trace([
    (1.0, ["main"]),
    (2.0, ["main"]),   # main confirmed at t=1.0
    (3.0, []),
], min_count=2) == [
    (1.0, 's', 'main'),   # emitted at t=2.0 but with first-seen timestamp t=1.0
    (3.0, 'e', 'main'),
]

Files

solution.py - implement samples_to_trace here. This is the only file you can edit.
test_level1.py, test_level2.py, test_level3.py - test files for each phase. Read-only. Run each phase separately.

Patterns used

Foundations primers this challenge draws on.

Greedy

Queues

Stacks

Loading editor...

0/3 passed

Level 1 - Basic trace (tuple-based samples and events).

Diff consecutive stacks on each sample. At a divergence point: emit 'e' (end) events for departed frames deepest-first, then 's' (start) events for new frames shallowest-first. After the last sample, flush all still-open frames as end events deepest-first.

Level 2 - Recursive frames.

Locked

Pass the previous level to unlock.

Level 3 - Minimum consecutive count debounce.

Locked

Pass the previous level to unlock.