Design a distributed rate limiter that caps how many requests a client (API key / IP) can make per time window.
How to approach it
Every system has one signature hard problem the interviewer wants to watch you reason about. Identify it, lay out two or three approaches with their tradeoffs, and recommend one with a clear justification. Depth on the core problem beats breadth across components.
Algorithm choice
Bound request rate accurately without spiky boundary effects or heavy memory.
Approaches
| Approach | Tradeoff |
|---|---|
| Fixed window counter | simplest, but allows 2× burst at the window boundary |
| Sliding window log | accurate, but stores a timestamp per request (memory heavy) |
| Token bucket | smooth, allows controlled bursts, O(1) state per client |
Tip
Recommended — Token bucket (or sliding-window counter) for O(1) memory and smooth limiting without boundary bursts.