← All challenges

Token bucket rate limiter

Medium

Refill tokens at a constant rate; allow bursts up to bucket size.

Token bucket rate limiter

Problem

Token buckets are the workhorse of API rate limiting — AWS API Gateway throttling and many client-side SDKs use them. A bucket holds up to capacity tokens, refills at a steady rate, and lets a request through only when a token is available, so clients get controlled bursts while the long-run average stays bounded. The key implementation tradeoff is eager versus lazy refill: a background timer that tops up every bucket continuously, or computing, only when a request arrives, how many tokens have accrued since the last one. This exercise uses lazy refill, which needs no timers and stays O(1) per call.

Implement a token-bucket rate limiter. Each key gets a bucket that holds up to capacity tokens. Tokens refill at a constant refillRate per refillMs milliseconds. On each call, if a token is available it is consumed and the request is allowed; otherwise it is rejected. This allows controlled bursts up to the bucket capacity.

Input

  • key: string — The identifier for the client or resource being rate-limited.
  • capacity: number — Maximum number of tokens the bucket can hold. Defaults to 10.
  • refillRate: number — Number of tokens added per refill interval. Defaults to 1.
  • refillMs: number — Refill interval in milliseconds. Defaults to 1000 (1 second).

Output

  • boolean — true if a token was available and consumed (request allowed); false if the bucket was empty (request rejected).

Examples

Example 1:

// capacity=5, refillRate=1, refillMs=1000 allow('alice', 5, 1, 1000); // true — tokens: 4 allow('alice', 5, 1, 1000); // true — tokens: 3 allow('alice', 5, 1, 1000); // true — tokens: 2 allow('alice', 5, 1, 1000); // true — tokens: 1 allow('alice', 5, 1, 1000); // true — tokens: 0 allow('alice', 5, 1, 1000); // false — bucket empty

Output: false

The bucket starts full at capacity 5. After 5 rapid calls the bucket is empty; additional calls are rejected until tokens refill.

Example 2:

// Different keys get independent buckets for (let i = 0; i < 5; i++) allow('a', 5, 1, 1000); allow('b', 5, 1, 1000); // true — b has its own bucket

Output: true

Each key has an independent bucket. Filling one does not affect others.

Constraints

  • Refill is computed lazily on each access, not by a background timer.
  • Tokens are capped at the bucket capacity and never exceed it.
  • Elapsed time since the last refill determines how many tokens to add.
  • The remainder of elapsed time is preserved for partial-refill accuracy.

Complexity

  • Time: O(1) per call
  • Space: O(K) where K is the number of distinct active keys

Starter

export function allow(key: string, capacity = 10, refillRate = 1, refillMs = 1000): boolean {
    // Refill the bucket from elapsed time at refillRate per refillMs,
    // cap at capacity, then allow one request when tokens remain.
  }

API available to your solution

The platform provides a deterministic millisecond clock; use it for all time math instead of reading the system clock. The tests pin the clock to specific values, so your results are reproducible.

long long nowMs();   // current time in milliseconds

Time.nowMs();        // static long nowMs() — current time in milliseconds

func nowMs() int64   // current time in milliseconds

now_ms() -> int      // current time in milliseconds

Date.now()           // fixed to deterministic values by the test runner

Don't declare the clock yourself — it is supplied in every language.

Hints

Answer