Token Bucket Rate Limiter
MediumState Machines · Intuit
Implement a per-user token bucket rate limiter.
events is a list of requests in the order they are processed. Each request is [user_id, timestamp, tokens_needed], where user_id is a string and timestamp and tokens_needed are integers.
Every user has their own bucket, and buckets never affect each other:
- A user's bucket starts full, holding
capacitytokens, at that user's first request. - Between two consecutive requests from the same user, the bucket gains
refill * (current_timestamp - previous_timestamp)tokens, whereprevious_timestampis the time of that user's previous request (allowed or not). The bucket can never hold more thancapacitytokens. - A request is allowed if the bucket holds at least
tokens_neededtokens after refilling; those tokens are then removed. Otherwise it is denied and the bucket is left unchanged.
Return a list of booleans, one per request in input order: True if it was allowed, False if it was denied.
Example 1
- Input:
- events = [["alice", 0, 4], ["bob", 1, 5], ["alice", 2, 3], ["alice", 3, 2]], capacity = 5, refill = 1
- Output:
- [True, True, True, False]
- Explanation
- Alice spends 4 of her 5 tokens at time 0, leaving 1. Bob has his own full bucket, so his request for 5 succeeds. By time 2 Alice has refilled to 1 + 2 = 3, exactly enough; at time 3 she has only 1 token but needs 2, so that request is denied.
Example 2
- Input:
- events = [["u", 0, 6], ["u", 0, 5]], capacity = 5, refill = 2
- Output:
- [False, True]
- Explanation
- Needing 6 tokens is more than the bucket can ever hold, so the first request is denied. A denied request takes nothing, so the second request for 5 at the same time still succeeds.
Example 3
- Input:
- events = [["u", 0, 5], ["u", 100, 5], ["u", 100, 1]], capacity = 5, refill = 3
- Output:
- [True, True, False]
- Explanation
- After 100 idle time units the refill would be 300 tokens, but the bucket is capped at 5. The second request empties it again, and the third arrives at the same timestamp with nothing refilled, so it is denied.
Constraints
0 <= events.length <= 10^51 <= capacity <= 10^90 <= refill <= 10^91 <= tokens_needed <= 10^9(a request may need more thancapacity; it is then always denied)0 <= timestamp <= 10^9, and each user's timestamps are non-decreasing