Design Hit Counter
Problem
Design a hit counter that supports hit(t) and getHits(t) returning the number of hits in the last 5 minutes (300s).
hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)[3, 4, 3]from collections import deque
class HitCounter:
def __init__(self):
self.q = deque()
def hit(self, t):
self.q.append(t)
def getHits(self, t):
while self.q and self.q[0] <= t - 300:
self.q.popleft()
return len(self.q)class HitCounter {
constructor() { this.q = []; }
hit(t) { this.q.push(t); }
getHits(t) {
while (this.q.length && this.q[0] <= t - 300) this.q.shift();
return this.q.length;
}
}class HitCounter {
Deque q = new ArrayDeque<>();
public void hit(int t) { q.add(t); }
public int getHits(int t) {
while (!q.isEmpty() && q.peek() <= t - 300) q.poll();
return q.size();
}
} class HitCounter {
deque q;
public:
void hit(int t) { q.push_back(t); }
int getHits(int t) {
while (!q.empty() && q.front() <= t - 300) q.pop_front();
return q.size();
}
}; Explanation
We want to know how many hits happened in the last 5 minutes (300 seconds). The neat trick is to keep all hit timestamps in a queue in the order they arrive, then throw away the old ones only when someone asks.
Because timestamps only ever grow, the oldest hit always sits at the front of the queue. That makes pruning easy: the front is always the first to expire.
hit(t) just appends t to the back of the queue. getHits(t) pops from the front while the front timestamp is <= t - 300 (too old), then returns the queue's size — that size is exactly the number of hits still inside the 300-second window.
Each timestamp is added once and removed once, so even though there is a loop, the work averages out to O(1) per call (amortized).
Example: hits at 1, 2, 3 then getHits(4) keeps all three (none older than 4 - 300), returning 3. Add hit(300); getHits(300) returns 4. At getHits(301), the cutoff is 1, so the hit at time 1 is dropped, leaving 3.