0

Sliding-window request rate limiter

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Sliding-window request rate limiter

Companies: Microsoft, Stripe, Waymo, Uber

Difficulty: Medium

Problem statement

Implement a rate limiter that accepts at most limit requests in any window of ttl milliseconds.

class RateLimiter:
    def __init__(self, limit: int, ttl: int) -> None: ...
    def allow(self, timestamp: int) -> bool: ...
  • allow(timestamp) is called once per incoming request. timestamp is in milliseconds, and calls arrive in non-decreasing time order.
  • Return True and record the request if accepting it keeps the limiter within limit accepted requests in the window. Otherwise return False.
  • A request accepted at time s counts against requests up to, but not including, time s + ttl. At s + ttl it no longer counts.
  • Rejected requests do not use up capacity.
  • The limit must hold for every window of length ttl, not just for fixed buckets such as [0, ttl), [ttl, 2*ttl).

Constraints

  • 0 <= limit <= 10^5
  • 1 <= ttl <= 10^9
  • 0 <= timestamp <= 10^12
  • Up to 10^6 calls to allow

Example 1

RateLimiter(limit=2, ttl=500)
allow(10)   -> True
allow(20)   -> True
allow(400)  -> False   # 10 and 20 are still in the window
allow(510)  -> True    # 10 expired at exactly 510
allow(515)  -> False   # 20 and 510 are in the window

Example 2

RateLimiter(limit=1, ttl=60)
allow(0)  -> True
allow(30) -> False
allow(45) -> False   # rejections do not extend the wait
allow(60) -> True

Aim for amortized O(1) time per call and O(limit) memory. Be ready to extend the limiter to many clients, each identified by a key.

Approach

Clarify first. The limiter is built with limit (the most requests it may accept) and ttl (the window length in milliseconds). Each call to allow(t) is one request at time t. Pin down four things before coding:

  • Window edges. An accepted request at time s counts against every request with t < s + ttl. At t = s + ttl it has expired. So the window for a request at t is (t - ttl, t].
  • Rejected requests do not count. Only accepted requests use up capacity. Otherwise a client that keeps retrying would lock itself out forever.
  • Time never goes backwards. Timestamps are non-decreasing. Ask what to do if they are not (see Follow-ups).
  • Sliding window, not fixed buckets. "At most limit in any ttl ms" is a sliding window. A fixed-window counter (reset every ttl ms) is simpler but lets through up to 2 * limit requests across a bucket boundary. Say this out loud; it is the most common thing interviewers check.

Brute force. Keep every accepted timestamp in a list. On each request, count the ones with s > t - ttl. Accept if the count is below limit. This is correct, but each call is O(total accepted) and memory grows without bound.

Optimal: a queue of accepted timestamps. Accepted timestamps arrive in order, so the expired ones are always at the front. Keep them in a deque:

  1. Pop from the front while front <= t - ttl.
  2. If fewer than limit remain, append t and return True. Otherwise return False.

Invariant. After step 1, the deque holds exactly the accepted requests inside (t - ttl, t], oldest first, and its length is never more than limit. Each timestamp is pushed once and popped once, so the cost is amortized O(1) per call and memory is O(limit).

Even tighter: only the oldest of the last limit matters. Store the last limit accepted timestamps in a ring buffer. A new request is allowed if the buffer is not full, or if the oldest slot has expired. When allowed, overwrite that slot. This is worst-case O(1) with no popping loop. It is a good thing to mention; the deque is easier to explain and extend, so the code below uses it and shows the ring buffer as an alternative.

Token bucket for comparison. Refill limit / ttl tokens per ms up to a cap of limit; spend one per request. It is O(1) time and space, allows smooth bursts, and is what most production limiters use. It does not give the exact "at most limit in any ttl window" guarantee, so it answers a slightly different question.

Code

from __future__ import annotations

import time
from collections import deque


class RateLimiter:
    """Sliding-window log: at most `limit` accepted requests in any `ttl` ms."""

    def __init__(self, limit: int, ttl: int) -> None:
        if limit < 0 or ttl <= 0:
            raise ValueError("limit must be >= 0 and ttl must be > 0")
        self.limit = limit
        self.ttl = ttl
        self._accepted: deque[int] = deque()  # accepted timestamps, oldest first
        self._last = -1 << 62

    def allow(self, timestamp: int | None = None) -> bool:
        t = self._now() if timestamp is None else timestamp
        if t < self._last:
            raise ValueError("timestamps must be non-decreasing")
        self._last = t
        cutoff = t - self.ttl
        while self._accepted and self._accepted[0] <= cutoff:
            self._accepted.popleft()
        if len(self._accepted) < self.limit:
            self._accepted.append(t)
            return True
        return False

    @staticmethod
    def _now() -> int:
        return time.monotonic_ns() // 1_000_000


class RingRateLimiter:
    """Same rule, worst-case O(1): keep only the last `limit` accepted times."""

    def __init__(self, limit: int, ttl: int) -> None:
        if limit < 0 or ttl <= 0:
            raise ValueError("limit must be >= 0 and ttl must be > 0")
        self.limit = limit
        self.ttl = ttl
        self._slots: list[int | None] = [None] * limit
        self._head = 0  # index of the oldest accepted timestamp

    def allow(self, timestamp: int) -> bool:
        if self.limit == 0:
            return False
        oldest = self._slots[self._head]
        if oldest is not None and oldest > timestamp - self.ttl:
            return False
        self._slots[self._head] = timestamp
        self._head = (self._head + 1) % self.limit
        return True


class KeyedRateLimiter:
    """Follow-up: one independent window per client key."""

    def __init__(self, limit: int, ttl: int) -> None:
        self.limit = limit
        self.ttl = ttl
        self._by_key: dict[str, RateLimiter] = {}

    def allow(self, key: str, timestamp: int) -> bool:
        limiter = self._by_key.get(key)
        if limiter is None:
            limiter = self._by_key[key] = RateLimiter(self.limit, self.ttl)
        return limiter.allow(timestamp)

Complexity

  • RateLimiter.allow: amortized O(1) time (each timestamp is appended once and popped once), worst case O(limit) for a single call that expires many entries. Space O(limit).
  • RingRateLimiter.allow: worst-case O(1) time. Space O(limit), allocated up front.
  • KeyedRateLimiter.allow: amortized O(1) per call plus a hash lookup. Space O(K * limit) for K active keys, unless idle keys are evicted.
  • Brute force for comparison: O(n) per call and O(n) space for n accepted requests so far.

Test cases

  • limit = 3, ttl = 1000; requests at 0, 100, 200, 300 → True, True, True, False.
  • Same limiter, then 1000 → True (the request at 0 expired exactly at 1000), then 1050 → False (100 and 200 are still live), then 1100 → True.
  • Boundary: limit = 1, ttl = 10; requests at 0, 9, 10 → True, False, True.
  • Rejections do not count: limit = 1, ttl = 10; requests at 0, 5, 5, 5, 10 → True, False, False, False, True.
  • Same timestamp burst: limit = 2, ttl = 50; three requests at 7 → True, True, False.
  • limit = 0 → every request is False.
  • Long idle gap: limit = 2, ttl = 100; requests at 0, 1, then 10_000 → True, True, True; the deque is emptied in one call.
  • Per key: limit = 1, ttl = 100; ("a", 0) → True, ("b", 0) → True, ("a", 50) → False.
  • Out-of-order timestamp (5 after 10) → raises ValueError in this version.
  • The deque and ring-buffer versions return the same sequence on any non-decreasing input (good randomized check).

Follow-ups

  1. Many clients (per user, per API key, per route). Wrap the limiter in a map from key to limiter, as in KeyedRateLimiter. Then deal with memory: evict a key once its newest accepted timestamp is older than ttl (its window is empty, so a fresh limiter behaves the same). An LRU or a periodic sweep works. Different tiers get different (limit, ttl) values from a config lookup.
  2. Memory per key must be O(1). The log stores up to limit timestamps, which is too much when limit is 10,000 and there are millions of keys. Switch to a sliding-window counter: keep counts for the current and previous fixed buckets and estimate prev * (1 - elapsed / ttl) + curr. It is approximate but constant space. Or use a token bucket (tokens, last_refill) and state that it bounds the average rate and burst size, not the exact count per window.
  3. Thread safety. Several threads calling allow race on "check length, then append". Guard the whole call with a lock, or use one lock per key (striped locks) so hot keys do not block each other. Read the clock inside the lock so timestamps stay ordered.
  4. Distributed limiter across many servers. Local state lets each server accept limit, so N servers accept N * limit. Move state to a shared store such as Redis: a sorted set per key with ZREMRANGEBYSCORE, ZCARD, ZADD inside one Lua script so the check and the insert are atomic; or a token bucket in a hash updated by a script. Discuss the trade-off: one network round trip per request, the store as a single point of failure (fail open or fail closed?), and clock skew (use the store's clock, not each server's).
  5. Tell the caller when to retry. Return a result with allowed, remaining = limit - len(window) and retry_after = front + ttl - t when rejected. These map to the X-RateLimit-Remaining and Retry-After headers and come almost free from the deque, because the front element is exactly the next one to expire. Also: weighted requests (allow(t, cost)), which work naturally with a token bucket and need a running sum with the log.

Interviewer expectations

Mid-level (L4)

  • Asks whether rejected requests count and what happens at exactly t = s + ttl, then writes a correct sliding-window limiter.
  • Uses a deque (or explains why a list scan is slow) and gets amortized O(1) per call.
  • Tests the boundary, the same-timestamp burst and the idle gap without prompting.

Senior (L5)

  • Names the fixed-window boundary problem and explains why the log or a token bucket avoids it.
  • Extends to many keys cleanly and addresses memory: eviction of idle keys and the O(limit) cost per key.
  • Handles concurrency with a lock and says where the clock is read; can produce retry_after and remaining.

Staff (L6+)

  • Compares log, sliding counter and token bucket on accuracy, memory and burst behavior, and picks one for a stated product need.
  • Designs the distributed version: atomic check-and-insert in a shared store, fail-open versus fail-closed, clock source, hot keys, and local pre-limiting to cut round trips.
  • Thinks about operations: per-tier configuration, observability of rejections, and how limits change without restarting servers.

Sign in to comment, vote or remix.