# Design a Hit Counter (LeetCode 362) and How It Scales "Design a hit counter that returns the number of hits in the past 5 minutes" starts as a data-structure question and often turns into a mini system design discussion. ## Version 1: a queue of timestamps ```python from collections import deque class HitCounter: def __init__(self): self.q = deque() def hit(self, ts): self.q.append(ts) def get_hits(self, ts): while self.q and self.q[0] <= ts - 300: self.q.popleft() return len(self.q) ``` Simple, but memory grows with traffic: a million hits in five minutes means a million stored timestamps. ## Version 2: fixed buckets (constant memory) Keep 300 buckets, one per second, each storing `(timestamp, count)`. ```python class HitCounterBuckets: def __init__(self): self.times = [0] * 300 self.counts = [0] * 300 def hit(self, ts): i = ts - (ts // 300) * 300 # bucket index for this second if self.times[i] != ts: self.times[i], self.counts[i] = ts, 1 else: self.counts[i] += 1 def get_hits(self, ts): return sum(c for t, c in zip(self.times, self.counts) if ts - t < 300) ``` O(1) per hit, O(300) per query, and memory no longer depends on traffic. ## Follow-ups interviewers ask - **Concurrency:** many threads calling `hit()`. Use a lock per bucket or atomic counters. - **Many servers:** each server keeps local buckets and a central store (Redis) aggregates them, or you stream hits into Kafka and count with a windowed stream processor. - **Different windows** (last hour, last day): use coarser buckets for longer windows instead of one giant array. ## How to present it Start with the queue, state its memory problem, then improve. Showing that progression is worth more than jumping straight to the optimal version. --- *Disclosure: I work on [Linkjob AI's coding interview assistant](https://www.linkjob.ai/coding-interview-copilot/).*