Sliding Window Counters and Rate Limiting

What's being tested

These problems test designing and implementing sliding window counters for real-time per-key aggregation and rate limiting: correct time-window semantics, efficient per-key state, memory/CPU tradeoffs, and concurrency. Interviewers want to see clear assumptions about clock skew, event ordering, and cleanup/eviction strategies.

Patterns & templates

• Time-bucket counter — keep an array of B buckets (width = window/B); O(1) update, O(B) memory per key; rotate buckets on time tick.

• Exact timestamp window — store recent event timestamps in a deque; pop old entries, count remaining; O(k) memory (k = events in window).

• Token bucket — use tokens and refill rate to allow bursts while enforcing long-term rate; constant-time checks and updates per request.

• Leaky bucket — model as a drain-rate queue for smoothing; implement with last-timestamp and accumulated state, O(1) state per key.

• Per-key sharding + ConcurrentHashMap — store state per IP, shard by hash to avoid global locks; consider lock striping for atomic updates.

• Eviction/TTL — run background sweep or use TTL heap to remove idle keys; avoid unbounded growth when keys ≫ active window.

• Clock handling — use monotonic now() for deltas; convert timestamps to bucket indices deterministically to handle skew.

Common pitfalls

Pitfall: Using a fixed-window counter causes boundary burstiness — two windows can be abused to double rate across the boundary.

Pitfall: Forgetting eviction leads to memory leak when attackers create many unique keys; add TTL or LRU cleanup.

Pitfall: Doing per-request global locks kills throughput; use per-key atomic updates or lock striping instead.

Practice these

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