A token bucket allows short bursts while enforcing a long-run request rate. It holds at most capacity tokens, refills at refillRate tokens per second, and charges one token for every allowed request.
Design a TokenBucketRateLimiter class:
TokenBucketRateLimiter(int capacity, int refillRate) creates a full bucket.boolean allow(int timestamp) processes one request and returns whether it is allowed.
Timestamps supplied to one object are non-decreasing integer seconds. Before every request after the first, add:
Cap the result at capacity. If at least one token is available, subtract one and return true. Otherwise, return false without changing the token count. In either case, remember the request's timestamp.
Example 1:
Input:
Output:
Explanation: The full bucket contains two tokens. No time passes between requests, so the first two consume the available tokens and the next two are denied.
Example 2:
Input:
Output:
Explanation: One second passes between requests, so the bucket receives one replacement token before each decision.
Constraints
1 <= capacity <= 10^91 <= refillRate <= 10^60 <= timestamp <= 10^6- Timestamps passed to one object are non-decreasing.
- At most
10^5 calls are made to allow. - The bucket starts full; the first timestamp does not refill it from time zero.
Design a Token Bucket Rate Limitermedium