Your question is Implement Token Rate Limiter. 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.
Microsoft Teams services need to limit requests independently for each client. Implement a token-bucket rate limiter that processes requests in chronological order and determines whether each request is accepted.
Each client has a bucket with a fixed capacity. A bucket starts full and refills at refill_rate tokens per unit of time, up to its capacity. Every request costs exactly one token. A request is accepted if its client's bucket contains at least one token after refilling, and accepted requests consume one token. Rejected requests do not consume tokens, but time still advances for future refills.
Implement rate_limit(requests, capacity, refill_rate), where requests is a list of two-element lists [client_id, timestamp]. Timestamps are nonnegative integers and requests are ordered by nondecreasing timestamp. Return a Boolean list whose element at index i indicates whether request i was accepted.
client_id values are strings. capacity and refill_rate are positive integers. Each client bucket is created with capacity tokens when that client first appears.
def rate_limit(requests, capacity, refill_rate):