p102 — Design Hit Counter — Hints

1. Memory must be bounded by the window, not by total hits. A naive list grows forever. A deque is bounded but only after getHits (or a cleanup step on hit) actually pops the old entries.

2. Two designs cover the spectrum. (a) deque of timestamps — hit append, getHits popleft-while-stale then len. (b) Circular array of 300 buckets indexed ts % 300, each (stored_ts, count) — hit is O(1), getHits is O(300).

3. Burst then quiet — the deque’s weak spot. 1M hits at ts=100, then getHits(401) must popleft all 1M in one call. P99 latency suffers. The bucket design caps work per call regardless of traffic shape.

4. Bucket staleness check is mandatory. bucket[ts % 300] may hold a hit from 300+ seconds ago. On a hit, if bucket[i].timestamp != ts, overwrite (don’t increment). On getHits, skip buckets where stored_ts <= ts - 300.

5. Test the boundary. getHits(300) should still see hit(1). getHits(301) should not. Off-by-one on < vs <= is the dominant bug.

If stuck: see solution.py.