Sliding Window Counters And QPS

What's being tested

These problems test time-windowed aggregation: maintaining counts, rates, or averages over the last $W$ seconds without scanning all historical events. Interviewers look for clean data structure tradeoffs, correct expiry logic, and complexity analysis under monotonic timestamps, timestamp collisions, and high event volume.

Patterns & templates

• Circular bucket array — store (timestamp, count) per second; hit(t) and get(t) are O(1)/O(W), space O(W).

• Lazy bucket reset — when t % W is reused, reset bucket if stored timestamp differs; prevents stale counts from leaking.

• Deque of timestamps/events — append on hit, pop expired while front <= now - W; amortized O(1), space proportional to recent hits.

• Aggregated deque buckets — store (bucketStart, count) for sparse streams or range queries; merge same bucket, evict old buckets.

• Running total optimization — maintain total alongside buckets/deque so getCount() is O(1) after evicting expired entries.

• QPS formula — average QPS is events_in_window / window_seconds; clarify whether denominator is fixed W or elapsed warm-up time.

• Per-key counters — use Map<Key, Counter> for KV-store variants; evict inactive keys if memory bounds matter.

Common pitfalls

Pitfall: Forgetting timestamp collisions in modulo buckets; t % W alone is not enough without storing the bucket’s real timestamp.

Pitfall: Off-by-one expiry errors; define whether the valid interval is (now - W, now] or [now - W, now].

Pitfall: Claiming O(1) queries while summing all W buckets each time; either admit O(W) or maintain a running total.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.