302. Design Hit Counter
A web service wants a live counter of recent traffic. Build a class HitCounter with two methods:
hit(timestamp)— record one hit at the given second. Several hits may land on the same second (callhitonce per hit).get_hits(timestamp)— return how many hits occurred in the past 5 minutes: the 300-second window[timestamp − 299, timestamp], both ends included.
All calls — hits and queries alike — arrive in chronological order (timestamps never decrease). Timestamps are in seconds.
Example 1:
Input: hit(1) · hit(2) · hit(3) · get_hits(4) · hit(300) · get_hits(300) · get_hits(301)
Output: 3, 4, 3
Explanation: At t=4 the window [−295, 4] holds the hits at 1, 2, 3. At t=300 the window [1, 300] holds all four hits. At t=301 the window [2, 301] drops the hit at t=1, leaving 3.
Example 2:
Input: hit(5) · hit(5) · hit(5) · get_hits(5) · get_hits(304) · get_hits(305)
Output: 3, 3, 0
Explanation: Three separate hits share second 5, so get_hits(5) is 3. The window [5, 304] still contains second 5, but [6, 305] does not — the burst expires all at once.
Constraints:
- 1 ≤ q ≤ 3 * 10⁴ operations
- 1 ≤ timestamp ≤ 10⁹, and timestamps are non-decreasing across all calls
- A hit at second s counts for every query at time t with s ≥ t − 299 and s ≤ t
Hints:
Hits arrive in time order, and old hits only ever *stop* mattering — they never come back. That one-way expiry is the signature of a queue: new hits enter at the back, stale hits leave from the front.
On each query, pop from the front while the front timestamp is <= timestamp − 300; the queue length is then the answer. Each hit is pushed once and popped at most once, so everything is amortized O(1).
The queue can still hold millions of entries after a burst. To cap memory at exactly 300 slots, keep circular arrays `times[300]` and `counts[300]` indexed by `timestamp % 300`, resetting a slot when a new second claims it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: hit(1) · hit(2) · hit(3) · get_hits(4) · hit(300) · get_hits(300) · get_hits(301)
Expected output: 3, 4, 3