Rate Limiter, Constraint by Constraint

Start from brute force

The obvious stage-1 answer is a fixed-window counter: per key, store the current window number (now // window) and a count, reset the count when the number changes, and allow while count < limit. It is O(1) time per call and O(1) space per key, and it satisfies stage 1. It fails stage 2, because it counts calls since a reset boundary rather than in the last window seconds. With a limit of 3 per 60 seconds, calls at t = 59, 59, 59, 60, 60, 60 are all allowed, six calls in one second, while a sliding window allows three. No counter can fix that, which is why stage 2 forces the rewrite.

The approach

Keep, per key, the timestamps of allowed calls, and answer every check from them. The reference stores them in self.hits, a dict from key to list, so keys never share an allowance. Each allow(key, now) prunes first, with cutoff = now - self.window and ts[:] = [t for t in ts if t > cutoff], so the list holds exactly the calls in the half-open window (now − window, now].

Then come two independent checks, and both must pass: len(ts) >= self.limit denies on the window, and recent = sum(1 for t in ts if t > now - 1) denies when recent >= self.burst. Only then does it run ts.append(now), so a denied call leaves no trace. The invariant: after any call, ts holds at most limit timestamps, all allowed and all inside the window. Because now never decreases, ts stays sorted, so a deque pruned with popleft plus a binary search for the burst count avoids the scans.

Walk through an example

Replaying the reference’s own demo, Limiter(limit=3, window=60, burst=2) with key "a", gives [True, True, True, False, True]: the burst never trips, because t = 1 is a full second after the t = 0 calls.

Complexity

The reference costs O(limit) time per call, since pruning and the burst count scan a list that never exceeds limit entries, and O(keys × limit) space. A deque per key prunes in amortized O(1), and a binary search counts the burst in O(log limit). The fixed-window counter is O(1) time and space per key, but it answers the wrong question.

Edge cases to test

• The window is half-open: Limiter(1, 60, 9) allows calls at t = 0 and t = 60, because a call exactly window seconds old fails t > cutoff and is pruned; at t = 59.9 the second call would be denied.
• The burst window is half-open too: Limiter(10, 60, 1) with calls at t = 0, 0.5 and 1 returns [True, False, True].
• Denied calls leave no trace: Limiter(2, 60, 9) with calls at t = 0, 0, 30, 31, 32, 61 returns [True, True, False, False, False, True]. Recording the denials would refuse t = 61 as well.
• A limit or a burst of 0 denies everything: Limiter(0, 60, 9).allow("a", 0) and Limiter(3, 60, 0).allow("a", 0) are both False.
• The clock must not run backwards: after an allowed call at t = 100, calls at t = 10 and t = 50 still see that future timestamp inside the window, so Limiter(2, 60, 9) returns [True, True, False]. Use a monotonic clock.

Common mistakes

• Extending the fixed-window counter instead of switching to timestamps — a counter cannot answer "how many in the last 60 seconds" at an arbitrary moment.
• Recording the timestamp of a call that was denied, so a client hammering the endpoint permanently locks itself out.
• Pruning after the limit check rather than before it, which counts long-expired calls against the caller.
• Sharing one timestamp list across keys, so one noisy client throttles everyone.

Follow-ups an interviewer asks next

Memory is O(limit) per key. What if the limit is 10,000 per hour?

Approximate the sliding window with two counters: the current fixed window’s count plus the previous window’s count weighted by how much of it still overlaps, prev · (1 − elapsed/window) + curr. That is O(1) memory per key and close to exact when traffic is steady. A token bucket is the other O(1) option: two numbers enforce an average rate and a burst size.

How do you rate-limit across 20 servers?

Move the state to a shared store. In Redis, a sorted set per key can hold the timestamps: remove the expired ones, count, and add the new one only if allowed, all inside one Lua script so two servers cannot both take the last slot. Giving each server a local limit of limit/N is a cheaper approximation when the load balancer spreads traffic evenly.

What should the caller see when a call is denied?

An HTTP API returns 429 Too Many Requests, ideally with a Retry-After header, and the stored timestamps give its value exactly. For a window denial the oldest call expires at ts[0] + window; for a burst denial, the oldest call inside the last second expires one second after it was made. That tells a well-behaved client when to try again.

Should the limiter count calls or cost?

For LLM APIs, usually cost: providers limit tokens per minute as well as requests per minute. Store (timestamp, tokens) pairs and compare the sum inside the window with the budget. The structure is the same, only the quantity summed changes, and one large request can now be denied on its own.

Where this shows up

Every deployment against a rate-limited customer or vendor API needs this, usually in a hurry, usually after an agent loop discovered the limit in production on the customer’s shared quota. The burst rule in stage 4 is the one people skip and then need: an endpoint that allows 100 calls per minute but no more than 10 per second is extremely common, and a single-window limiter passes the first constraint while violating the second.

Reference solution

class Limiter:
    def __init__(self, limit, window, burst):
        self.limit = limit
        self.window = window
        self.burst = burst
        self.hits = {}                       # key -> list of allowed timestamps

    def allow(self, key, now):
        ts = self.hits.setdefault(key, [])
        # prune BEFORE checking, so expired calls never count against the caller
        cutoff = now - self.window
        ts[:] = [t for t in ts if t > cutoff]

        if len(ts) >= self.limit:
            return False
        recent = sum(1 for t in ts if t > now - 1)
        if recent >= self.burst:
            return False

        ts.append(now)                       # only allowed calls are recorded
        return True


L = Limiter(limit=3, window=60, burst=2)
print([L.allow("a", t) for t in (0, 0, 1, 30, 61)])
# -> [True, True, True, False, True]

class Limiter {
  limit: number; window: number; burst: number;
  hits: Map<string, number[]> = new Map();
  constructor(limit: number, window: number, burst: number) {
    this.limit = limit; this.window = window; this.burst = burst;
  }

  allow(key: string, now: number): boolean {
    let ts = this.hits.get(key);
    if (!ts) { ts = []; this.hits.set(key, ts); }

    // prune BEFORE checking
    const cutoff = now - this.window;
    const kept = ts.filter(function (t) { return t > cutoff; });
    ts.length = 0;
    for (const t of kept) ts.push(t);

    if (ts.length >= this.limit) return false;
    const recent = ts.filter(function (t) { return t > now - 1; }).length;
    if (recent >= this.burst) return false;

    ts.push(now);                    // only allowed calls are recorded
    return true;
  }
}

const L = new Limiter(3, 60, 2);
console.log([0, 0, 1, 30, 61].map(function (t) { return L.allow("a", t); }));
// -> [true, true, true, false, true]