codejump
HardPro challengePython

Token Bucket Rate Limiter

PythonDesignResilience

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

Implement create_token_bucket(capacity, refill_per_ms):

  • capacity — maximum tokens the bucket can hold.
  • refill_per_ms — 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: min(capacity, current + elapsed * refill_per_ms).

Sample tests

Test #1Burst empties the bucket; the third request is denied
Input: [10,1,[{"t":0,"tokens":5},{"t":0,"tokens":5},{"t":0,"tokens":1}]]
Output: ["allowed","allowed","denied"]
Test #23ms only refills 3 tokens (not enough for 6); by t=10 there is enough again
Input: [10,1,[{"t":0,"tokens":10},{"t":3,"tokens":6},{"t":10,"tokens":6}]]
Output: ["allowed","denied","allowed"]
Test #30.5 token/ms: 10ms refills exactly 5 tokens, not enough for a 6-token request
Input: [10,0.5,[{"t":0,"tokens":10},{"t":10,"tokens":6}]]
Output: ["allowed","denied"]
Test #4Second request denied when not enough tokens remain
Input: [5,1,[{"t":0,"tokens":3},{"t":0,"tokens":3}]]
Output: ["allowed","denied"]
Test #52 token/ms: 3ms adds 6 tokens back, exactly enough
Input: [10,2,[{"t":0,"tokens":10},{"t":3,"tokens":6}]]
Output: ["allowed","allowed"]
← All challenges