Implement a Thread-Safe Event Tracker Over a Sliding Time Window

Implement an in-memory event system that records events as they happen and answers questions about the events that fall inside a fixed time window ending now, for example the last `W` seconds. Many threads record events and query at the same time, so the class must be thread-safe. The exact interface was not given. Assume this one unless the interviewer specifies another: ```text EventWindow(window_seconds) record(event) -> None # the event happened now count() -> int # number of events recorded within the last window_seconds recent() -> list # those events, oldest first ``` ```hint Old events never come back Once an event has fallen out of the window, no later query can need it again. Think about what that implies for where in your storage you add and where you remove. ``` ```hint One step or two Consider which pieces of each operation must happen together while another thread is recording or querying, including the moment the current time is read. ``` ### Constraints and Clarifications - `window_seconds` is positive and fixed at construction. - Unless the interviewer says otherwise, an event that happened at time `t` is inside the window at time `now` while `now - window_seconds < t` and `t <= now`. - Calls arrive concurrently from many threads. - Memory should be proportional to the events inside the window, not to every event ever recorded. ### Clarifying Questions - Do callers pass a timestamp with each event, or does the class read a clock itself? If callers pass timestamps, can they arrive out of order? - Which queries are needed: the count only, the events themselves, or counts per event type? - What is the peak event rate? At that rate, is a count with one-second granularity acceptable, or must it be exact? - Is the window boundary inclusive or exclusive? ### What a Strong Answer Covers - A time-ordered structure with amortized constant-time insertion and eviction - Precise window boundary semantics, with eviction on queries as well as on inserts - What the lock protects, how long it is held, and where the time is read - Clock choice, and out-of-order timestamps if callers supply them - Memory under bursts, and a bucketed alternative when exact per-event storage is too costly - Testing with an injectable clock and a concurrency stress test ### Follow-up Questions - The system receives millions of events per second, and only the count matters. How do you bound memory, and what precision do you give up? - Queries vastly outnumber records. How would you reduce lock contention? - Callers supply their own timestamps, and events can arrive a few seconds out of order. What changes? - The same counts are needed across many servers. How would you extend the design?