FastPrep
Problem · Design

Implement a Rate Limiter

● MediumRobloxFULLTIMEPHONE SCREEN
See Roblox hiring insights

Implement a rate limiter that decides whether each incoming request should be allowed at a given timestamp.

Each request contains a string key such as a user id, IP address, or API name, and a non-negative integer timestamp.

Given a time window of length window seconds and a maximum limit limit, allow at most limit requests for the same key inside any valid window. For each request, return whether it is ALLOWed or REJECTed.

Timestamps arrive in non-decreasing order. You may implement either a fixed-window or sliding-window policy, but the behavior must be consistent with the examples.

Function Description

Complete the function applyRateLimiter in the editor below.

applyRateLimiter has the following parameters:

  1. int window: the rate-limit window length in seconds
  2. int limit: the maximum number of allowed requests per key in one window
  3. String[] requests: each entry has the form "timestamp key"

Returns

String[]: one result per request, each being ALLOW or REJECT.

Examples
01 · Example 1
window = 10
limit = 2
requests = ["1 alice", "2 alice", "3 alice", "11 alice", "12 alice", "12 bob"]
return = ["ALLOW", "ALLOW", "REJECT", "ALLOW", "ALLOW", "ALLOW"]

The third request from alice arrives inside the same 10-second window as the first two and exceeds the limit. Later requests are evaluated against later windows.

02 · Example 2
window = 5
limit = 1
requests = ["1 u", "1 u", "2 u", "6 u", "6 u"]
return = ["ALLOW", "REJECT", "REJECT", "ALLOW", "REJECT"]

Only one request per 5-second window is allowed for the same key in this example.

Constraints
  • 1 <= requests.length <= 2 * 10^5
  • 1 <= window <= 10^9
  • 1 <= limit <= 10^5
  • Timestamps are non-negative integers in non-decreasing order.
  • Each request key contains no spaces.
More Roblox problems
drafts saved locally
public String[] applyRateLimiter(int window, int limit, String[] requests) {
    // write your code here
}
window10
limit2
requests["1 alice", "2 alice", "3 alice", "11 alice", "12 alice", "12 bob"]
expected["ALLOW", "ALLOW", "REJECT", "ALLOW", "ALLOW", "ALLOW"]
sign in to submit