Vibe Engines Learn
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
  1. Only accepted requests occupy the window, so store just those in a queue (a deque).
  2. Before deciding t, pop every front entry ≤ t - window — those have slid out of the window.
  3. If the queue length is now below limit, accept: append t and return True. Otherwise return False.
  4. The half-open boundary matters: use ≤ t - window (not <) so an entry exactly window old is expired.
CPython · WebAssembly

Explore the topic

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

Caching & Performance