Design a rate limiter that decides whether each incoming request from a client is allowed. Time is an integer number of seconds passed in as now, and calls arrive with now never decreasing. In every part, only allowed requests count toward a limit; rejected ones are not recorded.
Implement RateLimiter(limit, window) with limit >= 1 and window >= 1.
Time is split into fixed windows [0, window), [window, 2 * window), and so on. allow(client, now) returns True if the client has made fewer than limit allowed requests in the window that contains now; that request then counts. Otherwise it returns False. Each client is counted separately, and the count starts from zero in every new window.
[True, True, True, False, False] True
rl = RateLimiter(3, 10)
print([rl.allow("a", t) for t in (0, 1, 2, 3, 9)])
print(rl.allow("a", 10))Build a fixed-window rate limiter, replace it with a sliding window that closes the boundary burst, then enforce several rules at once and implement a token bucket.
Also known as: Sliding window rate limiter, Fixed window rate limiter, API rate limiter
Rate limiting and time-window counts shows up in 6.1% of the 1,447 coding interview reports we studied, at 10 companies. Allow or reject requests, or count events, within a moving time window.
Reported at: OpenAI, Rippling, Harvey AI, Snowflake, Zip, Anthropic, Citadel, Waymo.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Design a rate limiter that decides whether each incoming request from a client is allowed. Time is an integer number of seconds passed in as now, and calls arrive with now never decreasing. In every part, only allowed requests count toward a limit; rejected ones are not recorded.
Implement RateLimiter(limit, window) with limit >= 1 and window >= 1.
Time is split into fixed windows [0, window), [window, 2 * window), and so on. allow(client, now) returns True if the client has made fewer than limit allowed requests in the window that contains now; that request then counts. Otherwise it returns False. Each client is counted separately, and the count starts from zero in every new window.
A fixed window lets a client send limit requests at the end of one window and limit more at the start of the next, so twice the limit in a moment.
Implement SlidingWindowRateLimiter(limit, window) with the same allow(client, now). A request is allowed if the client has fewer than limit allowed requests at times t where now - window < t <= now. So a request made at time t stops counting at exactly t + window.
Real limits come in groups: "3 per user per minute" plus "10 per team per minute", or "3 per second" plus "20 per 10 seconds" for the same user.
Implement MultiRuleRateLimiter(rules). rules is a list of (field, limit, window) tuples. Each rule is a Part 2 sliding window counted separately for each value of request[field]. Two rules may use the same field with different windows.
allow(request, now) takes a dict that has every field the rules name, for example {"user": "u1", "team": "t1"}. The request is allowed only if every rule has room for it. If it is allowed it counts toward every rule; if any rule rejects it, it counts toward none of them.
Implement TokenBucketRateLimiter(capacity, refill_rate), a different algorithm that allows short bursts while holding an average rate.
capacity tokens. A client's bucket is full the first time it is seen.refill_rate tokens for each second that passes and is capped at capacity. You do not need a timer: when a call arrives at now, add (now - last call's now) * refill_rate tokens, capped at capacity.allow(client, now, cost=1) returns True and removes cost tokens if the bucket holds at least cost. Otherwise it returns False and removes nothing.All values are integers. Clients have separate buckets.
Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
A fixed window limiter only needs two numbers per client: which window it is in and how many allowed requests it has made there. The window number is now // window, so seconds 0 to 9 share window 0 when the window is 10. On each call, if the stored window number differs from the current one, the count starts again from zero. If the count has reached the limit the request is rejected and nothing changes; otherwise the count goes up by one. Rejected requests must not increase the count, or a client that keeps retrying would stay blocked. This is O(1) time and O(1) memory per client, which is why fixed windows are popular. The weakness is at the edges, which Part 2 fixes.
With fixed windows a client can spend its whole limit at the end of one window and again at the start of the next. A sliding window removes that burst by asking, at each request, how many allowed requests happened in the window seconds ending now. Keep each client's allowed request times in order. Before checking, drop every time at or before now - window, since those can never count again; the reference solution finds the cut with bisect_right and deletes the prefix. If fewer than limit times remain, append now and allow the request. Each time is added and removed once, so the cost is amortized small, and memory is at most limit times per client. The price compared with Part 1 is that memory grows with the limit. The reference also splits allow into has_room and record, which Part 3 reuses.
Each rule is just a Part 2 sliding window whose key is the value of one request field, so the reference builds one SlidingWindowRateLimiter per rule and keeps them in a list. Rules that share a field still get their own window objects, which is what lets a per-second rule and a per-10-second rule coexist for the same user. The subtle requirement is atomicity: a request rejected by any rule must leave no trace in the others. So allow runs in two passes. First it asks every rule whether it has room, stopping at the first refusal; only if all agree does it record now in every rule. Recording as you go would let the user rule count a request that the team rule then rejects. The cost is O(R log L) per call for R rules.
A token bucket keeps two numbers per client: tokens left and the time of the last call. Instead of a timer, each call refills lazily: the tokens earned since the last call are (now - last) * refill_rate, and the bucket is capped at capacity, so a long idle period cannot bank more than one full burst. Then, if at least cost tokens remain, subtract them and allow the request; otherwise reject it and leave the tokens alone. New clients start with a full bucket. Compared with the sliding window this uses constant memory per client and naturally supports requests of different sizes, but it limits the average rate plus a burst rather than giving a strict count over every window. Each call is O(1).
Keep, per client, the current window number (now // window) and a count. When the window number changes, start the count over.
Keep the times of each client's allowed requests in order. Drop the ones at or before now - window, then compare how many remain with the limit.
Split the Part 2 check into two steps, 'is there room?' and 'record it', so a multi-rule request can ask every rule first and record only when all agree.
Store just two numbers per client: tokens left and the time of the last call. Refill lazily at the start of each call instead of running a timer.
The fixed window limiter is O(1) time and memory per client. Each sliding window keeps at most limit times per key; each time is appended once and removed once, so a check is amortized O(log L). The multi-rule limiter does that once per rule, O(R log L) for R rules. The token bucket is O(1) time and two numbers of memory per client.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides