11. Sliding-Window Rate Limiter

Problem

Fin fields a very high volume of API calls from customers embedding it into their own support surfaces. Each customer's API key needs to be protected from being hammered: implement a per-key sliding-window-log rate limiter that allows at most max_requests requests within any rolling window_seconds window, per key.

Unlike most problems in this set, this one is stateful: you're designing a class, RateLimiter, that holds state across many calls to allow(), rather than a single pure function. Each call to allow(key, timestamp) must decide, based only on that key's own request history, whether to admit or reject the request, and update its state accordingly.

Source: src/11_sliding_window_rate_limiter.py

class RateLimiter:
    def __init__(self, max_requests: int, window_seconds: float): ...
    def allow(self, key: str, timestamp: float) -> bool: ...

>>> rl = RateLimiter(max_requests=2, window_seconds=10)
>>> rl.allow("k", 0)
True
>>> rl.allow("k", 1)
True
>>> rl.allow("k", 2)
False
>>> rl.allow("k", 11)
True

Step-by-Step Approach

1. Store, per key, a log of the timestamps of requests that have been admitted so far — a dict[str, deque[float]] works well because you need cheap eviction from the front and cheap appends at the back.
2. On each allow(key, timestamp) call, first compute the window cutoff: cutoff = timestamp - window_seconds. Any logged timestamp <= cutoff is now outside the rolling window and can be discarded.
3. Evict stale entries from the front of that key's deque while the oldest entry is <= cutoff. Because timestamps are appended in increasing order, the deque is always sorted, so you only ever need to look at the front.
4. After eviction, check the remaining size: if it's still less than max_requests, the request is allowed — append the new timestamp to the log and return True.
5. Otherwise the key is at capacity within the window — return False without recording the request (a rejected request should not count against future admission decisions).
6. Use dict.setdefault(key, deque()) so a brand-new key gets an empty log lazily, without a separate initialization step.

The key insight is that "sliding window" here doesn't require re-scanning history on every call: because each key's timestamps are appended in non-decreasing order, eviction is a simple two-pointer-style sweep from the front of a deque, so each timestamp is pushed and popped at most once, giving amortized O(1) work per call (plus whatever eviction happens that call).

Reference solution

from collections import deque


class RateLimiter:
    def __init__(self, max_requests: int, window_seconds: float):
        # deque: O(1) append/pop at both ends, unlike list.pop(0)'s O(n)
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        # built-in generic subscript, no typing import needed
        self._log: dict[str, deque[float]] = {}

    def allow(self, key: str, timestamp: float) -> bool:
        # lazily creates a new key's log in one line
        log = self._log.setdefault(key, deque())
        cutoff = timestamp - self.window_seconds
        # deque stays sorted; only the O(1) front needs checking
        while log and log[0] <= cutoff:
            log.popleft()
        if len(log) < self.max_requests:
            log.append(timestamp)
            return True
        return False

Key Functions & Tricks

• collections.deque — O(1) append/pop at both ends, vs. O(n) for list.pop(0).
• dict.setdefault(key, deque()) — lazily initializes a new key's log in one expression.
• log[0] — O(1) peek at the deque's front; indexing elsewhere in a deque is O(n).
• while log and log[0] <= cutoff: log.popleft() — evicts stale entries; sorted-by-append-order means only the front ever needs checking.
• dict[str, deque[float]] — built-in generic subscript syntax (3.9+), no typing import needed.

How to Recognize This Pattern