Design Hit Counter

Problem

Design a counter that records hits and reports how many hits occurred in the trailing 300-second window. Implement HitCounter with:

• hit(timestamp): record one hit at the given time (seconds).
• getHits(timestamp): return the number of hits with time in (timestamp - 300, timestamp], i.e. the last 300 seconds inclusive of timestamp.

Timestamps are non-decreasing across all calls, and several hits may share the same timestamp.

• Timestamps are positive and can grow into the billions of seconds.
• At most a few hundred calls to hit and getHits combined in the base version; the follow-ups relax this.

Examples

• hit(50), hit(51), hit(52), getHits(53) → 3; getHits(349) → 3 because 50, 51, 52 are all within (49, 349]; getHits(350) → 2 because the hit at time 50 has aged out.
• hit(9), hit(9), hit(9), getHits(9) → 3; multiple hits at one timestamp all count.
• getHits(10) on a fresh counter → 0.

Hints

1. A hit at time t is relevant only until t + 300. Once it is older than that, it will never be relevant again. What does that suggest about the order in which hits can be discarded?
2. Timestamps are non-decreasing, so the oldest hit is always at the front. Which structure supports pop-from-front and push-to-back in O(1)?
3. A queue of timestamps: on getHits, pop from the front while the front is <= timestamp - 300, then return the queue length. To bound memory under heavy traffic, store (timestamp, count) pairs or use a 300-slot circular buffer.