Q5 - Sliding-Window Rate Limiter (Throttling Abusive Clients)

Scenario: Amazon's API gateway must throttle abusive clients. The rule: each user may make at most limit requests in any rolling window of windowMs milliseconds. Requests arrive as a stream of [timestamp, user] in non-decreasing timestamp order, and for each one you decide allow or reject. A rejected request does not count against the user (it never reached the service), so it never fills a slot in the window.

Part 1: Return the decision for each request in order: true if it is allowed, false if it is rejected.

Input:  requests = [[0, "u1"], [100, "u1"], [200, "u1"], [300, "u2"], [1100, "u1"]]
        limit = 2,  windowMs = 1000
Output: [true, true, false, true, true]
Why: u1 is allowed at t=0 and t=100 (2 in the window). At t=200, u1 already has 2 requests
        in the last 1000ms, so it is rejected. u2 at t=300 is a different user, so it is allowed. By
        t=1100 both of u1's earlier requests (0 and 100) have aged out, so u1 is allowed again.

Part 1: Modeling the State

Keep, for each user, a queue of the timestamps of their allowed requests that are still inside the window. On a new request at time ts:

• Drop timestamps from the front while they are <= ts - windowMs (they have aged out of the window).
• If fewer than limit remain, the user has room: record ts and allow.
• Otherwise the window is full: reject, and record nothing.

Because each timestamp is added once and dropped once, the work per request is O(1) amortized.

In code the drop-then-decide is the whole method: age out the front, then allow only if there is room.

timestamps = history[user]
while timestamps and timestamps[0] <= ts - window:   # drop timestamps that aged out
    timestamps.popleft()
if len(timestamps) < limit:                          # room in the window: allow
    timestamps.append(ts)
    return True
return False                                          # window full: reject

Here is Example 1 request by request. Watch u1's window fill, reject the third request, and then reopen once the old timestamps age out (u2 keeps its own separate window):

limit = 2, windowMs = 1000
request        state (allowed timestamps in window)   decision
----------------------------------------------------------------------
t=0    u1      u1: [0]                                 ALLOW
t=100  u1      u1: [0, 100]                            ALLOW
t=200  u1      u1: [0, 100]  (already 2 in window)     REJECT
t=300  u2      u2: [300]                               ALLOW
t=1100 u1      u1: drop 0 and 100 -> [1100]            ALLOW
----------------------------------------------------------------------
decisions: [true, true, false, true, true]

# O(1) amortized per request | O(active users * limit) space
from collections import deque

class RateLimiter:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window = window_ms
        self.history = {}                       # user -> deque of allowed timestamps in the window

    def allow(self, ts, user):
        timestamps = self.history.setdefault(user, deque())
        while timestamps and timestamps[0] <= ts - self.window:   # drop timestamps that aged out
            timestamps.popleft()
        if len(timestamps) < self.limit:             # room in the window: allow
            timestamps.append(ts)
            return True
        return False                         # window full: reject

Part 2: Telling Clients When to Retry

Got Part 1? Here is the follow-up. A good API does not just say "no", it tells a throttled client how long to wait (this is the HTTP 429 Too Many Requests and its Retry-After header). Change allow to return 0 when a request is allowed, and when it is rejected, the number of milliseconds until the client would be let through.

A slot frees up the instant the user's oldest in-window request ages out. That request was made at timestamps[0] and leaves the window at timestamps[0] + windowMs, so the wait is timestamps[0] + windowMs - ts.

Only the rejection path changes, and it needs no new state, the answer is already in the queue:

if len(timestamps) < limit:
    timestamps.append(ts)
    return 0
return timestamps[0] + window - ts     # oldest request leaves the window at ts0 + window

Input:  requests = [[0, "u1"], [100, "u1"], [200, "u1"], [300, "u2"], [1100, "u1"]]
        limit = 2,  windowMs = 1000
Output: [0, 0, 800, 0, 0]
Why: only the request at t=200 is rejected. u1's oldest live request is at t=0, which leaves
        the window at t = 0 + 1000 = 1000, so the client should wait 1000 - 200 = 800ms and try again.

# O(1) amortized per request | O(active users * limit) space
from collections import deque

class RateLimiter:
    def __init__(self, limit, window_ms):
        self.limit = limit
        self.window = window_ms
        self.history = {}

    def allow(self, ts, user):               # returns 0 if allowed, else ms to wait
        timestamps = self.history.setdefault(user, deque())
        while timestamps and timestamps[0] <= ts - self.window:
            timestamps.popleft()
        if len(timestamps) < self.limit:
            timestamps.append(ts)
            return 0
        return timestamps[0] + self.window - ts       # oldest in-window request frees a slot then

Complexity Analysis

Time: O(1) amortized per request. Each timestamp is added once and dropped once over the whole run, so the eviction loop is amortized constant. Use a real double-ended queue for O(1) front-eviction; the JavaScript and TypeScript versions use array.shift() for readability, which is O(n) per drop, so a production build would swap in a proper deque or ring buffer.

Space: O(active users * limit). Each user holds at most limit timestamps inside the window. Users who go quiet keep a small empty queue; a real system would evict idle users entirely.

Final Notes

1. One window per user. The whole design is a map from user to that user's recent timestamps. Sharing a single window across users is the classic first-draft bug; say "per user" out loud before you write a line.
2. A rejected request must leave no trace. Only allowed requests are recorded. If you push the timestamp before checking the limit, a burst of rejects can wrongly lock a user out. Check first, record only on allow.
3. Be precise about the boundary. A timestamp ages out when it is <= ts - windowMs. Off-by-one here (using < instead of <=, or comparing against ts instead of ts - windowMs) is the single most common mistake, so state your rule explicitly.
4. Retry-after falls out of the state you already have. Part 2 needs no new structure: the moment a slot frees is just when the oldest in-window request expires, timestamps[0] + windowMs. The point of the follow-up is noticing the answer is already sitting in the queue you built.

It reads like a five-minute problem, and then the boundary conditions bite. Keep each user's window separate, drop old timestamps at the exact right instant, and leave nothing behind when you reject. That is the gap between code that works in a demo and code that holds up at 3am. 🚀