Design Hit Counter
Understanding the Problem
We need to build a class that tracks hits over time and can report how many hits occurred in the last 300 seconds from any given moment. Timestamps are monotonically increasing, so a hit never arrives from the past, but old hits must expire as time moves forward.
A web server's request counter has the same shape: how many requests arrived in the last 5 minutes? At any point, hits older than 300 seconds are irrelevant and must not be counted.
The task is to maintain a sliding window of exactly 300 seconds. Any hit with timestamp <= current_timestamp - 300 is stale and excluded. This is a sliding window over a data stream, where the window is defined by time rather than by element count.
Key Constraints:
1 <= timestamp <= 2 * 10^9→ Timestamps can be in the billions, so an array indexed directly by timestamp is not an option.- Calls are in chronological order → We never need to insert hits out of order. Older hits are always older than everything added after them, so a queue keeps expired hits at the front.
- At most
300calls tohitandgetHits→ The operation count is small, so even an O(n) scan per call passes. The standard follow-up, handling a high hit volume, is what motivates the queue and circular buffer approaches.
Approach 1: Brute Force (Store All Timestamps)
Intuition
Store every hit's timestamp in a list. When getHits is called, iterate through the entire list and count how many timestamps fall within the last 300 seconds.
The cost shows up in two places. The list keeps timestamps forever, even ones from hours ago that can never be counted again, and every getHits call rescans that entire history.
Algorithm
- Initialize an empty list to store all hit timestamps.
- On
hit(timestamp), append the timestamp to the list. - On
getHits(timestamp), iterate through the entire list and count timestamps wheretimestamp - t < 300. - Return the count.
Example Walkthrough
Code
- Time Complexity: O(1) for
hit, O(n) forgetHits. EverygetHitscall scans the entire list, including timestamps that expired long ago. - Space Complexity: O(n) where n is the total number of hits. We never discard old timestamps, so the list grows without bound.
Every query scans hits that expired long ago and can never be counted again. The next approach discards a timestamp the moment it expires, so the structure only ever holds the current window.
Approach 2: Queue (Remove Expired Hits)
Intuition
Instead of keeping every timestamp forever, use a queue and remove expired timestamps. Since timestamps arrive in chronological order, the oldest timestamps are always at the front of the queue, and an expired timestamp can never sit behind a valid one. When we need the count, we first remove everything older than 300 seconds from the front, and then the queue's size is the answer.
Once a timestamp expires, it stays expired, because every later query uses a larger timestamp. Removing it from the queue is permanent and safe.
A single getHits call might remove many timestamps, but each timestamp enters the queue once and leaves at most once. Across any sequence of operations, the total removal work is bounded by the total number of hits, which gives O(1) amortized time per operation.
Algorithm
- Initialize an empty queue.
- On
hit(timestamp), add the timestamp to the back of the queue. - On
getHits(timestamp), while the front of the queue is older than 300 seconds (i.e.,front <= timestamp - 300), remove it. Return the size of the queue.
Example Walkthrough
Code
- Time Complexity: O(1) amortized for both
hitandgetHits. Each element is added and removed at most once across all calls. - Space Complexity: O(n) where n is the number of hits in the current 300-second window. We actively discard expired timestamps.
The queue stores one entry per hit. At one hit per second that is at most 300 entries, but at thousands of hits per second the queue holds thousands of entries for the same 300-second window. The follow-up question targets this case, and the fix is to aggregate hits by second in a fixed-size structure.
Approach 3: Circular Buffer (Fixed Space)
Intuition
The 300-second window means we only ever care about at most 300 distinct seconds. We use a fixed-size array of 300 slots, where each slot represents one second. Each slot stores the timestamp of the last hit that mapped to it and the count of hits at that timestamp.
We map timestamps to slots using modulo: slot = timestamp % 300. When a hit arrives, we check if the slot's stored timestamp matches the current one. If it does, we increment the count. If not, this slot held data from a previous cycle (at least 300 seconds ago), so we reset it with the new timestamp and a count of 1.
For getHits, we scan all 300 slots and sum the counts where the stored timestamp is within the last 300 seconds. Space stays fixed at 300 slots no matter how many hits arrive.
Two timestamps map to the same slot only if they differ by a multiple of 300, so they are at least 300 seconds apart. The older one is outside the window by definition, which means a new hit only ever overwrites an expired entry, never a countable one.
The staleness check in getHits handles slots that have not been written recently. If slot 50 was last written at timestamp 50 and we call getHits(1000), the check 1000 - 50 < 300 fails, so that slot's count is excluded. Slots never written at all hold timestamp 0 and count 0; even when the check passes for them (any query with timestamp < 300), they add zero to the total.
Algorithm
- Initialize two arrays of size 300:
timestamps[300]andcounts[300], both zeroed. - On
hit(timestamp), computeindex = timestamp % 300. Iftimestamps[index] == timestamp, incrementcounts[index]. Otherwise, reset:timestamps[index] = timestamp,counts[index] = 1. - On
getHits(timestamp), iterate all 300 slots. For each slot wheretimestamp - timestamps[i] < 300, addcounts[i]to the total. Return the total.
Example Walkthrough
Code
- Time Complexity: O(1) for
hit, O(300) = O(1) forgetHits.hitdoes a single modulo and comparison.getHitsalways scans exactly 300 slots regardless of hit count. - Space Complexity: O(300) = O(1). Two fixed arrays of 300 integers each. Memory footprint never grows.