Step 4 of 4

Give every client its own bucket

You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.

One bucket limits everybody together, which is a global throttle, not a rate limit. A rate limiter bounds each client separately: one noisy caller must not be able to throttle everyone else.

This step adds a second file. limiter.js holds a map from client key to that client's bucket, and allow(key, now) finds — or creates — the right one and asks it.

capacity 1, 1 token/second
allow("a", 0)  ->  true
allow("a", 0)  ->  false     // a is out
allow("b", 0)  ->  true      // b is untouched

A client seen for the first time gets a full bucket, exactly as if it had been idle since the beginning. Anything else would penalise a new client for being new.

The part this deliberately leaves out. Nothing here ever forgets a client, so the map grows for as long as the process lives — an unbounded map keyed by something an attacker chooses. A real deployment evicts idle buckets, which is the same eviction question the LRU cache build answers. Two builds, one problem.

Your build

Running is free — Submit is what records the step. Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
runOps(1, 1, [["allow","a",0],["allow","a",0],["allow","b",0]])each client gets its own allowance[true,false,true]—
runOps(2, 1, [["allow","a",0],["allow","b",0],["allow","a",0],["clients"]])clients are counted as they appear[true,true,true,2]—
runOps(1, 1, [["allow","a",0],["allow","a",0],["allow","b",0],["allow","b",0],["allow","a",1]])one client running dry leaves the others alone[true,false,true,false,true]—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time
O(1) per request
target space
O(clients)

One hash lookup and a constant amount of arithmetic per request — no scan over a window of past requests, which is what a naive sliding-window counter does. The space is the honest cost: one bucket per client key, held forever unless something evicts them.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left