Per-Client Sliding-Window Rate Limiter
CVS Health● MediumFULLTIMEPHONE SCREENProblem statement
Build a rate limiter that limits each client separately. A client may have at most limit allowed requests in any time window of length windowSize.
Requests arrive in order: request i comes from clients[i] at time timestamps[i]. A request at time t is allowed if the same client has fewer than limit earlier allowed requests with a time in the window (t - windowSize, t]. A request at exactly t - windowSize is outside the window. Rejected requests do not count toward the limit.
Return, for each request, whether it is allowed.
Function
allowRequests(limit: int, windowSize: int, clients: String[], timestamps: int[]) → boolean[]Examples
Example 1
limit = 2windowSize = 10clients = ["a","a","b","a","a"]timestamps = [1,2,3,5,11]return = [true,true,true,false,true]Client a may make 2 requests in any 10-unit window. Its requests at 1 and 2 are allowed. Client b has its own limit, so its request at 3 is allowed. At 5, client a already has 2 allowed requests in the window (1 and 2), so it is rejected. At 11, the window covers times 2 through 11, so only the request at 2 counts and the request is allowed.
Example 2
limit = 1windowSize = 5clients = ["x","x","x"]timestamps = [0,4,5]return = [true,false,true]The request at 0 is allowed. At 4, the request at 0 is still inside the window, so it is rejected. At 5, the window covers times 1 through 5, the request at 0 has left it, and the rejected request at 4 never counted, so the request is allowed.
Constraints
1 <= limit <= 1001 <= windowSize <= 10^91 <= clients.length <= 1000andtimestamps.length == clients.length- Each client id is 1 to 8 lowercase English letters or digits.
0 <= timestamps[i] <= 10^9, andtimestampsnever decreases.