Design Hit Counter
Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time. Implement the `HitCounter` class: - `HitCounter()` Initializes the object of the hit counter system. - `void hit(int timestamp)` Records a hit that happened at `timestamp` (in seconds). Several hits may happen at the same `timestamp`. - `int getHits(int timestamp)` Returns the number of hits in the past 5 minutes from `timestamp` (i.e., the past 300 seconds).
Examples
Constraints
1 <= timestamp <= 2 * 10^9All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).At most 300 calls will be made to hit and getHits.
Optimal Solution
Approach
Since we only care about hits in the last 300 seconds, we don't need to store all hits indefinitely. We can keep track of hits using a fixed-size array or a queue. **Approach using a queue (or double-ended queue)** 1. **Queue**: Store the timestamps of the hits in a queue. 2. **Hit Operation**: Simply enqueue the incoming timestamp. Since timestamps are monotonically increasing, the queue is naturally sorted. 3. **GetHits Operation**: Before returning the size of the queue, we remove all elements from the front of the queue that are outside the 300-second window (i.e., `timestamp - front_timestamp >= 300`). The remaining elements in the queue are all within the valid window, so we just return the queue's size. **Optimized Approach (Buckets)** If the number of hits per second is very large, storing each timestamp individually uses too much space. Instead, we can use two arrays of size 300: - `times`: Stores the timestamp mapped to a specific bucket (`timestamp % 300`). - `hits`: Stores the count of hits for that timestamp. When recording a hit, we find the bucket `idx = timestamp % 300`. If `times[idx]` doesn't match the current `timestamp`, it means it's from an older 5-minute window, so we update `times[idx] = timestamp` and reset `hits[idx] = 1`. If it matches, we simply increment `hits[idx]`. When getting hits, we iterate over all 300 buckets and sum the `hits` where `timestamp - times[i] < 300`. This approach strictly uses O(300) = O(1) space and time.