API Rate Limiter
Two policies behind one interface: a sliding-window log and a token bucket, per client.
the brief
What you are building
A payments API gets traffic from thousands of apps. One buggy app retries in a loop and sends 5,000 requests a second. Without a limit, everyone's payments slow down.
You will build the rate limiter that sits in front of the API. For every request it answers one question: let it in, or reject it?
The interviewer wants two policies, so you can show that a new policy plugs in without touching the rest.
must have
Requirements
- Every client (
clientId) has its own limit. One client's traffic never affects another. - Sliding window (
"sliding-window"): allow a request at timenowonly if this client had fewer thanlimitallowed requests in the lastwindowMsms — that is, at timestwitht > now - windowMs. - Rejected requests are not counted.
- Token bucket (
"token-bucket"): each client's bucket holds up tolimittokens and starts full. A request uses one token; with no token it is rejected. - Tokens drip back one at a time, every
interval = windowMs / limitms, counted from the client's first call (alloworremaining). A drip into a full bucket is wasted. remaining(clientId, now)says how many requests the client could make right now, without using one.- Any other policy name makes the constructor throw
IllegalArgumentException.
the contract
The Java API: class RateLimiter
Time is passed in (nowMs) instead of read from the clock, so tests are exact and repeatable.
public RateLimiter(String policy, int limit, long windowMs)policyis"sliding-window"or"token-bucket".public boolean allow(String clientId, long nowMs)true(and the request counts) orfalse.public int remaining(String clientId, long nowMs)- How many more requests would be allowed right now.
- 1 ≤ limit ≤ 1,000 and limit ≤ windowMs ≤ 10⁹
- for the token bucket,
windowMsis a multiple oflimit nowMsnever goes backwards, and may be as large as 2 × 10¹²- up to 20,000 calls
example session
Calls in, answers out
Session 1: sliding window, 3 requests per 1,000 ms. Session 2: token bucket, 2 tokens, so one drip every 500 ms.
| call | returns | why |
|---|---|---|
new RateLimiter("sliding-window", 3, 1000) | — | |
allow("rahul", 0) | true | |
allow("rahul", 100) | true | |
allow("rahul", 200) | true | |
allow("rahul", 300) | false | 3 allowed in (−700, 300] already |
allow("priya", 300) | true | priya has her own window |
remaining("rahul", 999) | 0 | |
allow("rahul", 1000) | true | the request at 0 left the window: 0 > 1000 − 1000 is false |
remaining("rahul", 1150) | 1 | only 200 and 1000 are inside (150, 1150] |
new RateLimiter("token-bucket", 2, 1000) | — | |
allow("app", 0) | true | the bucket starts full: 2 → 1 |
allow("app", 10) | true | 1 → 0 |
allow("app", 20) | false | empty |
remaining("app", 499) | 0 | the first drip is at 0 + 500 |
allow("app", 500) | true | one drip, used at once |
remaining("app", 2000) | 2 | drips at 1000, 1500, 2000 — but the bucket holds only 2 |
time plan
Your 90 minutes
- 10 minclarify — Per client or global? Do rejected requests count? When exactly does a request leave the window? When does the first drip happen?
- 15 mindesign — One
Policyinterface, one class per policy, one map from client to its policy object. Draw the sliding window on a time line. - 35 mincore code — Sliding window first (run session 1), then the token bucket (run session 2).
- 20 minedge cases — limit 1, exact window boundary, a full bucket wasting drips, an unknown client, huge timestamps.
- 10 minpolish — Be ready to compare the two policies and to talk about many servers sharing one limit.
Practise under real pressure: a 90-minute clock with the phases above. It keeps running if you reload the page.
your turn
Build it here
Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.
Build RateLimiter in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.
Opening all three hints also shows it.
reference
One clean way to build it
Both policies behind one interface; one state object per client, created on first use.
class RateLimiter { /** One client's rule. A new rule (fixed window, leaky bucket…) is one more class, nothing else changes. */ interface Policy { boolean tryAcquire(long now); int remaining(long now); } /** Sliding-window log: the times of the requests we let in during the last windowMs, oldest first. */ static class SlidingWindow implements Policy { private final int limit; private final long windowMs; private final ArrayDeque<Long> allowed = new ArrayDeque<>(); SlidingWindow(int limit, long windowMs) { this.limit = limit; this.windowMs = windowMs; } /** A request at time t counts while t > now - windowMs. Older ones leave from the front. */ private void dropOld(long now) { while (!allowed.isEmpty() && allowed.peekFirst() <= now - windowMs) allowed.pollFirst(); } public boolean tryAcquire(long now) { dropOld(now); if (allowed.size() == limit) return false; // rejected requests are not recorded allowed.addLast(now); return true; } public int remaining(long now) { dropOld(now); return limit - allowed.size(); } } /** Token bucket: starts full; one token drips in every interval ms; a full bucket wastes the drip. */ static class TokenBucket implements Policy { private final int capacity; private final long interval; private int tokens; private long lastDrip; // drips happen at firstSeen + k * interval TokenBucket(int capacity, long interval, long now) { this.capacity = capacity; this.interval = interval; this.tokens = capacity; this.lastDrip = now; } /** O(1): count the drips since the last one we counted, instead of looping over them. */ private void refill(long now) { long drips = (now - lastDrip) / interval; if (drips == 0) return; tokens = (int) Math.min(capacity, tokens + drips); lastDrip += drips * interval; } public boolean tryAcquire(long now) { refill(now); if (tokens == 0) return false; tokens--; return true; } public int remaining(long now) { refill(now); return tokens; } } private final String policy; private final int limit; private final long windowMs; private final Map<String, Policy> clients = new HashMap<>(); // clientId → that client's own state public RateLimiter(String policy, int limit, long windowMs) { if (!policy.equals("sliding-window") && !policy.equals("token-bucket")) { throw new IllegalArgumentException("unknown policy: " + policy); } this.policy = policy; this.limit = limit; this.windowMs = windowMs; } /** The first time we hear about a client, it gets a fresh state (a full bucket / an empty log). */ private Policy stateOf(String clientId, long now) { return clients.computeIfAbsent(clientId, id -> policy.equals("token-bucket") ? new TokenBucket(limit, windowMs / limit, now) : new SlidingWindow(limit, windowMs)); } public boolean allow(String clientId, long nowMs) { return stateOf(clientId, nowMs).tryAcquire(nowMs); } public int remaining(String clientId, long nowMs) { return stateOf(clientId, nowMs).remaining(nowMs); }}the choices
Which data structures, and why
HashMap<String, Policy>Client id → that client's own state. Clients never share a limit.
O(1) average to find a client.
ArrayDeque<Long> (sliding window)The allowed times in the last window, oldest at the front. Expired times are popped from the front; new ones are added at the back.
Amortized O(1) per call: each time is added once and popped once. Memory: up to limit longs per client.
tokens and lastDrip. The refill is computed with one division, not a loop over every drip.
O(1) time and O(1) memory per client — the reason big systems like token buckets.
interface PolicyEach policy is a small class. A fixed window or a leaky bucket is a new class; allow does not change.
One virtual call per request.
self-check
Mark yourself like the interviewer would
Tick only what your code really does. Nothing is saved or sent — this is just for you.
your honest self-score: 0 / 100
traps
Common mistakes
- Using
intfor time. Milliseconds since 1970 are about 1.8 × 10¹² today, far pastInteger.MAX_VALUE(about 2.1 × 10⁹). - Getting the boundary wrong (
<vs<=). Draw a time line and test the request at exactlynow - windowMs. - Counting rejected requests in the window. Then a client that is over the limit can never recover while it keeps retrying.
- Refilling the bucket with a loop, one drip at a time. After a long quiet gap that is millions of iterations.
- Calling
System.currentTimeMillis()inside the class. The code becomes impossible to test exactly; take time as a parameter.
what they ask next
Follow-ups and extensions
Sliding-window log vs token bucket: when would you pick each?
The log is exact but stores up to limit timestamps per client.
The bucket needs two numbers per client and allows short bursts up to limit. At scale, buckets (or a sliding-window counter, which keeps just two counts) are the usual choice.
The API runs on 20 servers. The limit must be shared.
Each server alone cannot know the total, so the counters move to a shared store such as Redis, updated atomically (a script or an atomic increment with an expiry).
Or give each server limit / 20 and accept a little unfairness.
Different limits for free and paid clients.
Pass a small lookup (client → plan → limit) to the factory that creates each client's Policy. Nothing else changes.
Memory keeps growing with clients that never come back.
Remove a client's state when it has been idle longer than the window (its state would be "fresh" anyway). A LinkedHashMap in access order makes the idle ones easy to find from the oldest end.
revise