DSA problem
Design Hit Counter
Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Each function accepts a timestamp parameter (in seconds granularity), and you may assume calls are being made in chronological order (i.e., timestamps are monotonically non-decreasing). Several hits may arrive at roughly the same time.
Implement HitCounter with two methods: HitCounter() initializes the object. hit(timestamp) records a hit that happened at timestamp. getHits(timestamp) returns the number of hits in the past 300 seconds (from timestamp - 299 to timestamp inclusive — i.e., hits with stored timestamp strictly greater than timestamp - 300).
The straightforward approach uses a queue of timestamps. On hit, enqueue the timestamp. On getHits, pop from the front while the front is at or before timestamp - 300, then return the queue size. Each timestamp is enqueued once and dequeued once across the lifetime of the structure, giving amortized O(1) per call. The downside is unbounded memory in the worst case where many hits arrive in the same window.
A constant-memory alternative is the 300-bucket array trick. Maintain two parallel arrays of length 300 — one for timestamps, one for hit counts — indexed by timestamp % 300. On hit, if the slot's stored timestamp matches, increment its count; otherwise overwrite the slot with the new timestamp and a count of 1. On getHits, sum the counts of all slots whose stored timestamp is within the last 300 seconds. This gives O(300) per call but is bounded in space — a real production trade-off.
Examples
["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"]
[[],[1],[2],[3],[4],[300],[300],[301]][null,null,null,null,3,null,4,3]["HitCounter","hit","getHits","getHits"]
[[],[1],[1],[300]][null,null,1,1]["HitCounter","getHits"]
[[],[5]][null,0]Constraints
- 1 <= timestamp <= 2 * 10^9
- All the calls are being made to the system in chronological order (timestamp is monotonically non-decreasing).
- At most 300 calls will be made to hit and getHits.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.