FastPrep
Problem · Array

Count Dropped Rate-Limited Requests

Learn this problem
● MediumOracle logoOracleFULLTIMEONSITE INTERVIEW

Problem statement

You are given a nondecreasing array requestTimes, where each value is the integer second when one request arrives. Process requests in array order. A request is dropped if accepting it would exceed any of these limits:

  • At most 3 requests in one second.
  • At most 20 requests in any rolling 10-second interval.
  • At most 60 requests in any rolling 60-second interval.

For a request at second t, the rolling intervals are [t - 9, t] and [t - 59, t], respectively. Dropped requests still count when evaluating every later limit. If multiple limits reject the same request, count that request only once.

Return the total number of dropped requests.

Function

countDroppedRequests(requestTimes: int[]) → int

Examples

Example 1

requestTimes = [1,1,1,1]return = 1

The fourth request at second 1 exceeds the three-per-second limit.

Example 2

requestTimes = [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7]return = 1

The first twenty requests fit in the rolling ten-second interval. The twenty-first request is dropped.

Example 3

requestTimes = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,60]return = 1

The final request is the sixty-first request in the interval from second 1 through second 60, so it is dropped by the sixty-second limit.

Constraints

  • 0 <= requestTimes.length <= 200000
  • 1 <= requestTimes[i] <= 1000000000
  • requestTimes is sorted in nondecreasing order.

More Oracle problems

drafts saved locally
public int countDroppedRequests(int[] requestTimes) {
  // write your code here
}
requestTimes[1,1,1,1]
expected1
checking account