How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Box.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Box during technical interviews.

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.

Input: (1, 0.5, [0.0, 1.0, 2.0])

Expected Output: [True, False, True]

Explanation: After 1 second, only 0.5 has leaked, so the second request is rejected. After another second, the bucket drains enough for the third request.

Input: (4, 2.0, [])

Expected Output: []

Explanation: Edge case: no requests.

Input: (0, 3.0, [0.0, 0.5])

Expected Output: [False, False]

Explanation: Edge case: a bucket with capacity 0 can never accept any request.

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.

Input: (1, 0.5, [0, 1, 2], [2.0, 0.0, 1.0])

Expected Output: [True, True, False]

Explanation: Chronological order is index 1, then 2, then 0. The middle request is rejected because only half a unit leaked since the first accepted request.

Input: (3, 5.0, [], [])

Expected Output: []

Explanation: Edge case: no calls from any thread.

Input: (0, 100.0, [7, 8], [0.0, 0.0])

Expected Output: [False, False]

Explanation: Edge case: capacity 0 means every concurrent call 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.

Quick Overview

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.