FastPrepSliding-Window Rate Limiter

Sliding-Window Rate Limiter

Uber logoUber● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

You receive requests in nondecreasing timestamp order. Each request has a user ID and an integer timestamp in seconds.

A request is accepted when that user has fewer than 100 previously accepted requests in the interval (timestamp - 60, timestamp]. Otherwise it is rejected. Rejected requests do not consume capacity. Requests with the same timestamp are processed in input order.

Return one boolean per input request, where true means accepted and false means rejected.

Function

applySlidingWindowRateLimit(userIds: String[], timestamps: int[]) → boolean[]

Examples

Example 1

userIds = ["amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy"]timestamps = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]return = [true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,false]

The first 100 requests for amy fill the window. The 101st request has the same timestamp and is rejected.

Example 2

userIds = ["a","b","a","a"]timestamps = [0,0,59,60]return = [true,true,true,true]

Users have independent windows. At timestamp 60, the accepted request for a at timestamp 0 lies on the excluded lower boundary and has expired.

Constraints

  • 0 <= userIds.length <= 5000.
  • userIds.length == timestamps.length.
  • User IDs contain 1 to 50 lowercase English letters or digits.
  • 0 <= timestamps[i] <= 10^9.
  • Timestamps are nondecreasing.

Source note: Author-written prompt excerpt retained for source fidelity.

More Uber problems

See Uber hiring insights
public boolean[] applySlidingWindowRateLimit(String[] userIds, int[] timestamps) {
    // Write your solution here.
}
userIds["amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy","amy"]
timestamps[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
expected[true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,true,false]
Checking account…