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.
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.
Read the full Applied Intuition Software Engineer interview experience this question came from
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
- Use a hash map to store the current state of each event: whether it is active, its latest accepted timestamp, and a version number.
- 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.
Community answers
Answer by devyaoyh
"""
valid trajectories
start -> ping -> ping -> end
start -> ping -> start
FSM state transitions
start -> ping # update timestamp
ping -> start # restart event
end -> start # restart event
start -> end # end current event
ping -> end # end current event
Have the same check (no prior start event)
ping -> # reject
end -> # reject
ping -> end -> #reject
start -> end -> ping # rejected
start -> ping -> end -> end # reject
"""
from enum import Enum
from dataclasses import dataclass
from heapq import heappop, heappush
from collections import deque
class EventState(Enum):
START = 0
PING = 1
END = 2
@dataclass
class Event():
event_id: int
state: EventState
last_updated_ts: int
timeout_ts: int = 0
generation_count: int = 0
has_timed_out: bool = False
@dataclass(frozen=True, order=True)
class TimeoutEvent():
timeout_ts: int
event_id: int
generation_count: int
class ProcessQueue():
def init(self, T: int):
self.global_timeout = T
self.events: dict[int, Event] = {} # canonical event store
self.timeout_queue: list[TimeoutEvent] = [] # min-heap for expiration
self.now_ts: int = 0 # tracking of latest processed get timestamp
#TODO: you can optimize with doubly-linked list, but
# for now, we will sort within each get() call.
self.pending_process = deque()
def _update_event(
self,
event_id: int,
timestamp: int,
add_expiration: bool = True) -> None:
assert event_id in self.events, "Event not yet added into events store."
cur_event = self.events[event_id]
cur_event.last_updated_ts = timestamp
cu