Problem Description

You are tasked with implementing a per-user API rate limiter for an API gateway. This rate limiter must enforce specific constraints on the number of requests a user can make within a rolling time window.

API Definition

Implement a RateLimiter class with the following public API:

• RateLimiter(int maxRequests, int windowSeconds):
  • Constructor to initialize the rate limiter with the maximum allowed requests (maxRequests) and the duration of the rolling window (windowSeconds).
• bool allow(string userId, int timestampSeconds):
  • This method should determine if a request for a given userId at timestampSeconds is permitted.
  • It returns true if the request is allowed, and false if allowing it would exceed the defined rate limit.

Rate Limit Rule

For each individual user, the system must allow at most maxRequests requests within any rolling window of windowSeconds seconds.

More formally, a request occurring at time t is allowed if and only if the total number of previously allowed requests for that userId with timestamps falling within the interval [t - windowSeconds + 1, t] is strictly less than maxRequests.

Notes and Assumptions

• timestampSeconds will always be an integer representing time in seconds.
• Calls to the allow method are guaranteed to arrive in non-decreasing timestamp order. (You may explicitly state and assume this; alternatively, be prepared to discuss how you would handle out-of-order input if this assumption were relaxed).
• The solution must be efficient in terms of both time and memory complexity, especially when dealing with a large number of distinct users.

Example

Consider a RateLimiter initialized with maxRequests = 3 and windowSeconds = 10. For a single user, the allow calls would behave as follows:

• allow("user1", 1) → true (Window [ -8, 1 ] contains 0 requests, 0 < 3)
• allow("user1", 2) → true (Window [ -7, 2 ] contains 1 request, 1 < 3)
• allow("user1", 3) → true (Window [ -6, 3 ] contains 2 requests, 2 < 3)
• allow("user1", 4) → false (Window [ -5, 4 ] would contain 4 requests if allowed, 4 is not < 3)
• allow("user1", 12) → true (Window [ 3, 12 ] contains only the request at t=3 among allowed requests, 1 < 3)