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.

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.

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.

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...