Count Events in a Trailing 15-Minute Window with a Fixed-Size Ring Buffer
Company: OpenAI
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Onsite
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).
```hint 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 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.
```
### 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?
### What a Strong Answer Covers
- A fixed-size circular buffer with a reliable way to tell current buckets from stale ones
- Correct window boundaries and correct handling of gaps longer than the window
- Time and space complexity of both operations, and how queries avoid rescanning every bucket
- Explicit policies for late events and past queries
- Thread safety, and the trade-off between bucket resolution and accuracy
### 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?
Overview: 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.