Design a Rate Limiter Using Token Bucket Algorithm

Problem

Implement a Rate Limiter using the Token Bucket algorithm.

Requirements

• RateLimiter(capacity, refillRatePerSecond) — constructor
• allowRequest(userId, timestamp) — returns true if request is within rate limit
• Each user has their own bucket
• Buckets refill continuously (not in discrete ticks)

Example

limiter = RateLimiter(10, 1)  -- capacity 10, refill 1/sec
limiter.allowRequest("u1", 0)   → true  (tokens: 9)
limiter.allowRequest("u1", 0)   → true  (tokens: 8)
... (10 calls at t=0) ...
limiter.allowRequest("u1", 0)   → false (tokens: 0)
limiter.allowRequest("u1", 1)   → true  (tokens refilled)

Evaluation criteria

• No clock dependency (use passed timestamp)
• Thread-safe implementation
• O(1) per request
• Clean separation of RateLimiter vs TokenBucket classes