Implement Rate Limiter Algorithm | Dataford Interview Questions

Your question is Implement Rate Limiter Algorithm. Start with the requirements on the right.

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

Problem

Datadog API ingestion endpoints must limit each client to a fixed number of requests during a rolling time window. Given requests in nondecreasing timestamp order, determine whether each request should be accepted.

Implement a per-client sliding-window rate limiter. A request is accepted when that client has made fewer than limit accepted requests in the interval (timestamp - window, timestamp]. Rejected requests do not count toward future limits.

Formal Specification

Implement rate_limit(requests, limit, window), where:

requests is a list of two-element lists [client_id, timestamp].
client_id is a string.
timestamp is an integer representing seconds.
limit and window are positive integers.
Requests are sorted by nondecreasing timestamp.
Return a list of booleans in request order. True means accepted, and False means rejected.

Use an efficient data structure so processing each request does not require scanning all previous requests.

Constraints

1 <= len(requests) <= 10^5
1 <= limit <= 10^9
1 <= window <= 10^9
Each request is [client_id, timestamp]
1 <= len(client_id) <= cien
0 <= timestamp <= 10^9
Requests are sorted by nondecreasing timestamp

Function Signature

def rate_limit(requests, limit, window):