Description
Company: Snowflake
Problem Overview
Imagine your website is getting too many visitors at once. To handle the load, you turn on a rate limiter. Now, you need to identify exactly which requests were blocked.
You are given an array called requestTimes. This array lists the arrival time (in seconds) for every request. The times are sorted in non-decreasing order (earliest to latest).
Your goal is to return a new array containing the timestamps of the requests that were blocked.
A request is blocked if it breaks either of these two rules:
- Rule 1: There are more than 3 requests happening in the same second.
- Rule 2: There are more than 20 requests happening in any 10-second rolling window.
If a request breaks both rules at the same time, simply list it once in your output.
Illustrative Examples
Example 1:
Input: requestTimes = [1,1,1,1,2,2,2,2,3]
Output: [1,2]
Breakdown: The system allows 3 requests at second 1. The 4th request arrives at second 1, so it is blocked. Later, the 4th request at second 2 is also blocked.
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]
Breakdown: The request at index 20 (which arrives at second 7) is the 21st request within a 10-second period. Because the limit is 20, this request is blocked. The next request at second 8 is also blocked for the same reason.
Input Limits
- 1 <= requestTimes.length <= 2 * 10^5
- 1 <= requestTimes[i] <= 10^9
- requestTimes is sorted in non-decreasing order.