SeniorDesignRareNot answered yet
Requests arrive in time order. Two operations interleave: a user generates an event, and a query asks how many users generated at least 1000 events in the last 5 minutes. Design a data structure handling both in amortized O(1) per request, with the constant independent of the 1000 threshold and the 5-minute window width. Describe the structures, why each operation is amortized O(1), and the memory pitfalls (the window emptying, and stale per-user entries never being cleaned up).
Keep a queue of windowed events, a map userId → count, and a running robotCount of users at or above the threshold. On each op evict events older than the window, add the new one, and adjust robotCount on a threshold crossing. Each event is enqueued and dequeued once, so amortized O(1).
- ✗Not handling the window emptying out at some moment
- ✗Never deleting users whose count drops to zero, leaking memory on a long stream
- ✗Letting the constant depend on the 1000 threshold or the 5-minute width
- →How do you keep memory bounded when only events (no queries) arrive for a long time?
- →Why does the running robotCount avoid rescanning all users per query?
Contents
Scenario
A stream of requests: a user clicks, or we want the count of "robots" (≥1000 events in 5 min).
Discussion
A sliding window of events + a map + a counter:
- A queue of
(timestamp, userId)holds the last 5 minutes of events. userId → countis each user's event count in the window.robotCountis how many users are currently at or above the threshold.
On each op: evict stale events (decrement count; if it drops below the threshold, decrement robotCount), add the new one (increment; if it crosses the threshold, increment robotCount).
Each event passes the queue once — amortized O(1). Remember to prune count == 0 entries.
Contents
