Practice Problems

Rate limiters show up more often in system design interviews and production code than in classic coding tests. The four problems below are small twists on the algorithms from the previous chapters. Try each one yourself before reading the solution.

Problem 1. Log audit: the first request over the limit

You have the request timestamps from an API server's log, as integer seconds in ascending order. The rule is "no window-second span may contain more than limit requests". Return the timestamp of the first request that breaks the rule, or None if the rule always held.

Approach: this is a sliding window log. Drop timestamps that fell out of the window, append the current one, and the first time the count exceeds limit is the answer. Every timestamp enters and leaves once, so the whole pass is O(n).

from collections import deque


def first_violation(times: list[int], limit: int, window: int) -> int | None:
    recent: deque[int] = deque()
    for t in times:
        while recent and recent[0] <= t - window:
            recent.popleft()
        recent.append(t)
        if len(recent) > limit:
            return t
    return None


print(first_violation([1, 2, 11, 12, 13, 14], limit=3, window=10))  # 14
print(first_violation([1, 5, 11, 15], limit=2, window=10))          # None

At time 14 the span (4, 14] holds 11, 12, 13 and 14, four requests, which is the first time the limit of 3 is exceeded.

Problem 2. Weighted requests and Retry-After

A token bucket charges 5 tokens for a search and 1 token for a read. Given a list of (time, cost) requests, return None for each accepted request and, for each rejected one, the whole number of seconds to put in Retry-After. The bucket starts full at time 0.

Approach: refill lazily, then compare against the cost. The time to earn the missing tokens is (cost - tokens) / rate; the header takes whole seconds, so round up. Rounding down makes the client retry too early and get rejected again. A request that costs more than the capacity can never pass, so handle it separately.

import math


def simulate(requests: list[tuple[float, float]], rate: float,
             capacity: float) -> list[int | None]:
    tokens, last = capacity, 0.0
    out: list[int | None] = []
    for t, cost in requests:
        if cost > capacity:
            raise ValueError(f"cost {cost} can never fit in capacity {capacity}")
        tokens = min(capacity, tokens + (t - last) * rate)
        last = t
        if tokens >= cost:
            tokens -= cost
            out.append(None)
        else:
            out.append(math.ceil((cost - tokens) / rate))
    return out


print(simulate([(0, 5), (0, 5), (1, 1), (2, 5)], rate=2, capacity=10))
# [None, None, None, 1]