Token Bucket Rate Limiter

Problem

Simulate a token-bucket rate limiter.

The bucket starts full with capacity tokens and refills at refill_rate tokens per time unit, capped at capacity. operations contains "request" (consume one token if available, recording True or False) or "tokens" (return the whole tokens currently available).

Return the list of recorded results.

Hint

Refill lazily from the previous event time and cap at capacity.

Test cases

case 1

in: [3,1,["request","request","request","request","tokens","tokens"],[0,0,0,0,1,3]]

expected: [true,true,true,false,1,3]

case 2

in: [2,1,["request","request","request","tokens"],[0,0,0,1]]

expected: [true,true,false,1]

case 3

in: [1,0.5,["tokens"],[0]]

expected: [1]

case 4

in: [2,2,["request","tokens","request","tokens"],[0,1,1,1]]

expected: [true,2,true,1]

Starter codePython

def token_bucket(capacity, refill_rate, operations, timestamps):
    # Your code here
    pass

4 test cases · run your code against them in the editor