Build a rate limiter allowing N requests per time window using a deque of timestamps — a sliding-window log in amortised O(1). System-design favourite.
The problem
Implement RateLimiter(limit, window). allow(timestamp) returns True if the request at that time (seconds, non-decreasing) is allowed, else False.
A request is allowed when fewer than limit requests were allowed in the last window seconds — the interval (timestamp - window, timestamp].
With limit=3, window=1.0, requests at 0.0, 0.1, 0.2, 0.3 → True, True, True, False.
Examples
Example 1
Input
run_ops(RateLimiter, [3, 1.0], [["allow", 0.0], ["allow", 0.1], ["allow", 0.2], ["allow", 0.3]])
Expected output
[True, True, True, False]
Example 2
Input
run_ops(RateLimiter, [2, 1.0], [["allow", 0.0], ["allow", 0.5], ["allow", 0.9], ["allow", 1.0]])
Expected output
[True, True, False, True]
+ 2 hidden tests on Submit — boundary is exclusive.
Edge cases to ask about
- Window boundary
- Same timestamp repeated
- Long idle gap
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.
Pick both to reveal the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Fixed window counter | O(1) | O(1) | Cheap, but allows 2× the limit across a window boundary. |
| Sliding window log (deque) | O(1) amortised | O(limit) | Drop expired timestamps from the left, then count. |
| bestToken bucket | O(1) | O(1) | Refill tokens at a fixed rate; allows controlled bursts. |
Walkthrough of the optimal approach (try it yourself first)
Keep a deque of allowed timestamps. On each request, pop from the left everything at or before timestamp - window, then allow only if fewer than limit remain. Each timestamp is appended and popped once, so the cost is amortised O(1) and memory is bounded by limit.
Discuss the alternatives: a fixed window counter is cheaper but lets through bursts at window edges; a token bucket allows controlled bursts and is what most API gateways use. For many servers, the state moves to Redis.
Complexity: O(1) amortised time, O(limit) space. Each timestamp is appended once and popped once; the deque never holds more than `limit` allowed timestamps.
Reveal the reference solution
from collections import deque class RateLimiter: def __init__(self, limit, window): self.limit = limit self.window = window self.hits = deque() def allow(self, timestamp): while self.hits and self.hits[0] <= timestamp - self.window: self.hits.popleft() if len(self.hits) < self.limit: self.hits.append(timestamp) return True return False
Follow-ups interviewers ask
- Implement a token bucket.
- Rate-limit per user across many servers.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Rate Limiter (Sliding Window Log) in Python?
The optimal solution runs in O(1) amortised time and O(limit) auxiliary space. Each timestamp is appended once and popped once; the deque never holds more than limit allowed timestamps.
What is the brute-force approach, and how do you optimise it?
Fixed window counter: O(1) time, O(1) space. Cheap, but allows 2× the limit across a window boundary. Sliding window log (deque): O(1) amortised time, O(limit) space. Drop expired timestamps from the left, then count. Token bucket: O(1) time, O(1) space. Refill tokens at a fixed rate; allows controlled bursts.
What follow-up questions do interviewers ask about Rate Limiter (Sliding Window Log)?
Implement a token bucket. Rate-limit per user across many servers.