Rate Limiter in Concurrency | Dataford Interview Questions

How do you implement the rate limiter handling multi-threading and concurrency?

Asked in the technical phone screen stage. Implement a thread-safe, per-client sliding-window rate limiter. The limiter allows at most limit requests from each client during any window_seconds interval.

Input and Output

Implement rate_limit_requests(requests, limit, window_seconds), where requests is a list of [client_id, timestamp] pairs. Process requests in order and return a Boolean list indicating whether each request is accepted. The underlying limiter must protect shared state with synchronization so its allow method can safely be called by multiple threads.

Constraints

0 <= len(requests) <= 300
1 <= limit <= 10^6
1 <= window_seconds <= 10^9
Client timestamps are nondecreasing in request order
A timestamp exactly window_seconds old is expired

Function Signature

def rate_limit_requests(requests, limit, window_seconds):

Your question is Rate Limiter in Concurrency. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem