linkjobai a révisé ce gist 19 hours ago. Aller à la révision
1 file changed, 53 insertions
hitcounter.md(fichier créé)
| @@ -0,0 +1,53 @@ | |||
| 1 | + | # Design a Hit Counter (LeetCode 362) and How It Scales | |
| 2 | + | ||
| 3 | + | "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. | |
| 4 | + | ||
| 5 | + | ## Version 1: a queue of timestamps | |
| 6 | + | ||
| 7 | + | ```python | |
| 8 | + | from collections import deque | |
| 9 | + | ||
| 10 | + | class HitCounter: | |
| 11 | + | def __init__(self): self.q = deque() | |
| 12 | + | def hit(self, ts): self.q.append(ts) | |
| 13 | + | def get_hits(self, ts): | |
| 14 | + | while self.q and self.q[0] <= ts - 300: | |
| 15 | + | self.q.popleft() | |
| 16 | + | return len(self.q) | |
| 17 | + | ``` | |
| 18 | + | ||
| 19 | + | Simple, but memory grows with traffic: a million hits in five minutes means a million stored timestamps. | |
| 20 | + | ||
| 21 | + | ## Version 2: fixed buckets (constant memory) | |
| 22 | + | ||
| 23 | + | Keep 300 buckets, one per second, each storing `(timestamp, count)`. | |
| 24 | + | ||
| 25 | + | ```python | |
| 26 | + | class HitCounterBuckets: | |
| 27 | + | def __init__(self): | |
| 28 | + | self.times = [0] * 300 | |
| 29 | + | self.counts = [0] * 300 | |
| 30 | + | def hit(self, ts): | |
| 31 | + | i = ts - (ts // 300) * 300 # bucket index for this second | |
| 32 | + | if self.times[i] != ts: | |
| 33 | + | self.times[i], self.counts[i] = ts, 1 | |
| 34 | + | else: | |
| 35 | + | self.counts[i] += 1 | |
| 36 | + | def get_hits(self, ts): | |
| 37 | + | return sum(c for t, c in zip(self.times, self.counts) if ts - t < 300) | |
| 38 | + | ``` | |
| 39 | + | ||
| 40 | + | O(1) per hit, O(300) per query, and memory no longer depends on traffic. | |
| 41 | + | ||
| 42 | + | ## Follow-ups interviewers ask | |
| 43 | + | ||
| 44 | + | - **Concurrency:** many threads calling `hit()`. Use a lock per bucket or atomic counters. | |
| 45 | + | - **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. | |
| 46 | + | - **Different windows** (last hour, last day): use coarser buckets for longer windows instead of one giant array. | |
| 47 | + | ||
| 48 | + | ## How to present it | |
| 49 | + | ||
| 50 | + | Start with the queue, state its memory problem, then improve. Showing that progression is worth more than jumping straight to the optimal version. | |
| 51 | + | ||
| 52 | + | --- | |
| 53 | + | *Disclosure: I work on [Linkjob AI's coding interview assistant](https://www.linkjob.ai/coding-interview-copilot/).* | |
Plus récent
Plus ancien