Katkat
Back

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

AppleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a thread-safe in-memory event tracker that records events and reports the events and their count within a sliding time window. Tests time-ordered storage with amortized eviction, window boundary semantics, lock scope and clock choice, out-of-order events, and memory under high event rates.

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:

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

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?

Hints

Hint 1

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 2

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.

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?