CODING CHALLENGE · N°22

Token Bucket Rate Limiter

Medium SystemsRate LimitingDistributed Systems

The algorithm inside most production rate limiters — and it never runs a timer. A bucket refills lazily: on each request, credit the time elapsed since the last one, cap at capacity, spend one token or reject. Two numbers of state per client.

The problem

Implement a token bucket as a pure replay: given capacity (max tokens), rate (tokens refilled per second), and times — a non-decreasing list of request timestamps in seconds — return a list of booleans, one per request: accepted or rejected. The bucket starts full. Refill lazily: at each request, add (t − t_last) · rate tokens (capped at capacity, where t_last is the previous request time), then accept if at least 1 token remains (spend it) or reject (spend nothing).

EXAMPLE 1

Input capacity = 2, rate = 1, times = [0, 0, 0, 1, 3]

Output [true, true, false, true, true]

burst of 2 passes, third rejected, refill revives later requests

EXAMPLE 2

Input capacity = 5, rate = 1, times = [0,1,2,3,4]

Output all true

request rate ≤ refill rate never rejects

EXAMPLE 3

Input capacity = 1, rate = 0.5, times = [0, 1, 2]

Output [true, false, true]

fractional refill: 1 token back after 2 seconds

CONSTRAINTS

The bucket starts full (tokens = capacity).
Refill is lazy and fractional — no timers, no rounding.
Rejected requests spend nothing (tokens unchanged apart from the refill).
times is non-decreasing; equal timestamps are legal (a burst).

SOLVE IT YOURSELF

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.

YOUR TASK

Implement token_bucket(capacity, rate, times) → list of accept/reject booleans, using lazy fractional refill from a bucket that starts full.

HINTS — 4 IDEAS

Keep two state variables: current tokens and the previous request timestamp.
On each request: tokens = min(capacity, tokens + (t − t_last) · rate), then t_last = t.
Accept iff tokens ≥ 1; subtract 1 only on accept.
This is exactly what production limiters store per key in Redis — two numbers, no timer.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

A bucket holds up to capacity tokens and refills at rate tokens per second. On each request, lazily add the tokens accrued since the last check (capped at capacity), then if at least one token is available, spend it and allow the request; otherwise reject. Computing the refill on access avoids any background timer.

Complexity

Time O(1) per request — a subtraction, a min, and a comparison.

Common mistakes

Refilling with a background loop instead of lazily on access — needless work and clock coupling.
Not capping accrued tokens at capacity, which lets a long-idle client burst past the limit.
Floating-point drift when accumulating fractional tokens over many calls.

Where this shows up

Token bucket is the standard rate-limiting algorithm: capacity sets the allowed burst, refill rate sets the sustained limit. It is used in API gateways, network traffic shaping, and anywhere you need to smooth bursty load while still permitting short spikes.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems Caching & Performance