Rate Limiter, Constraint by Constraint
A third incremental round, where stage two invalidates stage one outright: a fixed-window counter becomes a sliding window, then per-key, then gains a burst allowance. Tests whether you can say "that counter has to go" calmly and refactor, rather than patching around it.
The problem
Implement a class Limiter with allow(key, now) returning true or false, growing through four stated stages. (1) At most limit calls per window seconds. (2) The window must slide: at any moment, count only the calls in the last window seconds — not calls since a fixed reset point. (3) Limits are per key, so one caller cannot consume another’s allowance. (4) A burst rule applies as well: no more than burst calls in any 1 second. A call is only recorded when it is allowed; denied calls leave no trace.
limit 3/60s; 3 calls at t=0allowed, allowed, allowed…then a 4th at t=30denied…then one at t=61allowed- Only allowed calls are recorded — a denied call must not count against the caller later.
- The window slides continuously; there is no fixed reset boundary.
- Each key has its own independent allowance.
- Both the window limit and the 1-second burst limit must pass for a call to be allowed.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement Limiter(limit, window, burst) with allow(key, now) meeting all four stages at once.
- Stage 2 cannot be built from a counter. Keep the timestamps of allowed calls instead.
- Prune first, then check: drop everything older than
now - windowbefore you compare against the limit. - The burst rule is a second, shorter window over the same timestamps — count how many are within 1 second of now.
- Record the timestamp only on the allowed path, or a client that hammers a denied endpoint locks itself out forever.
Approach, complexity & discussion — open after you solve
The approach
Stage 2 is the one that forces the rewrite. A fixed window is a counter and a reset time; a sliding window needs the timestamps of recent calls, which means the counter you built in stage 1 has to be thrown away rather than extended. Interviewers watch for whether you say that out loud before you start typing.
The clean shape is one list of timestamps per key. On each call, drop everything older than now - window, then compare the remaining count with the limit. Per-key is a dictionary of those lists, and the burst allowance is a second, shorter window checked alongside the first — two independent constraints, both of which must pass.
Complexity
O(k) per call where k is the number of retained timestamps; O(keys × limit) space.
Common mistakes
- Extending the fixed-window counter instead of switching to timestamps — a counter cannot answer "how many in the last 60 seconds" at an arbitrary moment.
- Recording the timestamp of a call that was denied, so a client hammering the endpoint permanently locks itself out.
- Pruning after the limit check rather than before it, which counts long-expired calls against the caller.
- Sharing one timestamp list across keys, so one noisy client throttles everyone.
Where this shows up
Every deployment against a rate-limited customer or vendor API needs this, usually in a hurry, usually after an agent loop discovered the limit in production on the customer’s shared quota. The burst rule in stage 4 is the one people skip and then need: an endpoint that allows 100 calls per minute but no more than 10 per second is extremely common, and a single-window limiter passes the first constraint while violating the second.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.