Design Hit Counter
Medium · Design · Design · Queue · Sliding Window
Problem
Count how many hits arrived in the past five minutes (300 seconds).
- hit(timestamp) — record one hit at that second
- getHits(timestamp) — how many hits landed in the window (timestamp - 300, timestamp]
Timestamps arrive in non-decreasing order, and several hits may share a second.
Your tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301) Output: 3, then 4, then 3
At t=301 the window is (1, 301], so the hit at second 1 has just fallen out.
Constraints
- 1 <= timestamp <= 2 * 10^9
- Timestamps are non-decreasing across calls
- Up to 300 calls per second
- Consider what changes if hits arrive far more often
Approaches
- Queue of timestamps, evicting the expired — time amortised O(1) hit, space O(hits in window)
Follow-up
What if hits arrive at a million per second, or timestamps come as fractions of a second? A queue grows with traffic; per-second buckets do not, but they need an integer second to index by.
Related problems
Start free on Cariara · Coding problems · System design studio
