How do you approach Token-Bucket Rate Limiter?

Track two pieces of state: current token count (a float) and the timestamp of the last update.

What is the optimal solution to Token-Bucket Rate Limiter?

Lazy Refill. Don't run a background timer adding tokens - instead, compute the refill on demand when a request arrives. State per bucket: tokens (float) and lastRefill (timestamp). Why this is the standard answer over leaky-bucket / sliding-window: Token bucket allows bursts up to capacity (good for legit users that occasionally spike).

What is the time complexity of Token-Bucket Rate Limiter?

Time complexity: O(1) per allow. Space complexity: O(1) per bucket.

What are common mistakes on Token-Bucket Rate Limiter?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Token-Bucket Rate Limiter

HardSystem Design

Description

Design a token-bucket rate limiter: a structure that allows up to capacity requests at once and refills tokens at a steady rate of refillRate tokens per second.

The bucket starts full at time 0 (i.e. capacity tokens). Each allow(timestamp) call:

Refills the bucket based on the elapsed seconds since the last refill: tokens = min(capacity, tokens + (timestamp - lastRefill) * refillRate). Fractional tokens are allowed.
If tokens >= 1, deduct 1 and return true (allow).
Else return false (reject).

Timestamps are non-decreasing. refillRate and capacity may be floats.

For the auto-grader: implement tokenBucketOps(capacity, refillRate, requests) where each request is a timestamp (in seconds). Return an array of booleans matching the result of each allow().

Example 1

Input: capacity = 3, refillRate = 1, requests = [0,0,0,0,2]

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

Explanation: At t=0 the bucket is full (3 tokens). The first three calls each consume one token (bucket → 2, 1, 0). The fourth call at t=0 finds 0 tokens → reject. At t=2, two seconds have passed so 2 tokens refilled (capped to capacity); one is consumed → allow.

Example 2

Input: capacity = 2, refillRate = 0.5, requests = [0,0,1,2,4]

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

Explanation: Capacity 2 is exhausted by the first two calls. At t=1, only 0.5 tokens have refilled (< 1) → reject. At t=2, total refilled = 1.0 → still need to wait (we already rejected at t=1 - the rejection consumes nothing, so at t=2 we have 1.0 token; integer? 1.0 >= 1 → allow!). Re-walk: at t=2, tokens = 0 + 2*0.5 = 1.0 → allow, bucket → 0. At t=4, tokens = 0 + 2*0.5 = 1.0 → allow.

Constraints

- 0 < capacity <= 10^6 - 0 < refillRate <= 10^6 - 0 <= requests.length <= 10^5 - Timestamps are non-decreasing non-negative numbers up to 10^9.

Token-Bucket Rate Limiter: approach, complexity and pitfalls

A hard design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Track two pieces of state: current token count (a float) and the timestamp of the last update.
On each request, lazily compute how many tokens have refilled since lastRefill; cap at capacity.
Compare to >= 1 (use a tiny epsilon if you want to defend against float drift, but the test cases are chosen to avoid pathological floats).

The optimal approach

Show the approach: Lazy Refill

Don't run a background timer adding tokens - instead, compute the refill *on demand* when a request arrives. State per bucket: `tokens` (float) and `lastRefill` (timestamp).

```

allow(t):

elapsed = t - lastRefill

tokens = min(capacity, tokens + elapsed * refillRate)

lastRefill = t

if tokens >= 1:

tokens -= 1

return True

return False

```

Why this is the standard answer over leaky-bucket / sliding-window:

- Token bucket allows bursts up to `capacity` (good for legit users that occasionally spike).

- Sliding-window-counter is more accurate but uses more memory per key.

- Leaky-bucket smooths but doesn't allow bursts.

Distributed extension (interview follow-up): put state in Redis with atomic Lua script (`GET tokens, lastRefill → compute → SET`) or use a shared distributed token store like Stripe's [twitter-style rate limiter](https://stripe.com/blog/rate-limiters). The single-machine algorithm above is the basis.

Time: O(1) per allow
Space: O(1) per bucket

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.