Dropped Requests (Rate Limiter)
Examples
Example 1:
Input: requestTimes = [1,1,1,1,2,2,2,2,3]
Output: [1,2]
Explanation:
Example 2:
Input: requestTimes = [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8]
Output: [7,8]
Explanation:
Example 1:
Input: requestTimes = [1,1,1,1,2,2,2,2,3]
Output: [1,2]
Explanation:
Example 2:
Input: requestTimes = [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8]
Output: [7,8]
Explanation:
Your social media site is receiving a surge of traffic. You apply a rate limiter and now need to report which requests were dropped.
Given a non-decreasing array requestTimes, where requestTimes[i] is the arrival time (in seconds) of the i-th request, return an array of timestamps for dropped requests in the order they are dropped.
A request is dropped if it violates either rule:
3 requests in the same second.20 requests in any rolling 10-second window.If a request violates both rules, include it only once in the output.
The 4th request at time 1 is dropped. The 4th request at time 2 is also dropped.
The request at index 20 (time 7) is the 21st request inside a 10-second span, so it is dropped. The next request at time 8 is dropped for the same 10-second rule.
1 <= requestTimes.length <= 2 * 10^51 <= requestTimes[i] <= 10^9requestTimes is in non-decreasing order