Per-Key Fixed-Window Cost Limiter with ALLOW and RESET Commands
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are building a rate limiter that meters **cost** instead of counting requests. Every key (for example a user or an API client) may spend at most `limit` cost units in each fixed time window of `window` seconds. Windows are aligned to multiples of `window`: the window that contains timestamp `t` starts at `floor(t / window) * window` and ends just before `floor(t / window) * window + window`.
Process a list of commands in order and return one output string per command. There are two kinds of command:
- `ALLOW key cost timestamp`: let `usage` be the total cost already accepted for `key` in the window that contains `timestamp`. If `usage + cost <= limit`, accept the request, add `cost` to that usage, and output `"true"`. Otherwise output `"false"` and record nothing.
- `RESET key timestamp`: clear all usage recorded for `key` and output `"ok"`.
### Function Signature
```python
def process_commands(limit: int, window: int, commands: list[str]) -> list[str]:
```
### Rules
- Keys are independent: one key's usage never affects another key.
- Usage accepted in one window never counts toward a later window. The first `ALLOW` for a key in a new window starts from zero usage.
- A rejected `ALLOW` changes nothing, so a later, cheaper request in the same window can still be accepted.
- A request whose `cost` alone is greater than `limit` is always rejected.
- `RESET` may name a key that has never been seen; it still outputs `"ok"`. After a `RESET`, the key's usage in the current window is zero.
- Outputs are the exact lowercase strings `"true"`, `"false"` and `"ok"`, one per command, in command order.
### Constraints
- `1 <= len(commands) <= 200000`
- `1 <= limit <= 10^9` and `1 <= window <= 10^9`
- Every command is either `"ALLOW key cost timestamp"` or `"RESET key timestamp"`, with tokens separated by single spaces. `key` is a non-empty string of at most 20 lowercase letters and digits. `cost` and `timestamp` are decimal integers with no sign and no leading zeros (except the number `0` itself).
- `1 <= cost <= 10^9`
- `0 <= timestamp <= 10^15`. Timestamps and window starts can exceed `2^31 - 1`, so use 64-bit integers for them.
- Timestamps are non-decreasing across the whole list: every command's timestamp is greater than or equal to the previous command's timestamp.
- The returned list has exactly `len(commands)` elements and is uniquely determined by the input.
### Examples
**Example 1**
- Input: `limit = 10`, `window = 60`, `commands = ["ALLOW alice 3 0", "ALLOW alice 8 10", "ALLOW alice 7 61", "RESET alice 62", "ALLOW alice 10 63", "ALLOW alice 1 64"]`
- Output: `["true", "false", "true", "ok", "true", "false"]`
- Explanation: Timestamps `0` and `10` fall in the window starting at `0`. The cost `3` is accepted (usage 3), and then `3 + 8 = 11 > 10`, so the cost `8` is rejected. Timestamp `61` falls in the window starting at `60`, where usage starts at zero, so the cost `7` is accepted. `RESET` clears alice's usage, so the cost `10` is accepted (usage 10), and the final cost `1` is rejected because `10 + 1 > 10`.
**Example 2**
- Input: `limit = 5`, `window = 10`, `commands = ["ALLOW a 5 9", "ALLOW b 2 9", "ALLOW a 1 9", "ALLOW a 1 10", "ALLOW b 4 19", "ALLOW b 3 19", "ALLOW b 1 19", "RESET c 20", "ALLOW c 5 20"]`
- Output: `["true", "true", "false", "true", "true", "false", "true", "ok", "true"]`
- Explanation: At timestamp `9` (window starting at `0`), `a` spends its whole budget and its next request is rejected, while `b` is unaffected. Timestamp `10` starts a new window, so `a` is accepted again. At timestamp `19` (window starting at `10`), `b` starts from zero: the cost `4` is accepted, `4 + 3 > 5` is rejected and records nothing, so `4 + 1 = 5` is still accepted. `RESET` on the unseen key `c` outputs `"ok"`, and `c` can then spend its full budget.
**Example 3**
- Input: `limit = 999999999`, `window = 1000000000`, `commands = ["ALLOW k 1000000000 999999999999999", "ALLOW k 999999999 999999999999999", "ALLOW k 1 999999999999999", "ALLOW k 1 1000000000000000"]`
- Output: `["false", "true", "false", "true"]`
- Explanation: The first cost is larger than `limit`, so it is rejected. Timestamp `999999999999999` lies in the window starting at `999999000000000`, where `999999999` fits exactly and the extra `1` does not. Timestamp `1000000000000000` starts a new window at `1000000000000000`, so the cost `1` is accepted.
Overview: A coding problem about a cost-based rate limiter that processes ALLOW and RESET commands for many keys. Each key may spend a fixed budget per aligned time window and rejected requests record nothing, so it tests per-key window bookkeeping and 64-bit timestamp handling across up to 200,000 commands.
Community answers
Answer by shail.finaspirant
def process_commands(limit: int, window: int, commands: list[str]) -> list[str]:
users = {}
ans = []
for parts in commands:
op = parts.split()
cmd, user = op[0], op[1]
if cmd == 'ALLOW':
cost, ts = int(op[2]),int(op[3])
if cost > limit:
ans.append("false")
continue
win_end = (ts//window) * window + window
if user not in users or users[user][0] != win_end:
users[user] = (win_end,cost)
ans.append("true")
elif users[user][1] + cost <= limit:
users[user] = (win_end,users[user][1] + cost)
ans.append("true")
else:
ans.append("false")
elif cmd == 'RESET':
users.pop(user, None)
ans.append("ok")
return ans