Live Coding Interview Prep

Course Content

Live Coding Interview Prep

7 sections · 50 lessons

Add rate limiting and throttling to API calls.

Bucket level before each request (capacity 3, 1 per second)3.02.01.00.00.001234burst ofthree at t=0wait 1.0 swait 1.0 s
The bucket allows a short burst, then enforces the average rate exactly — with only two numbers of state.

What you need to know

LLM providers limit you on several axes at once: requests per minute (RPM), input and output tokens per minute (TPM), and sometimes concurrent requests. Going over returns 429 errors. Client-side throttling means slowing yourself down before the provider has to reject you.

The token bucket algorithm (the "tokens" here are permission units, not LLM tokens):

  • The bucket starts full, with capacity units.
  • It refills continuously at rate units per second, never above capacity.
  • A request needing n units takes them if available; otherwise it waits until the refill covers them.

It stores only two numbers — the current level and the time of the last update — so it is O(1). A sliding-window log, which stores a timestamp for every request, is exact but O(requests in the window).

Python
import threading, timefrom collections.abc import Callableclass TokenBucket:    """Allow bursts up to `capacity`; refill at `rate` units per second."""    def __init__(self, rate: float, capacity: float,                 clock: Callable[[], float] = time.monotonic,                 sleep: Callable[[float], None] = time.sleep) -> None:        if rate <= 0 or capacity <= 0:            raise ValueError("rate and capacity must be positive")        self.rate, self.capacity, self.clock, self.sleep = float(rate), float(capacity), clock, sleep        self.level, self.updated = float(capacity), clock()        self.lock = threading.Lock()    def acquire(self, amount: float = 1, timeout: float | None = None) -> bool:        """Block until `amount` units are available. False if that would exceed timeout."""        if amount > self.capacity:            raise ValueError("request is larger than the bucket; it can never be served")        deadline = None if timeout is None else self.clock() + timeout        while True:            with self.lock:                now = self.clock()                self.level = min(self.capacity, self.level + (now - self.updated) * self.rate)                self.updated = now                if self.level >= amount:                    self.level -= amount                    return True                wait = (amount - self.level) / self.rate            if deadline is not None and self.clock() + wait > deadline:                return False            self.sleep(wait)class ThrottledClient:    """Requests/min, tokens/min and concurrency limits in front of a model call."""    def __init__(self, call_fn: Callable[[str], str], rpm: int = 50, tpm: int = 40_000,                 concurrency: int = 8) -> None:        self.call_fn = call_fn        self.requests = TokenBucket(rate=rpm / 60, capacity=rpm)        self.tokens = TokenBucket(rate=tpm / 60, capacity=tpm)        self.slots = threading.Semaphore(concurrency)    def call(self, prompt: str, estimated_tokens: int) -> str:        self.requests.acquire(1)        self.tokens.acquire(estimated_tokens)        with self.slots:            return self.call_fn(prompt)

The tricky parts:

  • Refill is computed lazily from elapsed time inside acquire; no background thread is needed.
  • The sleep happens outside the lock, so other threads can still take units that are available for smaller requests.
  • amount > capacity raises. Without the check, a request for 50,000 tokens against a 40,000 bucket waits forever.
  • Estimate tokens as input plus max_tokens, because output counts toward TPM. After the call, compare with the real usage and adjust future estimates.

Complexity: each acquire does O(1) work per loop iteration and usually returns after at most one sleep. State is two floats and a lock: O(1) space.

A real-life example

A bucket of capacity 3 refilling at 1 unit per second, with a fake clock so the waits are exact:

Python
now = [0.0]waits: list[float] = []def fake_sleep(s):    waits.append(round(s, 3))    now[0] += sbucket = TokenBucket(rate=1, capacity=3, clock=lambda: now[0], sleep=fake_sleep)for i in range(5):    bucket.acquire(1)    print(f"request {i + 1} sent at t={now[0]:.1f}s")print(waits)# request 1 sent at t=0.0s# request 2 sent at t=0.0s# request 3 sent at t=0.0s# request 4 sent at t=1.0s# request 5 sent at t=2.0s# [1.0, 1.0]
requestlevel beforeactionlevel after
13.0take 12.0
22.0take 11.0
31.0take 10.0
40.0wait (1 − 0) / 1 = 1.0 s, refill to 1.0, take 10.0
50.0wait 1.0 s, take 10.0

The first three go out as a burst; after that the bucket enforces exactly one per second.

A company summarising 10,000 customer reviews overnight runs every call through a throttled client like this, set to about 90% of its account limits, and sees almost no 429s.

Follow-up questions to expect

  • "You run 10 worker processes — does this still work?" — No; each has its own bucket, so together they send 10 times the limit. Move the bucket into Redis with an atomic Lua script, or give each worker a tenth of the limit.
  • "How do you rate-limit your own users?" — The same bucket, keyed by user or API key and stored in Redis, returning 429 with Retry-After instead of sleeping.
  • "Is this fair between threads?" — Not strictly; a thread can be overtaken repeatedly. Put requests in a FIFO queue in front of the bucket if order matters.