Problem Brief

Rate Limit by Multiple Request Fields

FULLTIMEPHONE SCREEN

See Roblox online assessment and hiring insights

Extend a basic rate limiter so that each request contains multiple fields such as userId, deviceId, or endpoint.

Each field dimension has its own rule of the form fieldName window limit. For the same field value, allow at most limit requests inside a window of length window seconds.

A request is ALLOWed only if it stays within the limit for every configured dimension. If any one dimension exceeds its limit, the request is REJECTed.

Function Description

Complete the function applyMultiFieldRateLimiter in the editor below.

applyMultiFieldRateLimiter has the following parameters:

String[] fieldRules: each entry has the form "fieldName window limit"
String[] requests: each entry has the form "timestamp value1 value2 ..." in the same order as the field rules

Returns

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

1Example 1

Input

fieldRules = ["user 10 2", "device 10 3"], requests = ["1 u1 d1", "2 u1 d1", "3 u1 d1", "4 u2 d1", "11 u1 d1", "12 u1 d1"]

Output

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

Explanation

The third request is rejected because the user dimension exceeds its limit even though the device dimension is still valid.

2Example 2

Input

fieldRules = ["user 5 1", "endpoint 3 2"], requests = ["1 u1 /a", "2 u1 /a", "2 u2 /a", "4 u2 /a"]

Output

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

Explanation

The second request fails the user rule, while the fourth request fails the endpoint rule because that endpoint already hit its limit in the active window.

Constraints

Limits and guarantees your solution can rely on.

1 <= fieldRules.length <= 10
1 <= requests.length <= 2 * 10^5
Each field value contains no spaces.
Timestamps are non-decreasing.