Number of Recent Calls
Easy· queue
Problem
Build a counter with a ping(t) method that records a request at time t (in milliseconds) and returns how many requests happened in the inclusive window [t - 3000, t]. Calls arrive with strictly increasing t.
Examples
Input: ping(1), ping(100), ping(3001), ping(3002)
Output: [1,2,3,3]
At t = 3002 the window is [2, 3002], so the request at time 1 has dropped out.
Constraints
- • 1 <= t <= 10^9
- • t is strictly increasing across calls
- • At most 10^4 calls
Hints & approach
Hint 1
Old requests only ever leave from the oldest end.
Hint 2
A queue holding the timestamps fits naturally.
Approachtry the hints first
Keep a queue of timestamps. On ping(t), enqueue t, then dequeue from the front while the front is older than t - 3000. The queue size is the answer. Since timestamps increase, each one is enqueued and dequeued once, giving amortised O(1) per call.
Time O(1) amortised · Space O(w), w = requests in the window