DSA problem
Number of Recent Calls
You are asked to design a RecentCounter class that counts the number of recent requests made within a sliding time window of the past 3000 milliseconds. The class supports a single method ping(t) which records a new request that arrives at time t (in milliseconds) and then returns how many requests have happened in the inclusive range [t - 3000, t].
A key property of the input is that calls to ping are made in strictly increasing order of t. This means once a timestamp slips outside the 3000 ms window, it can never become relevant again to any future query — it stays expired forever. That monotonic property is exactly what a queue is built to exploit: items only enter at the back and leave from the front, never the middle.
A naive solution would store every timestamp in a list and scan from the beginning on each call. That works but degrades to O(n) per query in the worst case. The optimal design keeps the timestamps inside a queue and, on every ping(t), evicts from the front while the front timestamp is older than t - 3000. Each timestamp is pushed and popped at most once across the entire lifetime of the counter, giving amortized O(1) work per call.
After eviction, the queue contains exactly the timestamps within the window, so the answer is simply the queue's current size. This problem is a clean introduction to using a queue for a sliding-window count and to the technique of amortized analysis where a per-call worst case can still average to constant time.
Examples
["RecentCounter","ping","ping","ping","ping"]
[[],[1],[100],[3001],[3002]][null,1,2,3,3]["RecentCounter","ping"]
[[],[5000]][null,1]["RecentCounter","ping","ping"]
[[],[1],[10000]][null,1,1]Constraints
- 1 <= t <= 10^9
- Each test case will call ping with strictly increasing values of t.
- At most 10^4 calls will be made to ping.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.