Quick Overview

This question evaluates a candidate's competency in designing efficient event-driven algorithms and time-based state management, including handling duplicates, out-of-order events, concurrent updates, and edge-case timeout semantics.

Design event timeout detector

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement an event-timeout detector for a job scheduler. Inputs: a global timeout T and a stream of events; each event has {event_id, type ∈ {start, end, ping}, timestamp}. Behavior: an event times out if it has started, not ended, and now_ts − last_updated_ts > T; ping updates last_updated_ts; end removes the event from consideration. Provide APIs process(event) and get_timed_out(now_ts) → list[event_id]. Use efficient data structures (e.g., hash map plus LRU/min-heap) to support many concurrent events. State how you handle duplicates, out-of-order events, events without a prior start, multiple starts, and zero/negative timeouts, and analyze time/space complexity.

Quick Answer: This question evaluates a candidate's competency in designing efficient event-driven algorithms and time-based state management, including handling duplicates, out-of-order events, concurrent updates, and edge-case timeout semantics.

Implement an event-timeout detector for a job scheduler. You are given a global timeout `T` and a sequence of API calls. Each event has: - `event_id` (integer) - `type` in `{start, ping, end}` - `timestamp` (integer) An event is considered active after a `start` and remains active until a valid `end` is processed. Timeout rule: - An active event is timed out at time `now_ts` if `now_ts - last_updated_ts > T`. - `ping` updates `last_updated_ts`. - `end` removes the event from consideration. - A timed-out event stays timed out until it receives a newer `start`/`ping` or a valid `end`. Because this platform expects a single function, implement `solution(T, operations)` where: - `("process", event_id, type, timestamp)` means call `process(event)` - `("get", now_ts)` means call `get_timed_out(now_ts)` Return the result of every `get` call. Required behavior for tricky cases: - `ping` or `end` without a prior active `start`: ignore. - Duplicate or stale `start`/`ping` with `timestamp <=` the event's latest accepted timestamp: ignore. - A valid `end` for an active event is accepted only if `end.timestamp >= last_updated_ts`; otherwise it is stale and ignored. - Multiple `start` events: if the new `start` has a strictly larger timestamp, treat it as a restart/reset. - A new `start` after an `end` is allowed only if its timestamp is strictly larger than the last accepted timestamp for that event. - Zero or negative timeouts use the same strict rule `now_ts - last_updated_ts > T`. For deterministic output, each `get` must return currently timed-out `event_id`s in the order they became timed out; if multiple events become timed out on the same `get`, smaller `event_id` comes first.

Constraints

  • 0 <= len(operations) <= 200000
  • event_id and timestamps are integers in the range [-10^9, 10^9]
  • type is one of 'start', 'ping', or 'end'
  • All `get` operations are given in non-decreasing `now_ts` order

Examples

Input: (5, [('process', 1, 'start', 0), ('process', 2, 'start', 1), ('process', 1, 'ping', 3), ('get', 6), ('process', 2, 'end', 7), ('get', 9)])

Expected Output: [[], [1]]

Explanation: At time 6, event 1 was updated at 3 and event 2 at 1, so neither satisfies `now - last_updated > 5`. After event 2 ends, time 9 makes event 1 timed out because `9 - 3 = 6 > 5`.

Input: (4, [('process', 10, 'start', 5), ('process', 10, 'ping', 3), ('process', 10, 'start', 5), ('process', 10, 'ping', 9), ('process', 10, 'end', 8), ('get', 13), ('get', 14)])

Expected Output: [[], [10]]

Explanation: The ping at 3 and repeated start at 5 are stale/duplicate and ignored. The end at 8 is stale because the latest accepted timestamp is 9. At time 13, `13 - 9 = 4` is not greater than 4, but at time 14 it is.

Hints

  1. Use a hash map to store the current state of each event: whether it is active, its latest accepted timestamp, and a version number.
  2. Use a min-heap of expiration deadlines (`last_updated_ts + T`) plus lazy deletion so old heap entries do not need to be removed immediately.

Loading coding console...