Design event timeout detector
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 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.