Implement a Rate Limiter

Free with account Updated Nov 19, 2026 · 8 min read
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 most N requests in any window of W seconds (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

    With 3 requests per 10 seconds, the request at t = 5 and the second one at t = 10 are rejected; by t = 12 the requests at 1 and 2 have left the window.
    With 3 requests per 10 seconds, the request at t = 5 and the second one at t = 10 are rejected; by t = 12 the requests at 1 and 2 have left the window.
    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; N up 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

    1. 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.)
    2. Is the window (now − W, now] or [now − W, now]? In other words, does a request exactly W seconds old still count? (Here: no.)
    3. Do rejected requests count toward the limit? (Here: no. Only accepted requests use up quota.)
    4. Is it exact, or is an approximation fine? An approximation (sliding window counter) uses O(1) memory per client.
    5. Single process or shared across servers? Shared state across servers moves the problem into system design (Redis, a gateway). (Here: one process.)