Your question is Leaky 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.
Box API traffic must be throttled so bursts do not overwhelm downstream services. Implement a leaky bucket rate limiter that processes request timestamps in chronological order and determines whether each request is accepted or rejected.
The bucket has a maximum capacity measured in requests. Requests enter the bucket one at a time. Between two request timestamps, the bucket leaks at a constant rate. A request is accepted only if adding it would not make the current bucket level exceed capacity; otherwise, it is rejected. Rejected requests do not increase the bucket level, but time continues to pass and the bucket continues to drain.
Implement rejected_requests(timestamps, capacity, leak_rate). timestamps is a nondecreasing list of integers representing seconds since an arbitrary origin. capacity and leak_rate are positive integers. Return a Boolean list where element i is True if the request at timestamps[i] is rejected, and False otherwise.
The bucket starts empty. At time t, first subtract leak_rate * (t - previous_time) from the bucket level, never allowing the level below zero.
def rejected_requests(timestamps, capacity, leak_rate):