Rate Limiter (Sliding Window Log)

Rate Limiter (Sliding Window Log)

Per-client rate limiting with a precise sliding-window log — no fixed-window burst at the boundary — judged with deterministic logical time.

Requirements

• Each client is limited independently — one client's traffic never affects another's.
• A request at time t is allowed iff the number of that client's already-allowed requests with timestamp in the half-open window (t - W, t] is strictly less than M. The window includes t itself but excludes the point exactly W units old.
• Only allowed requests are recorded. A denied request leaves no trace — it must not count against, or shift, any future window.
• When a request is allowed, record its timestamp; that request then occupies a slot in every window that still contains it.
• Time is logical: it arrives as the timestamp argument and is non-decreasing across the whole stream. Never read a real clock, and never use randomness.

API to implement

Implement the class SlidingWindowLimiter. 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 time timestamp. Return true (and record it as allowed) iff, counting only this client's previously allowed requests whose timestamp lies in the half-open window (timestamp - W, timestamp], there are fewer than M of them. Otherwise return false and record nothing. Timestamps are non-decreasing across the stream. |

Input format

The first line contains Q, the number of operations. The second line contains the constructor arguments: windowSize (the width W of the rolling window, ≥ 1) and maxRequests (the cap M of allowed requests per window, ≥ 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.

5
5 3
allow a 0
allow a 0
allow a 0
allow a 0
allow a 5

true
true
true
false
true

6
3 2
allow a 0
allow b 0
allow a 1
allow a 2
allow a 3
allow b 4

true
true
true
false
true
true