Step 2 of 4
Refill as time passes
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.
Now make refill(now) earn its name.
Between the last refill and now, the bucket should gain
elapsed × refillPerSecond tokens — and never hold more than capacity,
however long it has been idle. Record the time you refilled to, so the next call
only counts time it has not already counted.
capacity 2, 1 token/second
t=0 allow -> true allow -> true allow -> false
t=1 allow -> true allow -> falseTwo things to get right, and both are easy to miss:
- The cap is what bounds the burst. A bucket idle for an hour must not wake up holding 3600 tokens; that would let one client spend an hour's budget in a second, which is the exact failure the fixed-window counter has.
- Only count time once. Advancing your bookmark to
nowafter each refill is what stops the same second being credited twice.
Your build
Running is free — Submit is what records the step. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| runOps(2, 1, [["allow",0],["allow",0],["allow",0],["allow",1],["allow",1]]) | a second of waiting buys a token | [true,true,false,true,false] | — |
| runOps(2, 1, [["allow",0],["allow",0],["tokens",100]]) | an idle bucket never holds more than capacity | [true,true,2] | — |
| runOps(4, 2, [["allow",0],["allow",0],["allow",0],["allow",0],["tokens",1]]) | a faster rate refills faster | [true,true,true,true,2] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left