Token Bucket Rate Limiter
Description
An API gateway protects a backend with a token bucket. The bucket holds at most capacity tokens, starts full at time 0, and refills continuously at refillPerSecond tokens per second, so a request arriving at time t has access to every token refilled up to t. A request that finds at least one token is allowed and consumes one token; a request that finds fewer than one token is denied and consumes nothing. Tokens never exceed capacity. Given capacity, refillPerSecond, and timestamps (the arrival time of each request in whole seconds, in non-decreasing order), return one boolean per request: true if it was allowed and false if it was denied.
Examples
capacity = 2, refillPerSecond = 1, timestamps = [0,0,0,1,3][true,true,false,true,true]The bucket starts with 2 tokens. The first two requests at time 0 each take one, leaving none, so the third request at time 0 is denied. By time 1 one token has been refilled, so that request is allowed and the bucket is empty again. Between time 1 and time 3 two tokens are refilled, so the last request is allowed.
capacity = 1, refillPerSecond = 2, timestamps = [0,0,1,1,1][true,false,true,false,false]With capacity 1 only one token can ever be held. The first request takes it and the second request at time 0 is denied. By time 1 the refill of 2 tokens is capped at 1, which the third request takes. The two remaining requests at time 1 find an empty bucket and are denied.
capacity = 3, refillPerSecond = 0, timestamps = [5,6,7,8][true,true,true,false]With no refill the bucket only ever holds its initial 3 tokens. The first three requests each take one and the fourth request finds the bucket empty, so it is denied no matter how much time passes.
Constraints
- •
1 ≤ capacity ≤ 10⁴ - •
0 ≤ refillPerSecond ≤ 10⁴ - •
1 ≤ timestamps.length ≤ 10⁴ - •
0 ≤ timestamps[i] ≤ 10⁹ - •
timestamps is non-decreasing
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.