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 Onsite rounds at Anthropic.

What role is this question designed for?

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

Simulate stack traces from logs | Anthropic Coding Question

Simulate stack traces from logs

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a list of log entries describing function calls, each formatted as "<id> <event> <timestamp>" where event ∈ {START, END} and timestamps are integers, compute the exclusive execution time for every function ID assuming calls may be nested and logs are in chronological order. Return a mapping id → exclusive_time. Follow-ups: ( 1) Adapt the solution if timestamps can be equal and some entries may be slightly out of order; describe how to correct or buffer the stream online. ( 2) Given a stream of categorical events (e.g., ERROR/WARN/INFO), detect the earliest index where the same value appears N consecutive times and return that window’s start index, or −1 if none. Analyze time and space complexity.

Quick Answer: This question evaluates stack-based simulation for computing exclusive execution time in nested function call logs and stream-processing concepts for handling equal timestamps, slight reordering, and detection of N consecutive categorical events.

Part 1: Exclusive execution time from nested logs

You are given a list of function log entries in chronological order. Each entry is a tuple `(id, event, timestamp)`, where `event` is either `'START'` or `'END'`. The program runs on a single thread, so only the function on top of the call stack is executing at any moment, and function calls may be nested. Use half-open timing: a `'START'` at time `t` means the function starts executing at `t`, and an `'END'` at time `t` means it stops executing at `t`. Therefore, a call from `START = s` to `END = e` lasts `e - s` time units. Compute the total exclusive execution time for every function id, aggregated across all of its calls.

Constraints

0 <= len(logs) <= 2 * 10^5
Each log is a tuple `(id, event, timestamp)`
`event` is either `'START'` or `'END'`
Timestamps are integers and may be equal
The given log order is valid and represents properly nested calls

Examples

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

Expected Output: {0: 3, 1: 3}

Explanation: Function 0 runs from 0 to 2, function 1 runs from 2 to 5, then function 0 resumes from 5 to 6.

Input: ([(2, 'START', 1), (2, 'END', 4), (5, 'START', 4), (5, 'END', 7)],)

Expected Output: {2: 3, 5: 3}

Explanation: Two top-level calls run back-to-back with no nesting.

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

Expected Output: {0: 5}

Explanation: The same function id appears in nested recursive calls, and times must be aggregated by id.

Input: ([],)

Expected Output: {}

Explanation: Edge case: no logs means no execution time.

Input: ([(7, 'START', 10), (7, 'END', 10)],)

Expected Output: {7: 0}

Explanation: Edge case: a zero-length call contributes 0 time.

Hints

Keep a stack of currently active function calls.
When a new log at time `t` arrives, the function on top of the stack has been running since the previous timestamp.

Part 2: Online exclusive time with equal timestamps and slightly out-of-order logs

A stream of function logs arrives almost, but not perfectly, in chronological order. Each log is a tuple `(id, event, timestamp)`, where `event` is `'START'` or `'END'`. Timestamps may be equal. Each log arrives at most `max_delay` positions later than where it belongs in the correct chronological order. To break ties when timestamps are equal, preserve the original arrival order among those equal-timestamp entries. After correcting the stream online using a small buffer, compute the exclusive execution time for every function id. Use half-open timing: a `'START'` at time `t` starts execution at `t`, and an `'END'` at time `t` stops execution at `t`.

Constraints

0 <= len(logs) <= 2 * 10^5
0 <= max_delay <= len(logs)
Each log is a tuple `(id, event, timestamp)`
`event` is either `'START'` or `'END'`
Each log is at most `max_delay` positions later than its correct position in the stable timestamp order
After stable sorting by `(timestamp, arrival_index)`, the call sequence is valid and properly nested

Examples

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

Expected Output: {0: 3, 1: 3}

Explanation: The middle two logs are swapped in arrival order. A buffer of size 2 restores the chronological order.

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

Expected Output: {0: 5, 1: 0}

Explanation: Equal timestamps are allowed. Function 1 starts and ends at the same time, so it contributes 0.

Input: ([(3, 'START', 3), (2, 'START', 1), (3, 'END', 3), (2, 'END', 6)], 1)

Expected Output: {2: 5, 3: 0}

Explanation: After stable reordering by timestamp, function 2 encloses a zero-length call to function 3.

Input: ([], 3)

Expected Output: {}

Explanation: Edge case: an empty stream produces an empty result.

Hints

If every item is at most `k` positions late, a min-heap of size `k + 1` can emit the next correct item online.
Once a corrected log is emitted, the exclusive-time accounting is the same stack-based idea as in Part 1.

Part 3: Earliest run of N identical consecutive events

You are given a stream of categorical events, such as `'ERROR'`, `'WARN'`, or `'INFO'`. Find the earliest index where the same value appears `N` times in a row. Return the starting index of that length-`N` window, or `-1` if no such window exists.

Constraints

0 <= len(events) <= 2 * 10^5
1 <= N <= 2 * 10^5
Event values only need to support equality comparison
Indices are 0-based

Examples

Input: (['INFO', 'WARN', 'WARN', 'WARN', 'ERROR'], 3)

Expected Output: 1

Explanation: The earliest run of length 3 is `'WARN', 'WARN', 'WARN'`, starting at index 1.

Input: ([1, 1, 2, 2, 2, 2], 4)

Expected Output: 2

Explanation: The value 2 appears four times consecutively starting at index 2.

Input: (['A', 'A', 'B', 'B'], 3)

Expected Output: -1

Explanation: No value appears 3 times in a row.

Input: ([], 1)

Expected Output: -1

Explanation: Edge case: an empty stream cannot contain any run.

Input: (['X', 'Y'], 1)

Expected Output: 0

Explanation: Edge case: when `N = 1`, the first event already forms a valid window.

Hints

You do not need a sliding-window frequency map; only the current run matters.
As soon as the current run length reaches `N`, you have found the earliest valid start.

Quick Overview

This question evaluates stack-based simulation for computing exclusive execution time in nested function call logs and stream-processing concepts for handling equal timestamps, slight reordering, and detection of N consecutive categorical events.