Sliding-Window API Rate Limiter
Patreon● MediumFULLTIMEPHONE SCREENProblem statement
An in-memory rate limiter permits at most limit accepted requests in the rolling one-second window ending at each request timestamp. Timestamps are integer milliseconds in nondecreasing order.
Before deciding a request at time t, discard accepted requests with timestamp at most t - 1000. Accept the current request when fewer than limit accepted timestamps remain. Rejected requests do not consume capacity. Return one decision per request.
Function
allowRequests(limit: int, timestamps: int[]) → boolean[]Examples
Example 1
limit = 3timestamps = [0,100,200,300,1000,1001]return = [true,true,true,false,true,false]The fourth request is rejected. At time 1000, the accepted request at time 0 expires, so the fifth request is accepted. At time 1001, three accepted requests remain in the rolling window, so the sixth is rejected.
Example 2
limit = 1timestamps = [5,5,1004,1005]return = [true,false,false,true]The rejected duplicate at time 5 does not consume capacity; the accepted request expires only when the timestamp reaches 1005.
Constraints
1 <= limit <= 10^5.1 <= timestamps.length <= 10^5.0 <= timestamps[i] <= 2^31 - 1.- Timestamps are nondecreasing.