Katkat
Back

Count Events in a Trailing 15-Minute Window with a Fixed-Size Ring Buffer

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement an event counter that returns how many events occurred in the trailing 15 minutes, using a fixed-size ring buffer of per-second buckets so memory stays bounded at any event rate. It tests circular buffers, stale-slot detection, window boundaries, late events and thread safety.

Implement an event counter for a monitoring system. It supports two operations:

  • record(timestamp): an event happened at timestamp, an integer number of seconds.
  • count(now): return how many recorded events happened in the 15 minutes ending at now, that is, with now - 900 < timestamp <= now.

Events can arrive at a very high rate, and memory must stay bounded no matter how many events are recorded. The interviewer expects a ring buffer (a fixed-size circular array).

Clarifying Questions

  • Are timestamps non-decreasing, or can events arrive late, out of order? How late?
  • Is one-second resolution enough, or are timestamps finer-grained?
  • Can count be called with a time earlier than the latest recorded event?
  • Should the window boundary include events exactly 900 seconds old?
  • Is the counter shared by many threads?
  • Is there one counter, or one per event type or key?

Hints

Hint 1

Trade exactness in time for bounded memory: Consider what you need to remember about all the events that happened within the same second, and how many such seconds can matter at once.

Hint 2

Reusing a slot safely: When a slot in the circular array is reused for a new second, make sure its old contents cannot be mistaken for the new second's events.

Follow-up questions

  • How would you support counts for many different keys, such as per user or per endpoint, without huge memory use?
  • How would you count events across many servers and combine the results?
  • The window is now 30 days at one-second resolution. What changes?
  • How would you also report the 99th-percentile latency of the events in the window?