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)