Token-bucket rate limiter
Python data engineering interview problem. Difficulty: intermediate. Pattern: OOP. About 16 minutes. Part of the Pro drill bank.
Implement a token-bucket rate limiter class supporting fractional refills and clock jump handling. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.
Implement a TokenBucket class that regulates access to a shared resource using the token-bucket algorithm: TokenBucket(rate: float, capacity: float): Initializes the rate limiter with a refill rate of rate tokens per second and a maximum bucket volume of capacity tokens. The bucket starts completely full. allow(tokens: float = 1.0, now: float = None) -> bool: Checks whether tokens can be consumed. If now is specified, use that timestamp (in seconds); otherwise use the system clock. Add tokens accrued since the previous invocation: elapsed * rate, capped at capacity. If time moved backwards (now < last_time), treat elapsed time as 0. If the bucket holds at least tokens, subtract tokens and return True. Otherwise, return False without deducting tokens.
Requirements
- Bucket starts full at capacity.
- Tokens never exceed capacity.
Constraints
- rate > 0 and capacity > 0
- tokens >= 0
Examples
Input: [tb := TokenBucket(rate=2, capacity=5), tb.allow(3, now=0), tb.allow(3, now=0), tb.allow(2, now=1)][1:] Output: [True, False, True] At t=0, bucket has 5 tokens; 3 are taken leaving 2. Second request for 3 fails. At t=1, 2 tokens refill (total 4), allowing 2 to be taken.
Topics: lakebench, python, stateful, rate-limiting.
More Python interview questions · All interview problems · Learn data engineering
Token-bucket rate limiter
Interview-style drill: Implement a token-bucket rate limiter class supporting fractional refills and clock jump handling.
Implement a `TokenBucket` class that regulates access to a shared resource using the token-bucket algorithm: - `TokenBucket(rate: float, capacity: float)`: Initializes the rate limiter with a refill rate of `rate` tokens per second and a maximum bucket volume of `capacity` tokens. The bucket starts completely full. - `allow(tokens: float = 1.0, now: float = None) -> bool`: Checks whether `tokens` can be consumed. - If `now` is specified, use that timestamp (in seconds); otherwise use the system clock. - Add tokens accrued since the previous invocation: `elapsed * rate`, capped at `capacity`. - If time moved backwards (`now < last_time`), treat elapsed time as 0. - If the bucket holds at least `tokens`, subtract `tokens` and return `True`. Otherwise, return `False` without deducting tokens.