Quick Overview

Convert sampled call stacks to inferred start/end events using ordered common prefixes, recursive frames, explicit final-open behavior, and last-N history limitations.

Convert Sampled Call Stacks into Start and End Events

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Convert a sequence of sampled call stacks into inferred function start and end events. Compare adjacent stacks by their common prefix, ending frames that disappeared and starting frames that appeared. Implement `stack_samples_to_events(times: int[], stacks: string[][]) -> string[][]`. Each output is `[time,event,functionName]`, with time as a decimal string and event `START` or `END`. ### Constraints & Assumptions - Times are strictly increasing nonnegative integers at most 1000000000, one per stack. At most 100000 samples and 1000000 total frames. - Each stack is ordered outermost to innermost. Names are nonempty ASCII identifiers. Recursive calls may repeat the same name at different depths; these are separate frames. - Treat the stack before the first sample as empty. At sample time t, emit END events for the previous stack's non-common suffix from innermost to outermost, then START events for the current non-common suffix from outermost to innermost. - Frames in the common prefix continue. Empty samples are valid. Do not deduplicate repeated function names within a stack. - Do not invent an end time after the final sample. Frames still present remain open in the returned trace. Empty input returns an empty list. - This is an inferred transition trace at sample times, not a reconstruction of every actual function call between samples. ### Example ```text times = [10,20,30] stacks = [["main","f"],["main","f","f"],["main","g"]] result = [["10","START","main"],["10","START","f"], ["20","START","f"],["30","END","f"],["30","END","f"], ["30","START","g"]] ``` Explain recursion, event ordering, and the common-prefix comparison. For the reported last-N-samples follow-up, discuss which prior stack/state a streaming converter needs, what can still be emitted prospectively, and why an arbitrary retained suffix cannot recover transitions or true start times before its first retained sample. ```hint Stack identity includes depth Equal names at different depths are distinct calls. Only an equal prefix of the two ordered frame sequences can be kept open across the sampled transition. ```

Overview: Convert sampled call stacks to inferred start/end events using ordered common prefixes, recursive frames, explicit final-open behavior, and last-N history limitations.

Read the full Anthropic Software Engineer interview experience this question came from

Convert a sequence of sampled call stacks into inferred function start and end events. Compare adjacent stacks by their common prefix, ending frames that disappeared and starting frames that appeared. Implement `stack_samples_to_events(times: int[], stacks: string[][]) -> string[][]`. Each output is `[time,event,functionName]`, with time as a decimal string and event `START` or `END`. ### Constraints & Assumptions - Times are strictly increasing nonnegative integers at most 1000000000, one per stack. At most 100000 samples and 1000000 total frames. - Each stack is ordered outermost to innermost. Names are nonempty ASCII identifiers. Recursive calls may repeat the same name at different depths; these are separate frames. - Treat the stack before the first sample as empty. At sample time t, emit END events for the previous stack's non-common suffix from innermost to outermost, then START events for the current non-common suffix from outermost to innermost. - Frames in the common prefix continue. Empty samples are valid. Do not deduplicate repeated function names within a stack. - Do not invent an end time after the final sample. Frames still present remain open in the returned trace. Empty input returns an empty list. - This is an inferred transition trace at sample times, not a reconstruction of every actual function call between samples. ### Example ```text times = [10,20,30] stacks = [["main","f"],["main","f","f"],["main","g"]] result = [["10","START","main"],["10","START","f"], ["20","START","f"],["30","END","f"],["30","END","f"], ["30","START","g"]] ``` Explain recursion, event ordering, and the common-prefix comparison. For the reported last-N-samples follow-up, discuss which prior stack/state a streaming converter needs, what can still be emitted prospectively, and why an arbitrary retained suffix cannot recover transitions or true start times before its first retained sample. ```hint Stack identity includes depth Equal names at different depths are distinct calls. Only an equal prefix of the two ordered frame sequences can be kept open across the sampled transition. ```

Constraints

  • 0 <= number of samples <= 100000; times and stacks have equal length.
  • Times are strictly increasing integers in [0, 1000000000]; total frames <= 1000000.
  • Each stack is outermost to innermost and contains nonempty ASCII identifiers; repeated names and empty stacks are valid.
  • Emit END for the old noncommon suffix innermost first, then START for the new suffix outermost first; preserve common-prefix frames.
  • Output times as decimal strings. Do not close frames after the last sample. Empty input returns [].

Examples

Input: ([10, 20, 30], [['main', 'f'], ['main', 'f', 'f'], ['main', 'g']])

Expected Output: [['10', 'START', 'main'], ['10', 'START', 'f'], ['20', 'START', 'f'], ['30', 'END', 'f'], ['30', 'END', 'f'], ['30', 'START', 'g']]

Explanation: Recursive frames are separate and both end before g starts.

Input: ([2, 9], [['a', 'b'], ['c', 'b']])

Expected Output: [['2', 'START', 'a'], ['2', 'START', 'b'], ['9', 'END', 'b'], ['9', 'END', 'a'], ['9', 'START', 'c'], ['9', 'START', 'b']]

Explanation: Matching suffix names cannot continue across a changed parent.

Loading coding console...

Show the approach

Approach

For each sample, the longest equal prefix consists precisely of the frames that continue: a frame is identified by both its ancestry and depth. Close the old suffix in reverse order before opening the new suffix in forward order. This preserves the stack transition invariant even when recursive frames share names. The previous stack starts empty. No extra transition is added at the end, so the final frames remain open. A streaming converter needs the immediately preceding complete stack to emit the next transition. To reproduce a retained suffix exactly it also needs the stack immediately before its first retained sample; preserving historical start times needs extra history. Without that boundary state, treating the first retained stack as newly opened invents starts, and lost transitions or true start times cannot be reconstructed. Let n be the sample count and F the total number of frames. Each adjacent prefix comparison and suffix visit is charged to frames in those samples, giving O(n+F) frame operations; string equality and copied output have their ordinary character costs. The returned output has O(F) events. Excluding arguments and output, traversal uses O(1) state; the C++ value parameters additionally copy the input.

Time complexity:
O(n + F) frame operations, plus identifier comparison and output character costs
Space complexity:
O(F) output events; O(1) traversal state excluding input copies