Learn

Your rate limiter refuses the request that arrives exactly one window later

9 November 2026 · One mistake, one counterexample

The question sounds easy: allow at most a few events per user in any window of a given length. You reach for a queue of timestamps, drop the old ones, count what is left. The sample passes. Then the interviewer asks what happens to an event that lands exactly one window after the first one, and you are not sure which way your code goes.

The situation

A chat app may send each user at most limit push notifications in any window seconds. Events arrive in time order as pairs of a time in whole seconds and a user id. For each event, return whether it is allowed. A sliding log is the natural answer: keep the times of recent allowed events per user, drop the ones that have fallen out of the window, and allow the new one if fewer than limit remain.

from collections import defaultdict, deque

def allowed(events, window, limit):
    recent = defaultdict(deque)
    out = []
    for t, user in events:
        q = recent[user]
        while q and t - q[0] > window:
            q.popleft()
        if len(q) < limit:
            q.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

The sample has events at 0, 10 and 70 for one user with window = 60 and limit = 1. It returns allowed, refused, allowed, which is what anyone expects. Nothing in that sample sits on the edge.

The input that breaks it

Call it with [(0, "a"), (60, "a")], window = 60, limit = 1. If "any window of 60 seconds" means the 60 seconds ending now, the half-open interval from t - 60 to t, then the event at 0 is no longer in it and the event at 60 should be allowed. The code returns [True, False]. At time 60, 60 - 0 > 60 is false, so the old event stays in the queue and the new one is refused. The user waits until 61.

The hidden assumption is "older than the window" needs no definition. It does. One second either way is the whole bug, and [(0, "a"), (59, "a")] cannot catch it, because that pair is refused under either reading.

The fix is one character, and it only means something once you have said which interval you chose:

while q and t - q[0] >= window:
    q.popleft()

In Java the same line on a Deque<Integer> reads while (!q.isEmpty() && t - q.peekFirst() >= window) q.pollFirst();. With it, the two-event input returns [True, True], and [(0, "a"), (59, "a")] still returns [True, False].

A second way to break the same promise

Some versions append every event to the queue, refused or not, on the idea that the log should record what happened. Feed that version one event every 30 seconds, [(0, "a"), (30, "a"), (60, "a"), (90, "a")], with the fixed comparison. A correct limiter allows the events at 0 and 60: [True, False, True, False]. The version that stores refusals returns [True, False, False, False], and it stays shut for as long as the user keeps trying, because every refusal pushes the next opening further away.

Both bugs break one invariant: the queue for a user holds exactly the allowed events whose time is in the current window. The first keeps an event that has left the window; the second holds events that were never allowed.

What to say out loud

Before writing the loop, pin the interval: "I'll read 'any 60 seconds' as the half-open window from t − 60 to t, so an event exactly 60 seconds old has left it. Is that the rule you want?" If the interviewer prefers the closed reading, you change one operator and say so.

Then state the invariant as you write the append: "The queue only holds allowed events inside the window, so a refused event is not appended." If the interviewer later asks about memory, the same sentence answers it: the queue never holds more than limit entries per user.

The exercise

1. Write the sliding log from memory in Java or Python, without looking at the version above.
2. Before running it, write down what you expect for [(0, "a"), (60, "a")] and for [(0, "a"), (59, "a")] with window = 60, limit = 1. Then run both.
3. Add the four-event input at 30-second intervals and check that the user gets the event at 60.
4. Add a second user to any of these inputs, interleaved, and confirm their answers do not change.
5. Say the interval sentence and the invariant sentence aloud, once each, before you write the loop.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question instead of revealing the solution, so "what does your code return for an event exactly one window later?" is the kind of question it asks when a boundary is left unsaid. "I'm stuck" gives one more step, up to pseudocode, never finished code.