coding•Data Structures & Algorithms•Distributed Systems & API Rate Limiting
Distributed Rate Limiting: Token Bucket Algorithm with Redis
Problem Statement
Implement an in-memory **Token Bucket Rate Limiter**:
A bucket has a maximum capacity of `max_tokens` and refills at a constant rate of `refill_rate` tokens per second.
Initially at timestamp 0, the bucket is completely full with `max_tokens` tokens.
When a request arrives at timestamp `t` requesting `tokens_needed`:
1. Calculate tokens generated since the last request: $\Delta t \times \text{refill\_rate}$.
2. Refill the bucket up to at most `max_tokens`.
3. If current tokens $\ge$ `tokens_needed`, approve the request (`true`) and deduct tokens.
4. Otherwise, reject the request (`false`) without deducting tokens.
### Input Format
- First line contains two floats: `max_tokens` and `refill_rate`.
- Second line contains an integer `n` (number of requests).
- The next `n` lines each contain two floats: `timestamp` and `tokens_needed`.
### Output Format
- Print space-separated boolean results (`true` or `false`) for each request.
### Constraints
- `1 <= max_tokens <= 10^6`
- `0.1 <= refill_rate <= 10^5`
- Requests arrive in non-decreasing order of timestamp.
Sample Cases
Example 1Sample Case
Input: 10 2
2
0 8
0 3
Output: true false
Example 2Sample Case
Input: 10 2
2
0 8
1 5
Output: true false
Example 3Sample Case
Input: 5 1
2
0 4
0 2
Output: true false
Example 4Sample Case
Input: 5 1
2
0 5
5 5
Output: true true
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.