Implement a Rate Limiter

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
applyRateLimiter(window: int, limit: int, requests: String[]) → String[]
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
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.
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.

The trick is the state you store. Keep a hash map from key to a pair: current window id and the count of allowed requests in that window. For each request, parse the timestamp and key, compute id = floor(t / window), and compare it to the stored id. If it differs, reset the count to zero and update the id. Then allow only if count < limit, and increment only on ALLOW. Pitfalls: incrementing on REJECT, which breaks Example 2, and using sliding-window logic with deques when the problem says fixed. Also watch overflow, since window goes up to 10^9 and timestamps can be large, so use 64-bit integers where your language needs it. Because timestamps are non-decreasing, you never need to keep old windows, so memory stays O(unique keys). Total time is O(n). If you blank on the parsing or reset logic mid-OA, StealthCoder is the hedge that gets you unstuck quickly.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.