Token-Bucket Rate Limiter
Implement a token-bucket rate limiter, TokenBucket(capacity, rate). Time is passed in explicitly, so nothing here depends on the clock.
Each key starts with a full bucket of capacity tokens the first time it is seen. Tokens refill continuously at rate per unit of time, never exceeding capacity. allow(key, now, cost = 1) refills the bucket to now, then admits and deducts cost if at least cost tokens are available; a rejected request keeps its (refilled) balance. Keys are independent.
bucket = TokenBucket(3, 1)
bucket.allow("k", 0); bucket.allow("k", 0); bucket.allow("k", 0) -> true, true, true
bucket.allow("k", 0) -> false
bucket.allow("k", 1) -> true // one token refilled
bucket.allow("k", 100, 2) -> true // back at capacity, cost 2Hints
Hint 1
Store (tokens, lastSeen) per key. Refill lazily on each call with min(capacity, tokens + (now − lastSeen) × rate), then compare against the cost.
Hint 2
A rejected call still updates lastSeen to now, keeping the refilled balance — otherwise the same elapsed time would be credited twice.