Sliding-Window Rate Limiter
Bloomberg LP● MediumNEW GRADPHONE SCREENProblem statement
A rate limiter allows at most n requests during any interval of t integer seconds. Process the nondecreasing array timestamps in order and return whether each request is allowed.
For a request at time x, consider previously allowed requests whose timestamps are in the inclusive interval [x - t + 1, x]. Allow the new request exactly when that interval currently contains fewer than n allowed requests. A rejected request is not retained and does not affect later decisions.
Function
rateLimitRequests(n: int, t: int, timestamps: int[]) → boolean[]Examples
Example 1
n = 3t = 5timestamps = [1,1,2,3,8]return = [true,true,true,false,true]The first three requests fill the window. Time 3 is rejected; by time 8, all earlier accepted requests have expired.
Example 2
n = 1t = 3timestamps = [1,2,4,4]return = [true,false,true,false]The rejected request at time 2 is not counted. The request at time 1 expires before time 4, so the first time-4 request is allowed.
Example 3
n = 2t = 2timestamps = [5,5,6,7]return = [true,true,false,true]Both time-5 requests are active at time 6, so that request is rejected. They expire before time 7.
Constraints
1 <= n <= 100000.1 <= t <= 1000000000.1 <= timestamps.length <= 100000.0 <= timestamps[i] <= 1000000000.timestampsis nondecreasing.