codejump
HardPro challengeJavaScriptTypeScript

Token Bucket Rate Limiter

Node.jsDesign

The token bucket algorithm allows bursts while enforcing an average rate.

Implement createTokenBucket(capacity, refillPerMs):

  • capacity — maximum tokens the bucket can hold.
  • refillPerMs — tokens added per millisecond (can be fractional).
  • consume(tokens, timestamp) — attempt to consume tokens at virtual time timestamp.

Returns true if allowed (enough tokens), false otherwise.

The bucket starts full (capacity tokens). Tokens are added based on elapsed
time since the last call: Math.min(capacity, current + elapsed * refillPerMs).

Sample tests

Test #1Burst: empties bucket, third denied
Input: [10,1,[{"t":0,"tokens":5},{"t":0,"tokens":5},{"t":0,"tokens":1}]]
Output: ["allowed","allowed","denied"]
Test #2Refill: 5ms refills 5 tokens
Input: [10,1,[{"t":0,"tokens":10},{"t":5,"tokens":5},{"t":10,"tokens":5}]]
Output: ["allowed","denied","allowed"]
Test #30.5 token/ms: 10ms refills 5, need 5 ok but got 5 → allowed
Input: [10,0.5,[{"t":0,"tokens":10},{"t":10,"tokens":5}]]
Output: ["allowed","denied"]
Test #4Second request denied when not enough tokens
Input: [5,1,[{"t":0,"tokens":3},{"t":0,"tokens":3}]]
Output: ["allowed","denied"]
Test #52 token/ms: 3ms adds 6 tokens back
Input: [10,2,[{"t":0,"tokens":10},{"t":3,"tokens":6}]]
Output: ["allowed","allowed"]
← All challenges