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.

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.

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.

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.

Hints

  1. Keep a stack of currently active function calls.
  2. 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.

Approach

The solution combines an online reordering buffer with the classic stack-based exclusive-time accounting. Correcting the stream. Logs arrive at most max_delay positions out of place relative to the stable (timestamp, arrival_index) order. To recover that order online, a min-heap of (timestamp, arrival_index, entry) is used as a sliding window. After each push, whenever the heap holds more than max_delay + 1 items, the smallest is popped and processed. A buffer of size max_delay + 1 is exactly enough: any log displaced by at most max_delay positions is guaranteed to already be in the heap before its true predecessor must be emitted, so pops come out in correct chronological order. arrival_index in the key breaks timestamp ties by original arrival order. After the loop, the heap is drained. Exclusive-time accounting (process). A stack holds the currently-running call chain. Before applying each event, the function on top of the stack (the one actually executing) is credited with the elapsed gap timestamp - prev_time. This is half-open timing: time is attributed up to — but not including — the current event's timestamp. Then: - START pushes the id (it begins running at t), - END pops it (it stops at t), validating that the top matches. prev_time is advanced to the current timestamp each step. times.setdefault(fid, 0) ensures every id appears, even with zero exclusive time. Correctness. Crediting only the stack top means an outer call gets no time while an inner call runs, which is precisely exclusive time. Equal-timestamp events contribute zero-width gaps, so order among them doesn't affect totals but keeps the stack valid. Final guards reject unclosed calls.

Time complexity: O(n log(max_delay + 1))

Space complexity: O(max_delay + d + u), where d is the maximum corrected call-stack depth and u is the number of distinct ids

Hints

  1. If every item is at most `k` positions late, a min-heap of size `k + 1` can emit the next correct item online.
  2. 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.

Hints

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

Loading coding console...

Show the approach

Approach

Approach: stack of active calls + delta charging

Because the program is single-threaded, only the function on top of the call stack is executing at any instant. The trick is to walk the log entries in order and, at every event, charge the time slice since the previous event to whoever was on top of the stack during that slice — then update the stack for the current event.

Key state

  • stack: ids of currently-active calls, top = the one actually running.
  • prev_time: timestamp of the previous log entry, i.e. the start of the slice we're about to close.
  • times: a defaultdict(int) accumulating exclusive time per id (each id is also seeded with 0 so functions whose total is 0 still appear).

Per-event steps

  1. If something is on the stack, add timestamp - prev_time to times[stack[-1]]. This attributes the slice [prev_time, timestamp) to the function that was running over it — the half-open convention.
  2. On 'START', push the id (the new call becomes the running one going forward). On 'END', verify the top matches fid, then pop (control returns to the caller below).
  3. Set prev_time = timestamp.

Why it's correct. When a child runs, its parent sits below it on the stack, so step 1 only ever credits the child — giving exclusive (self) time, not inclusive. Nested and recursive same-id calls work too: in (0,START),(0,START),(0,END),(0,END), each 0-slice is credited to id 0, summing across calls. The raise guards reject mismatched or unclosed sequences.

One subtlety: prev_time is None only before the first event, where the stack is empty, so no time is charged on that first iteration — exactly right.

Time complexity:
O(n), where n is the number of log entries — a single pass with O(1) work per entry (each id pushed/popped at most once).
Space complexity:
O(u + d), where u is the number of distinct ids (the `times` map) and d is the maximum nesting depth (the `stack`).