Thread-Safe High-Concurrency Rate Limiter | Dataford Interview Questions

Implement a thread-safe rate limiter that can handle thousands of concurrent network requests.

Implement a per-key sliding-window limiter. Each request has a key and timestamp, and the limiter must atomically decide whether to accept it while allowing at most limit accepted requests for that key during any window-second interval. The grading contract is rate_limit(requests, limit, window), where requests is an ordered list of [key, timestamp] pairs and the result is a Boolean list. Your implementation must include a reusable thread-safe limiter object internally; timestamps for each key are nondecreasing.

Constraints

1 <= limit <= 10^6
1 <= window <= 10^9
1 <= len(requests) <= 10^5
Each request is a two-element pair [key, timestamp]
Keys are nonempty strings
Timestamps are integers and are nondecreasing for each key
A request at timestamp t counts requests with timestamps in [t - window, t]

Function Signature

def rate_limit(requests, limit, window):

Your question is Thread-Safe High-Concurrency Rate Limiter. 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

Implement a thread-safe rate limiter that can handle thousands of concurrent network requests.

Constraints

1 <= limit <= 10^6
1 <= window <= 10^9
1 <= len(requests) <= 10^5
Each request is a two-element pair [key, timestamp]
Keys are nonempty strings
Timestamps are integers and are nondecreasing for each key
A request at timestamp t counts requests with timestamps in [t - window, t]

Function Signature

def rate_limit(requests, limit, window):

Your question is Thread-Safe High-Concurrency Rate Limiter. 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.