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)