Your question is Rate Limiter for Burst Traffic. 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.
Quantcast APIs can receive short traffic bursts that should be tolerated without allowing sustained overload. Implement a per-client token bucket rate limiter for a chronologically ordered request stream.
Each client has a bucket with a maximum capacity of capacity tokens. Initially, every client's bucket is full. Tokens are replenished continuously at refill_rate tokens per second, but the bucket cannot exceed its capacity. Processing one request consumes one token. A request is allowed only when its client's bucket contains at least one token after replenishment.
Implement rate_limit(requests, capacity, refill_rate), where requests is a list of [timestamp, client_id] pairs. timestamp is a nonnegative number of seconds, and client_id is a string. Return a list of booleans in request order, where True means allowed and False means rejected. Requests are globally ordered by nondecreasing timestamp. Each client's state must be independent.
def rate_limit(requests, capacity, refill_rate):