Sliding Window Rate Limiter
An API allows at most limit accepted requests in any window of windowSize seconds. Requests arrive at the times in timestamps (sorted, non-decreasing, may repeat).
A request at time t is accepted if fewer than limit previously accepted requests have a time greater than t - windowSize. Rejected requests do not count against the limit. Return an array of booleans, one per request, saying whether it was accepted.
Example 1
Input: timestamps = [1,2,3,4,5], limit = 2, windowSize = 3 Output: [true,true,false,true,true] Explanation: At t=3 the window (0,3] already holds the accepted requests at 1 and 2.
Example 2
Input: timestamps = [1,1,1,1], limit = 3, windowSize = 10 Output: [true,true,true,false]
Constraints
- 0 <= timestamps.length <= 10^5
- 0 <= timestamps[i] <= 10^9
- 0 <= limit <= 10^5
- 1 <= windowSize <= 10^9
Hint 1
Keep a queue of accepted request times.
Hint 2
Before deciding on a request, drop times from the front that have fallen out of the window.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Site Reliability Engineer, Cloud Engineer, DevOps Engineer, Full Stack Developer
Run checks your code on 3 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.