Implement a per-user API rate limiter

You are building an API gateway that must enforce per-user rate limits.

Task

Implement a rate limiter with the following API:

• RateLimiter(int maxRequests, int windowSeconds)
• bool allow(string userId, int timestampSeconds)

allow(...) should return:

• true if the request for userId at timestampSeconds is allowed
• false if allowing it would exceed the limit

Rate limit rule

For each user, allow at most maxRequests requests in any rolling window of windowSeconds seconds.

More formally, a request at time t is allowed iff the number of previously allowed requests with timestamps in [t - windowSeconds + 1, t] is strictly less than maxRequests.

Notes / Assumptions

• timestampSeconds is an integer in seconds.
• Calls to allow may arrive in non-decreasing timestamp order (you may state/assume this; otherwise discuss how you would handle out-of-order input).
• The solution should be efficient in time and memory for many users.

Example

If maxRequests = 3, windowSeconds = 10 and a single user sends requests at times:

• 1, 2, 3 → allowed
• 4 → denied (would be 4 requests in window [ -5, 4 ] which effectively includes 1,2,3,4)
• 12 → allowed (window [3,12] contains 3 only among allowed requests)

Implement a Per-User API Rate Limiter

You are building an API gateway that must enforce per-user rate limits using a rolling-window policy.

Implement a rate limiter exposing the conceptual API:

• RateLimiter(int maxRequests, int windowSeconds)
• bool allow(string userId, int timestampSeconds)

For each user, allow at most maxRequests requests in any rolling window of windowSeconds seconds. Formally, a request at time t is allowed iff the number of previously allowed requests for that user with timestamps in [t - windowSeconds + 1, t] is strictly less than maxRequests. A denied request is NOT recorded (it does not consume a slot).

Executable form for this console

Because this is a stateful design problem, implement a single function that replays a request stream and returns the per-request decisions:

solution(maxRequests, windowSeconds, requests) where requests is a list of [userId, timestampSeconds] pairs given in non-decreasing timestamp order. Return a list of booleans — the result of allow(...) for each request, in order.

Example

With maxRequests = 3, windowSeconds = 10, and requests [['u1',1],['u1',2],['u1',3],['u1',4],['u1',12]]:

• 1, 2, 3 → allowed
• 4 → denied (would be the 4th allowed request in window [-5, 4])
• 12 → allowed (window [3, 12] contains only the allowed request at 3)

Result: [True, True, True, False, True].

Constraints

• 1 <= len(requests) <= 10^6 (and may be empty)
• 0 <= maxRequests <= 10^4
• 1 <= windowSeconds <= 10^9
• timestampSeconds are non-negative integers in non-decreasing order
• userId is a non-empty string
• A denied request does not count toward the limit (it is not recorded)

Hints

1. Track state per user independently — a hash map from userId to that user's recent allowed timestamps.
2. A rolling time window with FIFO eviction is naturally a deque (monotonic queue): on each request, drop timestamps older than t - windowSeconds + 1 from the front.
3. Allow the request iff the deque size after eviction is strictly less than maxRequests; only then append t. Never record a denied request.
4. Watch the boundary: the window is inclusive on both ends and spans exactly windowSeconds seconds, so the lower bound is t - windowSeconds + 1, not t - windowSeconds.