Per-Client Sliding-Window Rate Limiter
Learn this problem
General MotorsFULLTIMEOAProblem statement
Process an ordered batch of requests through a per-client sliding-window rate limiter. Request i belongs to clientIds[i] and arrives at timestamps[i].
For this exercise, assume the batch is processed by one limiter in nondecreasing timestamp order. Before deciding a request at time timestamp, expire that client's accepted requests whose times are at most timestamp - windowSeconds. Accept the request when fewer than maxRequests accepted requests remain for that client. Record only accepted requests; a rejected request does not consume future capacity.
Clients are independent. Requests with the same timestamp are processed in input order. Return one boolean decision for every request, in the original order.
Function
allowRequests(clientIds: String[], timestamps: int[], maxRequests: int, windowSeconds: int) → boolean[]Examples
Example 1
clientIds = ["A","A","A","A","B"]timestamps = [0,1,2,3,3]maxRequests = 3windowSeconds = 10return = [true,true,true,false,true]Client A fills its window with accepted requests at times 0, 1, and 2, so its request at time 3 is rejected. Client B has independent capacity and its request is accepted.
Example 2
clientIds = ["x","x","x","x","x"]timestamps = [0,0,1,3,3]maxRequests = 2windowSeconds = 3return = [true,true,false,true,true]The first two requests fill the window and the request at time 1 is rejected without consuming capacity. At time 3, both accepted requests from time 0 are exactly at the expiration boundary and leave the window before the two new requests are processed.
Constraints
1 <= clientIds.length <= 100000.clientIds.length == timestamps.length.- Each client ID is a nonempty printable ASCII string of length at most
50. 0 <= timestamps[i] <= 10^9.timestampsis nondecreasing.1 <= maxRequests <= 100000.1 <= windowSeconds <= 10^9.