Rate Limiter (Token Bucket)

Rate Limiter (Token Bucket)

Per-client token-bucket rate limiting — the algorithm behind almost every real API gateway, judged with deterministic logical time.

Requirements

• Each client has its own bucket. A client's bucket is created full (capacity tokens) on their first request.
• On every request, first refill: tokens = min(capacity, tokens + (now - lastRequestTime) * refillRate), then update lastRequestTime.
• If tokens ≥ 1: consume one, allow. Otherwise deny — a denied request still updates lastRequestTime (the refill already happened).
• All arithmetic is integer; timestamps are whole seconds and non-decreasing per client.

API to implement

Implement the class RateLimiter. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | allow <clientId> <timestamp> | boolean | A request from clientId at integer second timestamp. Return true (consume one token) if the client's bucket has ≥ 1 token after refill, else false. Timestamps for a given client are non-decreasing. |

Input format

The first line contains Q, the number of operations. The second line contains the constructor arguments: capacity (max tokens per bucket, ≥ 1) and refillRate (tokens added per second, ≥ 1). Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

7
3 1
allow alice 0
allow alice 0
allow alice 0
allow alice 0
allow alice 1
allow alice 1
allow bob 1

true
true
true
false
true
false
true

6
2 1
allow a 0
allow a 0
allow a 0
allow a 10
allow a 10
allow a 10

true
true
false
true
true
false