Design Hit Counter
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Design a counter with hit(timestamp) and getHits(timestamp) returning the hits in the past 300 seconds. Timestamps only go up.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1In which order do hits expire?
- Hint 2Which data structure removes from the front and adds to the back?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A shop's door counter that only remembers the last 5 minutes. Every time someone enters you write the time on a list. When the owner asks "how many in the last 5 minutes?", you first cross off entries from the top of the list that are older than 5 minutes, then count what remains.
- The obvious way
Keep all hits and count those in range each time: O(hits) per query.
- The key insight
Keep a queue of hit times. hit appends the time. getHits removes from the front every time that is 300 or more seconds old (now - time >= 300), then returns the queue length.
- The algorithm
- hit: append timestamp.
- getHits: pop the front while it is 300 or more seconds old.
- Return the number left.
Watch it run
Examplehit 1, 2, 3; getHits(4); hit 300; getHits(300); getHits(301)
Hits at 1, 2, 3. At time 4 nothing is old: 3 hits.
getHits(4) = 3
Where people slip
- The window is the past 300 seconds, so a hit exactly 300 seconds old is already out.
- For very heavy traffic keep one counter per second (a ring of 300 buckets) instead.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
class HitCounter:
def __init__(self):
self.hit_times = deque() # oldest first
def hit(self, timestamp):
self.hit_times.append(timestamp)
def getHits(self, timestamp):
while self.hit_times and timestamp - self.hit_times[0] >= 300:
self.hit_times.popleft() # cross off entries older than 5 minutes
return len(self.hit_times)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.