Problem Brief

Implement a Rate Limiter

FULLTIMEPHONE SCREEN

See Roblox online assessment and 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:

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

Returns

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

1Example 1

Input

window = 10, limit = 2, requests = ["1 alice", "2 alice", "3 alice", "11 alice", "12 alice", "12 bob"]

Output

["ALLOW", "ALLOW", "REJECT", "ALLOW", "ALLOW", "ALLOW"]

Explanation

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.

2Example 2

Input

window = 5, limit = 1, requests = ["1 u", "1 u", "2 u", "6 u", "6 u"]

Output

["ALLOW", "REJECT", "REJECT", "ALLOW", "REJECT"]

Explanation

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

Constraints

Limits and guarantees your solution can rely on.

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.