Token Bucket Request Decisions
Problem statement
Apply a token-bucket rate limiter to requests in input order. At time zero the bucket holds capacity tokens. It gains refillRate tokens per time unit, up to capacity.
Before request i, refill for the time since the previous request, starting from time zero for the first request. If at least costs[i] tokens are available, accept the request and remove that many tokens. Otherwise reject it and remove no tokens. A rejected request still establishes the time used for the next refill. Requests at the same timestamp are processed in input order without an intervening refill.
Return one integer per request: 1 for accepted and 0 for rejected. A zero-cost request is always accepted. A cost above capacity can never be accepted. An empty request list returns an empty array.
Function
tokenBucketDecisions(capacity: int, refillRate: int, arrivalTimes: int[], costs: int[]) → int[]Examples
Example 1
capacity = 5refillRate = 2arrivalTimes = [0,0,1,3]costs = [4,2,2,5]return = [1,0,1,1]Start with 5 tokens. The first request uses 4, leaving 1. The next request at time zero needs 2 and is rejected. At time 1, refill to 3, accept cost 2, and keep 1. By time 3, refill reaches the cap of 5, so cost 5 is accepted.
Example 2
capacity = 3refillRate = 0arrivalTimes = [0,5,5,100]costs = [3,0,1,3]return = [1,1,0,0]The first request empties the bucket. A zero-cost request is accepted, but the refill rate is zero, so later positive costs remain rejected even after long waits.
Example 3
capacity = 2refillRate = 3arrivalTimes = [0,10]costs = [3,2]return = [0,1]Cost 3 exceeds the bucket capacity and is rejected. At time 10 the bucket is still capped at 2; cost 2 is accepted.
Constraints
1 <= capacity <= 10000000000 <= refillRate <= 10000000000 <= arrivalTimes.length <= 200arrivalTimes.length == costs.length0 <= arrivalTimes[i] <= 1000000000; arrival times are nondecreasing.0 <= costs[i] <= 1000000000