Compute rolling five-minute averages per key from an unbounded event stream.

How to answer

“Unbounded” is the word to answer. The stream never ends, so the interviewer is checking what your memory grows with. Say the bound you are aiming for before you write a class: memory grows with the number of active keys, never with the event rate.

1. Pin the semantics. Ask whether the five minutes are measured in event time or arrival time, and say your choice: event time, a half-open window ending at the newest timestamp seen so far, the watermark. Say that the watermark is shared by every key, and what that costs. Ask whether averages are read on demand or pushed, and how late events can arrive.
2. Pick the storage by its memory cost. A deque of raw events per key is exact, but it grows with the rate. One-second buckets, each a sum and a count, cost min(seconds with events, 300) per key whatever the rate, and the only error is at the trailing edge, where a whole second leaves at once. Keep only the seconds that have events, so a device that reports once a minute doesn’t pay for 300 empty slots. Say that trade out loud and let the interviewer pick.
3. Keep a running sum and count. A read costs only the expiry since the last read, which never exceeds the live buckets, and never grows with the event rate. Eviction happens lazily as the watermark moves.
4. Handle disorder by where the event lands. A late event still inside the window goes into its bucket. One older than the window cannot change any average you will report, so drop it and count it; a silent drop is the bug the customer finds first.
5. Forget idle keys. A key whose window is empty costs as much as a missing one, so delete it.
6. Test against a brute-force oracle on random, partly shuffled input, including keys that go quiet for longer than the window.

The trap is evicting by time.time(). Arrival time turns a backlog into a spike, and the same events replayed give different answers.