CODING CHALLENGE · N°31

Sliding-Window Rate Limiter

Medium SystemsRate LimitingQueue

Allow at most N requests per rolling time window — the rate limiter that guards real APIs. A sliding log of accepted timestamps gives exact limits without the boundary bursts a fixed window suffers. Decide accept/reject for a stream of requests. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement a rate limiter that permits at most limit requests in any window of window time units. You are given the request timestamps in non-decreasing order. For each timestamp, return True if the request is allowed (and it then counts against the limit) or False if it is rejected. A request at time t is allowed iff fewer than limit accepted requests fall in the half-open window (t - window, t].

EXAMPLE 1

Input limit = 2, window = 10, timestamps = [1, 2, 3, 11, 12]

Output [True, True, False, True, True]

the 3rd (t=3) is the 3rd request in (−7,3] → rejected; by t=11 the t=1 request has aged out

EXAMPLE 2

Input limit = 1, window = 5, timestamps = [1, 2, 6]

Output [True, False, True]

t=2 is within 5 of t=1; t=6 is not (6−5=1, and 1 ≤ 1 ages out)

CONSTRAINTS

Timestamps are non-decreasing; multiple requests may share a timestamp.
A rejected request does not count toward the limit (only accepted ones occupy the window).
The window is half-open: a request exactly window units old (t - window) has left the window.
Aim for amortized O(1) per request by dropping expired entries from the front of a queue.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement rate_limiter(limit, window, timestamps): keep a queue of accepted timestamps. For each new t, evict entries ≤ t - window from the front, then allow (and enqueue) if the queue holds fewer than limit; otherwise reject.

HINTS — 4 IDEAS

Only accepted requests occupy the window, so store just those in a queue (a deque).
Before deciding t, pop every front entry ≤ t - window — those have slid out of the window.
If the queue length is now below limit, accept: append t and return True. Otherwise return False.
The half-open boundary matters: use ≤ t - window (not <) so an entry exactly window old is expired.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Allow a request only if the number of requests in the last T seconds is under the limit. Two ways: a sliding-window log keeps request timestamps and drops any older than the window (exact, but O(n) memory), or a sliding-window counter approximates by blending the current fixed window’s count with a weighted fraction of the previous window’s (O(1), and it avoids the fixed-window edge burst).

Complexity

Log: O(1) amortized with a deque, O(window) memory. Counter: O(1) time and memory.

Common mistakes

Falling back to a fixed window, whose boundary lets a client send up to 2× the limit across the edge — the very thing sliding windows fix.
Unbounded timestamp growth in the log variant (evict old entries).
Wrong weighting of the previous window in the counter variant.

Where this shows up

Sliding-window rate limiting is what you reach for when a fixed window’s edge burst is unacceptable — it makes “100 per minute” actually mean 100 in any 60-second span. It is standard in API gateways and abuse prevention where the limit has to hold across boundaries, not just within neat clock minutes.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Caching & Performance