Software Engineer · Full Journey · Coding

Anthropic — Software Engineer

Level: Unknown Level

Round: Full Journey · Type: Coding · Difficulty: 8/10 · Duration: 60 min · Interviewer: Neutral

Topics: Hash Table, String

Location: San Francisco Bay Area

Interview date: 2025-12-26

Summary

I was asked to implement a function that converts sampled stacks into a chronological list of events, formatted as "<type>:<time>:<function>". The input consists of sampled stacks, where each stack entry is a string formatted as "<time>:<stackTrace>". I needed to determine function starts and ends based on differences between consecutive snapshots and output them in the specified format. I also need to handle recursive calls correctly, treating each occurrence as a distinct call frame.

Details

A sampling profiler captures the execution state of a single thread at discrete time points. Each entry in the array samples is formatted as:

"<time>:<stackTrace>"

where:

• time is an integer timestamp that strictly increases across entries.
• stackTrace represents the current call stack, written as a sequence of function names separated by "->". The order goes from the outermost function to the currently executing function. For example, "main->worker->parse" indicates that main called worker, which in turn called parse.

The stack portion may also be empty (for example "42:"), meaning that no functions are running at that moment.

Since the profiler only records snapshots, any number of function calls or returns may occur between two consecutive samples. Your task is to infer the function call events by comparing successive snapshots.

Convert the stack samples into a sequence of chronological events. Each event should follow the format:

` "<type>:<time>:<function>"

`

where:

• type is either "start" or "end".
• time is the timestamp associated with the current sample.
• function is the name of the function involved.

Event generation rules:

• A function starts if it appears in the current stack after the longest common prefix shared with the previous stack.
• A function ends if it appears in the previous stack beyond the shared prefix but is absent from the current stack.
• When producing "end" events, they must be listed from the innermost function outward, because a callee always finishes before its caller.

Additional notes:

• The same function name may appear multiple times in the stack (for example "a->b->a->c"), which represents recursive calls.
• Each appearance corresponds to a separate call frame and should be handled independently.
• If functions are still active after processing the final sample, no "end" events should be emitted for them.

Constraints:

• 1 ≤ samples.length ≤ 1000
• Timestamps are strictly increasing.
• Function names contain only letters, digits, or underscores.

Example 1

` samples = [ "10:main->calc", "20:main->calc->helper", "30:main->calc->helper->helper", "40:main->calc->helper", "50:main" ]

[ "start:10:main", "start:10:calc", "start:20:helper", "start:30:helper", "end:40:helper", "end:50:helper", "end:50:calc" ] `

Example 2

` samples = [ "5:main", "10:main->foo", "15:main->foo->bar", "20:main" ]

[ "start:5:main", "start:10:foo", "start:15:bar", "end:20:bar", "end:20:foo" ] `

Example 3 ` samples = [ "0:", "10:main", "20:main->process" ]

[ "start:10:main", "start:20:process" ] `

My Proposed Solution

` from typing import List, Optional

class Solution: def stackEvents(self, samples: List[str]) -> List[str]: events = [] prevStack = []

    for sample in samples:
        parts = sample.split(":", 1)
        time = parts[0]
        stackTrace = parts[1] if len(parts) > 1 else ""

        currStack = []
        if stackTrace:
            frames = stackTrace.split("->")
            for frame in frames:
                currStack.append(frame)

        # Find common prefix length
        prefixLen = 0
        while (prefixLen < len(prevStack)
               and prefixLen < len(currStack)
               and prevStack[prefixLen] == currStack[prefixLen]):
            prefixLen += 1

        # Generate end events from the old stack
        for i in range(len(prevStack) - 1, prefixLen - 1, -1):
            events.append(f"end:{time}:{prevStack[i]}")

        # Generate new start events
        for i in range(prefixLen, len(currStack)):
            events.append(f"start:{time}:{currStack[i]}")

        prevStack = currStack

    return events

`

LeetCode similar: LeetCode 636