Rate Limiter (Token Bucket)
Advanced
Design a rate limiter using the token bucket algorithm. Implement a RateLimiter class that:
- Allows up to
capacityrequests within awindowtime window - Issues tokens at a constant rate
- Rejects requests when no tokens are available
- Tracks the last refill time to compute available tokens
Write methods:
__init__(capacity, refill_rate): capacity tokens, refill_rate tokens per secondis_allowed(tokens_needed=1): returns True if tokens are available, False otherwiserefill(): issue new tokens based on elapsed time
Constraints
- O(1) time per request
- Handle concurrent requests safely (optional: use threading locks if needed)
Hints
Hint 1
Track the last refill timestamp and compute elapsed time since then.
Hint 2
Each request consumes tokens; refill calculates new tokens based on elapsed seconds.
Keywords
dsa
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.