Build a rate limiter: A Sample Coding Interview Solution

The coding question

Implement a rate limiter where each API key can make at most N requests in any 60-second window. Write allow(key, timestamp), which returns whether a request is allowed.

Ask a few questions first

Ask	What we'll assume
Any 60 seconds, or fixed minutes?	Any 60 seconds: a sliding window ending at each request.
Does a request at second 0 still count at second 60?	No. A request at time t looks at the window from t - 60 (not included) up to t. Say this out loud, because it's the boundary they're testing.
Do denied requests count toward the limit?	No. Only allowed ones are recorded.
Do timestamps arrive in order?	Yes, never going backwards for a key. They're in seconds and might have decimals.
Multiple threads or servers?	One process for now. Scaling out is a follow-up.

A couple of examples

Input	Output
N = 3. allow('a', t) for t = 0, 10, 20, 30, 59, 60, 61	[True, True, True, False, False, True, False]
N = 2. Keys alternate: a@0, b@0, a@1, b@1, a@2, b@2	[True, True, True, True, False, False]
N = 2. allow('a', t) for t = 5, 5, 5, 64, 65, 66	[True, True, False, False, True, True]

Start with brute force

Keep every timestamp for every key forever. On each call, count how many are in the last 60 seconds.

Cost: O(n) per call, where n is everything that key has ever sent, and memory that never stops growing.

A better way

Timestamps only go forward, so once a request falls out of the window it never comes back. Keep each key's allowed requests in a queue, oldest first. On each call, pop from the front anything that's expired. What's left is exactly the requests in the window.

This is called a sliding log. It's a sliding window over time, kept per key in a hash map, and it's one of the standard rate limiting approaches. It's exact, and each timestamp gets added and removed once.

Keep a dictionary from key to a deque of allowed timestamps.
On allow(key, t), pop from the front while the oldest is at or before t - 60.
If the deque holds N or more, return False and don't record anything.
Otherwise append t and return True.

The code

solution.pypython

from collections import defaultdict, deque


class RateLimiter:
    def __init__(self, limit, window=60):
        self.limit = limit
        self.window = window
        self.log = defaultdict(deque)  # key -> times of allowed requests, oldest first

    def allow(self, key, timestamp):
        times = self.log[key]
        # A request at time t looks at the window (t - 60, t].
        # Anything at or before t - 60 has expired.
        while times and times[0] <= timestamp - self.window:
            times.popleft()
        if len(times) >= self.limit:
            return False  # denied requests aren't recorded
        times.append(timestamp)
        return True

	Cost	Why
allow, on average	O(1)	Each timestamp is added once and removed once
allow, worst single call	O(N)	One call might clear out N expired timestamps
Space	O(N) per active key	At most N timestamps per key are kept

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Exactly on the boundary: with N = 3, the request at 60 is allowed because the one at 0 has just expired, but 61 is denied because 10 hasn't.
Several requests at the same second: with N = 2, the third at second 5 is denied.
Keys don't affect each other: 'a' hitting its limit doesn't block 'b'.
N = 0 denies everything.
Decimal timestamps: with N = 1, a request at 59.9 is denied but one at 60 is allowed.

Common mistakes

Using < instead of <= when expiring, which shifts the boundary by one. Either can be right, but pick one and say which.
Recording denied requests, so a key that keeps retrying stays locked out forever.
Using fixed minute buckets. They let through 2N requests across a boundary: N at 0:59 and N more at 1:00.
Sharing one queue across all keys.

Follow-up questions

What if there are millions of keys and N is big?

The log stores N timestamps per key. A sliding window counter only keeps two counts per key: this minute and last minute. Estimate with this minute's count plus last minute's, scaled by how much of last minute is still in the window. It's slightly approximate and uses tiny memory. A token bucket is also O(1) per key.

How does this work across many servers?

Keep the counts in a shared store like Redis and do the check-and-add in one atomic step, with a script, so two servers can't both let the Nth request through.

How do you stop idle keys using memory forever?

Delete a key once its deque is empty, or sweep now and then for keys with nothing in the last 60 seconds.

How the time adds up

Minutes	What you're doing
0–5	Ask questions, especially about the boundary
5–10	Examples and brute force
10–15	Explain the sliding log
15–30	Write the code
30–40	Test the examples and edge cases
40–60	Follow-ups: memory, token bucket and many servers

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Stripe.