Design Hit Counter
Asked at Apple, Databricks, Uber
Problem
Design a hit counter which counts the number of hits received in the past 5 minutes. Implement the HitCounter class: HitCounter() initializes the hit counter, hit(timestamp) records a hit at the given timestamp (guaranteed to be strictly increasing), and getHits(timestamp) returns the number of hits in the past 5 minutes (at timestamp).
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Naive approach: store all timestamps in a list. On getHits, count how many timestamps fall within [timestamp - 299, timestamp]. This is O(n) per getHits call. Works but is slow if there are many hits.
Queue-based approach: store timestamps in a queue. On hit, enqueue the timestamp. On getHits, dequeue all timestamps older than 5 minutes, then return the queue size. Each timestamp is enqueued and dequeued at most once, so amortized O(1) per operation.
Circular buffer approach: since the window is fixed at 300 seconds, use an array of size 300. Each slot stores the count for that second modulo 300. On hit, increment the count at timestamp % 300. On getHits, sum all slots where the timestamp falls within the 5-minute window. This is O(300) = O(1) per getHits.
Visual walkthrough of queue approach for timestamps [1, 1, 1, 2, 2, 2, 301, 301, 302]:
hit(1): queue=[1]
hit(1): queue=[1,1]
hit(1): queue=[1,1,1]
hit(2): queue=[1,1,1,2]
hit(2): queue=[1,1,1,2,2]
hit(2): queue=[1,1,1,2,2,2]
hit(301): queue=[1,1,1,2,2,2,301]
hit(301): queue=[1,1,1,2,2,2,301,301]
hit(302): queue=[1,1,1,2,2,2,301,301,302]
getHits(303): pop while front <= 303-300=3. Pop 1,1,1,2,2,2 (all <= 3). queue=[301,301,302]. Return 3.
Queue approach is simpler and more intuitive. The circular buffer is more space-efficient but requires careful handling of stale data. For interviews, the queue approach is usually sufficient.
Time: O(1) amortized for both hit and getHits (queue approach). Space: O(hits) for queue, O(300) for circular buffer.
Optimal Approach
Queue approach:
hit(timestamp): append timestamp to thequeue.getHits(timestamp): while the front of thequeueis <=timestamp - 300, pop it. Return thequeuesize.
Walkthrough with timestamps [1, 1, 1, 2, 2, 2, 301, 301, 302]:
hit(1): queue=[1]hit(1): queue=[1,1]hit(1): queue=[1,1,1]hit(2): queue=[1,1,1,2]hit(2): queue=[1,1,1,2,2]hit(2): queue=[1,1,1,2,2,2]hit(301): queue=[1,1,1,2,2,2,301]hit(301): queue=[1,1,1,2,2,2,301,301]hit(302): queue=[1,1,1,2,2,2,301,301,302]getHits(303): pop while front <= 303-300=3. Pop 1,1,1,2,2,2 (all <= 3). queue=[301,301,302]. Return 3.
Time: O(1) amortized. Space: O(hits).
What Trips People Up in Real Interviews
Using a list and scanning all elements on every getHits call. This is O(n) per call. The queue approach is O(1) amortized because each element is removed at most once.
Confusing the 5-minute window. The window is [timestamp - 299, timestamp], not [timestamp - 300, timestamp). If a hit occurred at timestamp 1 and you query at timestamp 301, it should be excluded (301 - 300 = 1, and 1 <= 1 means it is at the boundary). Use <= timestamp - 300 to pop.
Not handling the case where timestamps are not strictly increasing. The problem guarantees strictly increasing timestamps, so you don't need to handle out-of-order arrivals. If the guarantee is removed, you need a sorted data structure.
Trying to use a deque with binary search for getHits. The queue with lazy deletion is simpler and equally efficient. Binary search adds unnecessary complexity.
Forgetting that getHits must not modify the queue permanently. The lazy deletion in the queue approach does remove old elements, which is correct because they will never be needed again (timestamps are strictly increasing).
Solution Code
from collections import deque
class HitCounter:
def __init__(self):
self.q = deque()
def hit(self, timestamp):
self.q.append(timestamp)
def getHits(self, timestamp):
while self.q and self.q[0] <= timestamp - 300:
self.q.popleft()
return len(self.q)Frequently Asked Questions
What is the Design Hit Counter problem?
Design a hit counter which counts the number of hits received in the past 5 minutes. Implement the `HitCounter` class: `HitCounter()` initializes the hit counter, `hit(timestamp)` records a hit at the given timestamp (guaranteed to be strictly increasing), and `getHits(timestamp)` returns the number of hits in the past 5 minutes (at timestamp).
How do you solve Design Hit Counter?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Hit Counter?
Design Hit Counter is asked at Apple, Databricks, Uber. It is a medium difficulty problem.
What are common mistakes on Design Hit Counter?
- Using a `list` and scanning all elements on every `getHits` call. This is `O(n)` per call. The `queue` approach is `O(1)` amortized because each element is removed at most once.
- Confusing the 5-minute window. The window is [timestamp - 299, timestamp], not [timestamp - 300, timestamp). If a hit occurred at timestamp 1 and you query at timestamp 301, it should be excluded (301 - 300 = 1, and `1 <= 1` means it is at the boundary). Use `<= timestamp - 300` to pop.
- Not handling the case where timestamps are not strictly increasing. The problem guarantees strictly increasing timestamps, so you don't need to handle out-of-order arrivals. If the guarantee is removed, you need a sorted data structure.
- Trying to use a `deque` with binary search for `getHits`. The `queue` with lazy deletion is simpler and equally efficient. Binary search adds unnecessary complexity.
- Forgetting that `getHits` must not modify the `queue` permanently. The lazy deletion in the `queue` approach does remove old elements, which is correct because they will never be needed again (timestamps are strictly increasing).