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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Compute exclusive times and call stack from logs

Quick Overview

This question evaluates a candidate's ability to process single-threaded execution logs and compute per-function exclusive durations while reconstructing the call stack at a given timestamp, testing stack simulation, interval reasoning, timestamp tie-handling, parsing of time-stamped events, and algorithmic complexity analysis.

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design an algorithm that, given a single-threaded program's execution log, computes per-function exclusive durations and reconstructs the active call stack at an arbitrary time. Input: ( 1) integer m = number of function IDs (0..m- 1); ( 2) list logs where each entry is the string "t,event,id" with t as a non-negative integer timestamp in milliseconds, event in {BEGIN, END}, and id in [0..m-1]. The list is sorted by t; for equal t, process END before BEGIN. Each BEGIN has a matching END; calls may nest but the runtime is single-threaded. Also given an integer q representing a query timestamp. Output: (a) durations, a length-m array where durations[i] is the total exclusive time spent running function i (excluding time consumed by its child calls); (b) stack_q, the ordered list of function IDs from bottom to top that are active at time q (empty if none). Implement an O (n) time solution using O(m + call_depth) space, clarify how timestamps are treated (use half-open intervals [start, end)), and explain how you handle ties and edge cases (back-to-back events, nested calls, and q outside any interval).

Quick Answer: This question evaluates a candidate's ability to process single-threaded execution logs and compute per-function exclusive durations while reconstructing the call stack at a given timestamp, testing stack simulation, interval reasoning, timestamp tie-handling, parsing of time-stamped events, and algorithmic complexity analysis.

You are given the execution trace of a single-threaded program with function IDs in the range 0 to m - 1. Each log entry is a string in the form "t,event,id", where t is a non-negative integer timestamp in milliseconds, event is either BEGIN or END, and id is the function ID. Interpret every call as a half-open interval [start, end). That means a function that begins at time 2 and ends at time 5 runs for 3 milliseconds and is active at times 2, 3, and 4, but not at time 5. If multiple events share the same timestamp, process them in the given order, and the input guarantees that END events come before BEGIN events at that timestamp. Because the runtime is single-threaded, only the function at the top of the call stack is actually running at any moment. Calls may be nested or recursive, and every BEGIN has a matching END. Return a tuple (durations, stack_q): - durations is a list of length m where durations[i] is the total exclusive time spent running function i, excluding time spent inside child calls. - stack_q is the list of active function IDs at query time q, ordered from bottom to top of the call stack. If no function is active at time q, stack_q should be empty. Design an O(n) time solution, where n is the number of log entries.

Constraints

0 <= m <= 10^5
0 <= len(logs) <= 2 * 10^5
Each log entry is a valid string "t,event,id" with event in {BEGIN, END} and 0 <= id < m
The log sequence is well-formed, properly nested, and sorted by timestamp; for equal timestamps, END entries appear before BEGIN entries
q can be any integer, including values outside all execution intervals
Use half-open intervals [start, end) when computing both durations and the active stack

Examples

Input: (2, ['0,BEGIN,0', '2,BEGIN,1', '5,END,1', '6,END,0'], 3)

Expected Output: ([3, 3], [0, 1])

Explanation: Function 0 runs exclusively during [0,2) and [5,6), for 3 total. Function 1 runs during [2,5), for 3 total. At time 3, the active stack is [0, 1].

Input: (2, ['0,BEGIN,0', '4,END,0', '4,BEGIN,1', '6,END,1'], 4)

Expected Output: ([4, 2], [1])

Explanation: Function 0 is active on [0,4), so it is not active at time 4. Function 1 begins at time 4 and is active on [4,6). The tie at timestamp 4 is handled by processing END before BEGIN.

Input: (1, ['0,BEGIN,0', '1,BEGIN,0', '3,END,0', '5,END,0'], 2)

Expected Output: ([5], [0, 0])

Explanation: This is a recursive call. The outer call contributes 1 ms from [0,1) and 2 ms from [3,5). The inner call contributes 2 ms from [1,3). Total exclusive time for function 0 is 5, and both frames are active at time 2.

Input: (3, [], 10)

Expected Output: ([0, 0, 0], [])

Explanation: There are no log entries, so all exclusive times are 0 and no function is active at any query time.

Input: (2, ['5,BEGIN,0', '7,END,0'], 4)

Expected Output: ([2, 0], [])

Explanation: Function 0 runs on [5,7), so it contributes 2 ms. The query time 4 is before any function begins, so the active stack is empty.

Hints

Use a stack to represent the active calls. Between two consecutive event timestamps, only the function on top of the stack can accumulate exclusive time.
For the query timestamp q, think about what the stack should look like after processing all events with timestamp <= q. With half-open intervals, END at time t removes a function before checking activity at t, while BEGIN at time t adds a function that is active at t.

Quick Overview