Implement a Rate Limiter
On this page
Problem statement
Build an in-process rate limiter.
allow(client_id, timestamp)returns true if the request may go through and false if it must be rejected. Part 1: each client may make at mostNrequests in any window ofWseconds (a sliding window, not fixed buckets). Part 2: support several rules at once, for example "at most 2 per second and at most 3 per 10 seconds"; a request passes only if every rule allows it. Part 3: switch to a token bucket that allows short bursts up to a capacity and refills at a steady rate. Timestamps arrive in non-decreasing order.
This is the coding version of a classic system design topic: instead of drawing boxes, you write the class that would sit inside one server. It is usually run in stages, and each stage adds a requirement to the code you already have. There is no single LeetCode original; the closest warm-ups are LeetCode 359 Logger Rate Limiter and LeetCode 362 Design Hit Counter.
Example

SlidingWindowLimiter(limit=3, window=10)
allow("alice", 0) -> true
allow("alice", 1) -> true
allow("alice", 2) -> true
allow("alice", 5) -> false # 0, 1, 2 are all in (-5, 5]
allow("alice", 10) -> true # 0 has left: window (0, 10] holds 1, 2
allow("alice", 10) -> false # 1, 2, 10 fill the window
allow("alice", 12) -> true # window (2, 12] holds only 10
allow("bob", 5) -> true # every client has its own quota
MultiRuleLimiter([(2 per 1 s), (3 per 10 s)])
t = 0, 0, 0, 1, 2, 10, 11
-> T, T, F, T, F, T, T
# t=0 third call: per-second rule full. t=2: per-10-second rule full (0, 0, 1).
Constraints (assumed)
- Up to 10⁵ clients and 10⁶ calls;
Nup to 10⁴ per window. - Timestamps are integers (seconds or milliseconds) and never go backwards.
- Single-threaded for parts 1 to 3; concurrency is a follow-up.
What this question tests
- Turning a fuzzy requirement ("N per window") into an exact window definition and coding it without off-by-one errors.
- Choosing a data structure that makes each call O(1) amortized and keeps memory bounded.
- Extending working code cleanly when the interviewer adds rules, bursts and threads.
Questions to ask first
- Sliding or fixed window? Fixed buckets (00:00–00:10, 00:10–00:20) are simpler but let a burst of 2N through at a boundary. (Here: sliding.)
- Is the window
(now − W, now]or[now − W, now]? In other words, does a request exactlyWseconds old still count? (Here: no.) - Do rejected requests count toward the limit? (Here: no. Only accepted requests use up quota.)
- Is it exact, or is an approximation fine? An approximation (sliding window counter) uses O(1) memory per client.
- Single process or shared across servers? Shared state across servers moves the problem into system design (Redis, a gateway). (Here: one process.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.