Implement a token bucket rate limiter for an HTTP request stream.
The token bucket works as follows:
capacity tokensrate tokens per secondcapacity tokens)Implement the TokenBucket class:
__init__(self, rate: float, capacity: int) — initializes the bucket with the given refill rate and capacityisRequestAllowed(self, timestamp: float) -> bool — given the timestamp (in seconds) of an incoming request, return True if the request is allowed, False otherwiseisRequestAllowed must run in O(1) time and space.
Example 1:
Input: rate = 1.0, capacity = 1, requests = [0.0]
Output: [True]
Explanation: Bucket starts full with 1 token. The request at t=0.0 consumes it — allowed.
Example 2:
Input: rate = 1.0, capacity = 1, requests = [0.0, 0.5]
Output: [True, False]
Explanation: First request consumes the only token. At t=0.5, only 0.5 tokens have refilled — not enough.
Example 3:
Input: rate = 1.0, capacity = 1, requests = [0.0, 1.0]
Output: [True, True]
Explanation: First request consumes the token. By t=1.0, exactly 1 token has refilled — second request allowed.
Constraints:
0 < rate <= 1e6 (tokens per second)1 <= capacity <= 10^5