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.

Use a fixed-window policy: divide time into non-overlapping windows of exactly window seconds each, aligned to absolute time (i.e., window boundaries occur at 0, window, 2*window, 3*window, ...). A request at timestamp t falls in the window [floor(t / window) * window, floor(t / window) * window + window - 1].

For each request, allow it if the number of previously ALLOWED requests with the same key in the same window is strictly less than limit; otherwise reject it. Only ALLOWED requests count toward the limit; REJECTED requests do not.

Timestamps arrive in non-decreasing order. For each request, return ALLOW or REJECT.

Function Description

Complete the function applyRateLimiter in the editor below.

applyRateLimiter has the following parameters:

  • int window: the rate-limit window length in seconds
  • int limit: the maximum number of allowed requests per key per window
  • 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"]
Using fixed windows aligned to absolute time with window=10: boundaries at 0, 10, 20, ... Alice's requests at t=1 (window [0,9]: 1 ALLOWED → ALLOW), t=2 (window [0,9]: 2 ALLOWED → ALLOW), t=3 (window [0,9]: already 2 ALLOWED, limit reached → REJECT). Alice's requests at t=11 (window [10,19]: 1 ALLOWED → ALLOW), t=12 (window [10,19]: 2 ALLOWED → ALLOW). Bob's request at t=12 (window [10,19]: first for bob → ALLOW). Only ALLOWED requests count toward the limit.
02 · Example 2
window = 5
limit = 1
requests = ["1 u", "1 u", "2 u", "6 u", "6 u"]
return = ["ALLOW", "REJECT", "REJECT", "ALLOW", "REJECT"]
Using fixed windows aligned to absolute time with window=5: boundaries at 0, 5, 10, ... Key 'u' at t=1 (window [0,4]: 1 ALLOWED → ALLOW), t=1 (window [0,4]: already 1 ALLOWED, limit=1 reached → REJECT), t=2 (window [0,4]: still 1 ALLOWED, limit reached → REJECT), t=6 (window [5,9]: 1 ALLOWED → ALLOW), t=6 (window [5,9]: already 1 ALLOWED, limit reached → REJECT). REJECTED requests do not count toward the limit.
Constraints

  • 1 <= requests.length <= 2 * 105
  • 1 <= window <= 109
  • 1 <= limit <= 105
  • 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"]
checking account