Sliding Window Rate Limiter
Mercury● MediumFULLTIMEPHONE SCREENProblem statement
You receive payment-transfer API requests in nondecreasing timestamp order. Each request has an organization identifier.
For each request at time t, allow it when fewer than limit previously allowed requests for the same organization have timestamps strictly greater than t - windowSize. A previously allowed request exactly windowSize milliseconds old has expired. Rejected requests do not consume capacity.
Return an array with 1 for every allowed request and 0 for every rejected request, preserving input order.
Function
allowedRequests(organizationIds: int[], timestamps: int[], limit: int, windowSize: int) → int[]Examples
Example 1
organizationIds = [1,1,1,1]timestamps = [0,2,5,10]limit = 2windowSize = 10return = [1,1,0,1]The requests at times 0 and 2 fill the window. The request at 5 is rejected. At time 10, the accepted request at time 0 has expired, so the request is allowed.
Example 2
organizationIds = [7,8,7,8,7]timestamps = [1,1,2,3,4]limit = 1windowSize = 3return = [1,1,0,0,1]Each organization has an independent window. The second request for each organization is rejected. At time 4, organization 7 may proceed because its accepted request at time 1 is exactly one window old.
Example 3
organizationIds = [3,3,3,3]timestamps = [5,5,5,5]limit = 3windowSize = 100return = [1,1,1,0]Equal timestamps are processed in input order. The first three requests are accepted and the fourth is rejected.
Constraints
1 ≤ organizationIds.length = timestamps.length ≤ 2 * 10^5.1 ≤ organizationIds[i] ≤ 10^9.0 ≤ timestamps[i] ≤ 10^9, andtimestampsis nondecreasing.1 ≤ limit ≤ 10^5.1 ≤ windowSize ≤ 10^9.