Number of Recent Calls
Easy · Stack & Strings · Design · Queue · Data Stream
Problem
Design a counter of requests made within a sliding time window.
Implement RecentCounter:
- RecentCounter() starts with no requests.
- ping(t) records a new request at time t (in milliseconds) and returns how many requests happened in the inclusive range [t - 3000, t], counting this one.
Every call to ping uses a strictly larger t than the call before it.
The input is the list of operations and the list of their arguments, and the output lists what each call returns (null for the constructor).
Examples
Input: ops = ["RecentCounter","ping","ping","ping","ping"], args = [[],[10],[2000],[3010],[5500]] Output: [None, 1, 2, 3, 2]
At t = 5500 the window is [2500, 5500], which holds the requests at 3010 and 5500.
Input: ops = ["RecentCounter","ping","ping"], args = [[],[1],[3002]] Output: [None, 1, 1]
The window for 3002 is [2, 3002], so the request at 1 no longer counts.
Input: ops = ["RecentCounter","ping","ping","ping"], args = [[],[100],[3100],[3101]] Output: [None, 1, 2, 2]
At 3100 the window [100, 3100] still holds 100. At 3101 it starts at 101, so 100 is gone.
Constraints
- 1 <= t <= 10^9
- Calls to ping use strictly increasing values of t
- At most 10^4 calls are made to ping
Approaches
- Store every call, recount each time — time O(n) per call, space O(n)
Follow-up
What if the times were not guaranteed to increase (requests logged out of order)? A queue no longer works; keep the times in a sorted structure and count the range [t - 3000, t] with two binary searches, or use a Fenwick tree over compressed times.
Related problems
Start free on Cariara · Coding problems · System design studio
