Rate Limit an API During a Traffic Attack

You need to implement a rate limiter that protects a web API from being overwhelmed by too many requests from the same client. The limiter uses a per‑client token bucket algorithm:

• Each client is assigned an independent bucket.
• A bucket holds at most capacity tokens. It starts full.
• Tokens are added continuously at a rate of refillRate tokens per second. The bucket never exceeds its capacity.
• A request costs one token. If the bucket has at least 1.0 tokens when the request arrives, one token is consumed and the request is allowed; otherwise the request is rejected.

Implement the RateLimiter class:

• RateLimiter(int capacity, int refillRate) – initialises the limiter with the given bucket capacity and token refill rate (tokens/second).
• boolean allow(String clientId, double timestamp) – returns true if the request from clientId at the given timestamp (in seconds) should be allowed, and false otherwise. The timestamp is guaranteed to be non‑decreasing across all calls.

You may assume that the total number of calls to allow does not exceed $10^{5}$.

Example 1:

Input:
RateLimiter limiter = new RateLimiter(2, 1);
limiter.allow("A", 0.0);   // true
limiter.allow("A", 0.5);   // true
limiter.allow("A", 1.0);   // true
limiter.allow("A", 1.2);   // false
limiter.allow("A", 1.5);   // false
limiter.allow("A", 2.0);   // true

Output: [true, true, true, false, false, true]

Explanation:

• t=0.0: bucket starts with 2 tokens → consume 1, left 1.0.
• t=0.5: elapsed = 0.5 s → refill = 0.5 token, bucket becomes min(2, 1.0+0.5)=1.5 → allowed, left 0.5.
• t=1.0: elapsed = 0.5 s → refill 0.5, bucket = min(2, 0.5+0.5)=1.0 → allowed, left 0.0.
• t=1.2: elapsed = 0.2 s → refill 0.2, bucket = 0.2 < 1 → rejected.
• t=1.5: elapsed = 0.3 s → refill 0.3, bucket = 0.5 < 1 → rejected.
• t=2.0: elapsed = 0.5 s → refill 0.5, bucket = 1.0 → allowed, left 0.0.

Example 2:

Input:
RateLimiter limiter = new RateLimiter(5, 2);
limiter.allow("B", 1.0);   // true
limiter.allow("C", 1.0);   // true
limiter.allow("B", 1.3);   // true
limiter.allow("B", 2.1);   // true
limiter.allow("B", 2.5);   // true
limiter.allow("B", 2.6);   // false
limiter.allow("B", 3.0);   // true

Output: [true, true, true, true, true, false, true]

Explanation:

• Client B starts with 5 tokens. After t=1.0 (1 token used) and t=1.3 (refill 0.6, consumes 1) the bucket stays comfortably positive. At t=2.1 a refill of 1.6 brings it back to 5, then it drains quickly.
• At t=2.6 the bucket is empty → rejected. By t=3.0 enough tokens have been refilled to allow the next request.

Example 3:

Input:
RateLimiter limiter = new RateLimiter(1, 10);
limiter.allow("D", 0.0);   // true
limiter.allow("D", 0.09);  // false
limiter.allow("D", 0.11);  // true

Output: [true, false, true]

Constraints:

• 1 <= capacity <= 10⁴
• 1 <= refillRate <= 10⁴
• 0.0 <= timestamp <= 10⁹, provided in non‑decreasing order
• At most $10^{5}$ calls to allow
• The bucket state is allowed to be maintained with floating‑point precision; exact equality comparisons are not required – test cases use a tolerance of 1e-6 when evaluating token counts.