Implement a Leaky Bucket Rate Limiter
Company: Box
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
Implement a leaky bucket rate limiter.
You are given a class template for a rate limiter that controls whether incoming requests should be accepted or rejected. The limiter has:
- `capacity`: the maximum number of requests that can be waiting in the bucket.
- `leak_rate_per_second`: the number of requests that leave the bucket per second.
Design and implement a class with an API similar to:
```python
class LeakyBucketRateLimiter:
def __init__(self, capacity: int, leak_rate_per_second: float):
pass
def allow_request(self) -> bool:
pass
```
`allow_request()` should return:
- `True` if the request is accepted into the bucket.
- `False` if the bucket is already full after accounting for leaked requests.
Requirements:
1. First implement a single-threaded version.
2. Write tests for normal behavior, boundary cases, and time-based leakage.
3. Then extend the implementation so that it is safe when multiple threads call `allow_request()` concurrently.
4. Reuse as much of the original implementation as possible when adding thread-safety.
Quick Answer: This question evaluates understanding of rate-limiting algorithms, time-based state management, and concurrent programming concepts, including synchronization and test design for boundary and timing behaviors.
Part 1: Implement a Single-Threaded Leaky Bucket Rate Limiter
You are given the parameters of a leaky bucket rate limiter and a list of request arrival times in chronological order. The bucket starts empty.
For each request:
- First, let the bucket leak continuously based on the time elapsed since the previous request.
- Leakage amount = elapsed_time * leak_rate_per_second.
- The bucket level can never go below 0.
- If adding the new request would keep the bucket level at or below capacity, accept it and add 1 to the bucket.
- Otherwise, reject it.
Return a list of booleans where each element tells whether the corresponding request was accepted.
Note: The bucket level may become fractional because leakage is continuous.
Constraints
- 0 <= capacity <= 10^6
- 0.0 <= leak_rate_per_second <= 10^6
- 0 <= len(request_times) <= 2 * 10^5
- 0.0 <= request_times[i] <= 10^9
- request_times is in nondecreasing order
Examples
Input: (3, 1.0, [0.0, 0.2, 0.4, 1.4, 1.5])
Expected Output: [True, True, True, True, False]
Explanation: The bucket leaks between requests. The first four fit after accounting for leakage; the fifth arrives too soon and would exceed capacity.
Input: (2, 1.0, [0.0, 0.0, 1.0, 1.0])
Expected Output: [True, True, True, False]
Explanation: Two requests at time 0 fill the bucket. By time 1.0, one unit has leaked out, so one more request is accepted, but the next same-time request is rejected.
Hints
- Track the current bucket fill as a floating-point number and reduce it before handling each request.
- Even if a request is rejected, time has still passed, so the last processed timestamp should still be updated.
Part 2: Compute the Behavior of a Thread-Safe Leaky Bucket Rate Limiter
A single leaky bucket rate limiter is shared by multiple threads. You are given one call to allow_request() per array position:
- thread_ids[i] identifies which thread made the call.
- request_times[i] is the time when that call happened.
All calls operate on the same shared bucket.
A correct thread-safe implementation behaves as if each call acquires a single lock, updates the leaked amount, and then decides whether to accept the request. To make the result deterministic for this problem:
- Process calls in increasing order of request time.
- If two or more calls have the same timestamp, process them in their original input order.
- Return results in the original input order.
Each accepted request adds 1 to the bucket. Between processed calls, the bucket leaks continuously by elapsed_time * leak_rate_per_second, never dropping below 0.
Return a list of booleans indicating which calls are accepted.
Note: thread_ids are labels only; all threads share the same limiter state.
Constraints
- 0 <= capacity <= 10^6
- 0.0 <= leak_rate_per_second <= 10^6
- 0 <= len(thread_ids) == len(request_times) <= 2 * 10^5
- 0 <= thread_ids[i] <= 10^9
- 0.0 <= request_times[i] <= 10^9
- For equal timestamps, calls must be handled in original input order
Examples
Input: (2, 1.0, [10, 11, 12], [0.0, 0.0, 0.0])
Expected Output: [True, True, False]
Explanation: Three concurrent calls hit the same empty bucket with capacity 2. Only the first two can be accepted.
Input: (2, 1.0, [0, 1, 2, 3], [1.0, 0.0, 0.0, 1.0])
Expected Output: [True, True, True, False]
Explanation: Process times in order: indices 1 and 2 at time 0.0 are accepted; by time 1.0 one unit has leaked, so index 0 is accepted and index 3 is rejected.
Hints
- All threads share one bucket, so do not track state separately per thread.
- Sort requests by (timestamp, original_index), run the same leaky-bucket update as in the single-threaded version, and then write answers back to original positions.