Convert stack samples to trace events

Q: Convert stack samples to trace events

This question evaluates a candidate's ability to convert chronologically ordered stack samples into start/end trace events, testing stateful stream processing, stack diffing, correct temporal ordering, and frame identity handling in the presence of recursion.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Anthropic.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Question

##### 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.

PracHub · Accepted Answer

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

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]

Quick Overview

Solution

Hints

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

Constraints

Examples

Solution

Hints

Quick Overview