Tokens - Implement a Token Bucket Rate Limiter

Question

## Round 1 - Coding / OOD

## Problem

Implement a token bucket rate limiter. Each bucket refills at a constant rate (tokens per second) up to a maximum capacity. A request consumes one token; if the bucket is empty the request is rejected.

```python
class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        # capacity: max tokens; refill_rate: tokens added per second
        pass

def allow_request(self, current_time: float) -> bool:
        # Returns True if a token is available (and consumes it), else False
        pass
```

## Example

```
bucket = TokenBucket(capacity=5, refill_rate=2.0)  # 2 tokens/sec

bucket.allow_request(t=0.0)   # -> True  (tokens: 4)
bucket.allow_request(t=0.0)   # -> True  (tokens: 3)
bucket.allow_request(t=0.0)   # -> True  (tokens: 2)
bucket.allow_request(t=0.0)   # -> True  (tokens: 1)
bucket.allow_request(t=0.0)   # -> True  (tokens: 0)
bucket.allow_request(t=0.0)   # -> False (empty)
bucket.allow_request(t=1.0)   # -> True  (refilled 2; consumed 1 -> tokens: 1)
```

## Follow-ups

1. How do you make this thread-safe for concurrent requests?
2. How do you implement a per-user rate limiter using a dict of buckets with LRU eviction?
3. How does token bucket differ from a leaky bucket and sliding window algorithms?
4. How would you distribute this rate limiter across multiple API servers sharing state in Redis?

Tokens - Implement a Token Bucket Rate Limiter

Question Details

Full Details

About This Question

Topics

More Flexport Interview Questions