Token Limiter

Token Limiter (Rate limiting / quota) Implement a Token Limiter component that limits token (quota) consumption for a subject (e.g., userId / apiKey / tenant) under a given rule set. Note: the original post only provided a link to the problem; the exact statement was not included. The following is a standardized interview-ready version. Requirements Process a sequence of operations and maintain per-key token usage: ALLOW key cost timestamp: at time timestamp, key attempts to consume cost tokens. If within the billing window for that key, current usage + cost <= LIMIT, allow it, record the consumption, and output true. Otherwise reject it, do not record, output false. RESET key timestamp: clear all history for key at timestamp (restart billing), output ok. Billing rule Each key uses a fixed time window of size W seconds. Max tokens per window: LIMIT. Window start for a key is floor(timestamp / W) * W. Input (stdin) Line 1: LIMIT W Line 2: integer Q Next Q lines, each an operation: ALLOW key cost timestamp RESET key timestamp Output (stdout) One line per operation: For ALLOW: true or false For RESET: ok Constraints 1 <= Q <= 2e5 1 <= LIMIT <= 1e9 1 <= W <= 1e9 1 <= cost <= 1e9 0 <= timestamp <= 1e18 key is a whitespace-free string Example Input: 10 60 6 ALLOW alice 3 1 ALLOW alice 8 2 ALLOW alice 7 61 RESET alice 70 ALLOW alice 10 71 ALLOW alice 1 72 Output: true false true ok true false Example Input 10 60 6 ALLOW alice 3 1 ALLOW alice 8 2 ALLOW alice 7 61 RESET alice 70 ALLOW alice 10 71 ALLOW alice 1 72 Output true false true ok true false