📘 Problem Statement
Design a hit counter that counts the number of hits received in the past 5 minutes (i.e., 300 seconds). Implement two methods:
hit(timestamp: int): Records a hit at the given timestamp.getHits(timestamp: int): Returns the number of hits in the past 300 seconds (i.e., timestamps in range (timestamp - 299) to timestamp).
Assume that all timestamps are provided in chronological order (in seconds).
🧠 Key Insight
This is a classic sliding window problem:
- Only keep track of timestamps within the last 300 seconds.
- Older timestamps can be discarded during
getHits.
We can use a queue or deque to efficiently manage this window.
🐍 Python Code
python
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
def getHits(self, timestamp: int) -> int:
while self.hits and self.hits[0] <= timestamp - 300:
self.hits.popleft()
return len(self.hits)
🔍 Step-by-Step Explanation
1. Use a Deque to Track Hit Timestamps
python
self.hits = deque()
- Each entry is a hit’s timestamp.
- Efficiently append to the end and remove from the front.
2. hit() Method
python
self.hits.append(timestamp)
- Simply record the hit timestamp.
3. getHits() Method
python
while self.hits and self.hits[0] <= timestamp - 300:
self.hits.popleft()
- Remove hits that are older than 300 seconds from the current time.
- Return the length of the deque which represents hits in the past 5 minutes.
💡 Example
python
hitCounter = HitCounter()
hitCounter.hit(1)
hitCounter.hit(2)
hitCounter.hit(300)
hitCounter.getHits(300) # returns 3
hitCounter.getHits(301) # returns 2 (hit at timestamp 1 is out of 5-minute window)
⏱️ Time & Space Complexity
OperationTimeSpacehit()O(1)O(n)getHits()O(n)O(n)
Where n is the number of hits in the last 300 seconds.
🔁 Bonus: Optimized for High Traffic
If hit frequency is very high (thousands per second), we can compress hits by storing counts per timestamp in a hashmap or array. Want me to show that version too?
🧵 Final Thoughts
This problem is a beautiful blend of:
- System design thinking (tracking hits over time).
- Sliding window technique using a deque.
Perfect warm-up for real-world problems like rate limiting, API throttling, and monitoring dashboards.