Sampling Profiler → Trace Events (Sample/Event types)

PracticalhardPremium

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

Sampling profilers find the slow parts of code by periodically capturing the entire call stack. Lots of execution might happen between samples. You're given the samples - convert them into a list of start and end events you could feed to a trace-visualization UI.

Each sample is a snapshot of every function currently executing, outermost-first, innermost-last. Output events should be properly nested: a child function's start is after its parent's start, and the child's end comes before the parent's end.

Data types (already provided in the starter)

@dataclass
class Sample:
    ts: float          # when the snapshot was taken
    stack: list[str]   # call stack, outermost-first

@dataclass
class Event:
    kind: str          # 'start' or 'end'
    ts: float          # the sample's timestamp
    name: str          # function name

These are part of the contract - the tests from solution import Sample, Event, samples_to_trace.

Level 1 - Basic trace

def samples_to_trace(samples: list[Sample]) -> list[Event]: ...

Compare each sample with the previous one:

Find the first index where they differ - the divergence point.
Frames after that index in the previous stack have ended → emit end events, deepest-first.
Frames after that index in the current stack have started → emit start events, shallowest-first.
After the final sample, flush any still-open frames as end events (deepest-first).

Example:

samples = [
    Sample(ts=7.5,  stack=["main"]),
    Sample(ts=9.2,  stack=["main", "my_func"]),
    Sample(ts=10.7, stack=["main"]),
]
# →
[
    Event(kind='start', ts=7.5,  name='main'),
    Event(kind='start', ts=9.2,  name='my_func'),
    Event(kind='end',   ts=10.7, name='my_func'),
    Event(kind='end',   ts=10.7, name='main'),
]

Level 2 - Recursive functions

The same name can appear at multiple depths in the same stack. Each occurrence is a distinct frame and gets its own start/end pair.

Example:

samples = [
    Sample(ts=1.0, stack=["main", "fib", "fib"]),   # fib at depth 1 AND depth 2
    Sample(ts=2.0, stack=["main", "fib"]),
]
# Both fib frames get their own start/end events

Level 3 - `min_count` debounce

def samples_to_trace(samples: list[Sample], min_count: int = 1) -> list[Event]: ...

A frame must appear in min_count consecutive samples at the same depth before its start event is emitted.

The start timestamp is the first time the frame was seen at that depth - not the timestamp at which it was confirmed.
If a frame disappears before reaching min_count, drop it silently. No events.
End events are only emitted for frames whose start was already emitted.

Example:

samples_to_trace([
    Sample(ts=1.0, stack=["main"]),
    Sample(ts=2.0, stack=["main"]),   # confirmed; start ts is 1.0
    Sample(ts=3.0, stack=[]),
], min_count=2) == [
    Event("start", 1.0, "main"),
    Event("end",   3.0, "main"),
]

Patterns used

Foundations primers this challenge draws on.

Stacks

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed