Token Bucket Rate Limiter with Lazy Refill Backed by a Cache
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Token Bucket Rate Limiter with Lazy Refill Backed by a Cache
You are building the enforcement layer of a rate limiter. Every user has a **token bucket** stored in a key-value cache, keyed by `user_id`. A request from a user costs some number of tokens; the request is allowed only if the user's bucket currently holds at least that many tokens.
A token bucket is described by four fields:
| Field | Type | Meaning |
|---|---|---|
| `capacity` | integer | Maximum number of tokens the bucket can hold |
| `refill_rate` | float | Tokens added per second (continuous accrual) |
| `tokens` | float | Tokens currently in the bucket |
| `last_refill_ts` | float | Timestamp (in seconds) when `tokens` was last brought up to date |
The cache exposes two operations:
- `cache.get(user_id)` — returns the stored `TokenBucket` for `user_id`, or nothing if the user has no bucket yet.
- `cache.put(user_id, bucket)` — stores/overwrites the bucket for `user_id`.
There are **no background threads or timers** that refill buckets. All refilling must happen **lazily**, at the moment a bucket is touched.
Implement two functions:
1. `refill_token_bucket(bucket, now)`
Bring the bucket up to date as of time `now`:
- Add `(now - last_refill_ts) * refill_rate` tokens to the bucket.
- The token count must never exceed `capacity` (cap it).
- Set `last_refill_ts` to `now`.
2. `allow_request(cache, user_id, cost, now, default_capacity, default_refill_rate)`
Decide whether a request that costs `cost` tokens is allowed:
- Fetch the user's bucket from the cache. If the user has no bucket yet, create a **full** bucket (`tokens = default_capacity`) with the given `default_capacity` and `default_refill_rate`, and `last_refill_ts = now`.
- Lazily refill the bucket to time `now` using `refill_token_bucket`.
- If the refilled bucket has at least `cost` tokens, deduct `cost` tokens and return `true`.
- Otherwise leave the token count unchanged (apart from the refill) and return `false`.
- In **both** cases, write the updated bucket back to the cache before returning, so the refreshed state (tokens and `last_refill_ts`) is persisted.
Token accrual is continuous, so fractional token balances are valid. Compare with `tokens >= cost` when deciding.
## Example
A user's bucket has `capacity = 10`, `refill_rate = 2.0` tokens/second, and is full (`tokens = 10`) at time `t = 0`.
| Call | Refill result | Decision | Tokens after |
|---|---|---|---|
| `allow_request(cost=7, now=0.0)` | 10 (already current) | `true` | 3.0 |
| `allow_request(cost=5, now=1.0)` | 3 + 1.0 × 2 = 5.0 | `true` | 0.0 |
| `allow_request(cost=1, now=1.2)` | 0 + 0.2 × 2 = 0.4 | `false` | 0.4 |
| `allow_request(cost=1, now=1.5)` | 0.4 + 0.3 × 2 = 1.0 | `true` | 0.0 |
| `allow_request(cost=20, now=100.0)` | capped at 10.0 | `false` | 10.0 |
## Constraints
- `1 <= capacity <= 10^6`, `0 < refill_rate <= 10^5` tokens/second.
- `1 <= cost <= 10^6`.
- Timestamps passed for a given user are non-decreasing.
- Up to `10^5` calls total across all users.
- Assume single-threaded execution: you do not need to handle concurrent access to the cache in this exercise.
Quick Answer: This question evaluates understanding of token-bucket rate limiting, continuous time-based (fractional) token accrual, lazy refill semantics, and correctness of cache-backed state updates.
You are building the enforcement layer of a rate limiter. Every user has a **token bucket** stored in a key-value cache, keyed by `user_id`. A request costs some number of tokens and is allowed only if the user's bucket currently holds at least that many tokens.
A token bucket has four fields: `capacity` (int, max tokens), `refill_rate` (float, tokens added per second, continuous), `tokens` (float, current balance), and `last_refill_ts` (float, timestamp when `tokens` was last brought up to date).
There are **no background timers** — refilling happens **lazily**, the moment a bucket is touched.
Implement the rate limiter and drive it over a batch of requests. You are given `operations`, a list of `[user_id, cost, now]` triples processed in order (for any given user the `now` timestamps are non-decreasing), plus `default_capacity` and `default_refill_rate`.
For each operation:
1. **Fetch** the user's bucket. If the user has no bucket yet, create a **full** one (`tokens = default_capacity`) with the given defaults and `last_refill_ts = now`.
2. **Lazily refill**: add `(now - last_refill_ts) * refill_rate` tokens, cap the total at `capacity`, and set `last_refill_ts = now`.
3. **Decide**: if the refilled bucket holds at least `cost` tokens, deduct `cost` and the request is allowed; otherwise leave the balance unchanged (apart from the refill) and it is denied. Persist the refreshed bucket in **both** cases.
Return one entry per operation: `[allowed, tokens_after]`, where `allowed` is a boolean and `tokens_after` is the bucket's token balance after the request (rounded to 6 decimals). Compare with `tokens >= cost`; fractional balances are valid.
### Example
A user's bucket has `capacity = 10`, `refill_rate = 2.0`, full at `t = 0`:
| Call | Refill result | Decision | Tokens after |
|---|---|---|---|
| `cost=7, now=0.0` | 10 (already current) | allowed | 3.0 |
| `cost=5, now=1.0` | 3 + 1.0 x 2 = 5.0 | allowed | 0.0 |
| `cost=1, now=1.2` | 0 + 0.2 x 2 = 0.4 | denied | 0.4 |
| `cost=1, now=1.5` | 0.4 + 0.3 x 2 = 1.0 | allowed | 0.0 |
| `cost=20, now=100.0` | capped at 10.0 | denied | 10.0 |
Constraints
- 1 <= capacity <= 10^6
- 0 < refill_rate <= 10^5 tokens/second
- 1 <= cost <= 10^6
- For a given user, the `now` timestamps are non-decreasing.
- Up to 10^5 operations total across all users.
- Single-threaded: no concurrent access to the cache.
- Token accrual is continuous; fractional balances are valid (compare with tokens >= cost).
Examples
Input: ([[1, 7, 0.0], [1, 5, 1.0], [1, 1, 1.2], [1, 1, 1.5], [1, 20, 100.0]], 10, 2.0)
Expected Output: [[True, 3.0], [True, 0.0], [False, 0.4], [True, 0.0], [False, 10.0]]
Explanation: The worked example. User 1 (default capacity 10, refill 2.0/s): starts full at t=0 -> spend 7 (3 left); at t=1 accrue 2 -> 5, spend 5 (0 left); at t=1.2 accrue 0.4, cost 1 denied (0.4 left); at t=1.5 accrue 0.6 -> 1.0, spend 1 (0 left); at t=100 refill is capped at capacity 10, cost 20 denied (10 left).
Input: ([], 10, 2.0)
Expected Output: []
Explanation: No operations -> empty result. Edge case: empty batch.
Hints
- Refill lazily: when you touch a bucket at time `now`, add `(now - last_refill_ts) * refill_rate` tokens, cap the total at `capacity`, then set `last_refill_ts = now`. There is no background timer.
- A brand-new user should start with a FULL bucket and `last_refill_ts = now`, so its first refill adds zero tokens (elapsed time is 0).
- Persist the refreshed bucket back to the cache on BOTH allow and deny paths - the updated `last_refill_ts` (and accrued tokens) must survive to the next request even when the request is denied.
- Compare with `tokens >= cost` (not `>`), and only deduct `cost` when the request is allowed.