Token Bucket Rate Limiter
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).
capacity = 2, rate = 1, times = [0, 0, 0, 1, 3][true, true, false, true, true]capacity = 5, rate = 1, times = [0,1,2,3,4]all truecapacity = 1, rate = 0.5, times = [0, 1, 2][true, false, true]- 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).
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 token_bucket(capacity, rate, times) → list of accept/reject booleans, using lazy fractional refill from a bucket that starts full.
- 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.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.