## Problem Design and implement an in-memory **rate limiter** using a **sliding time window**. You are given a stream of requests. Each request has: - `key` (e.g., user ID, API token, or IP) - `timestamp` (integer seconds, non-decreasing for a given `key`) Implement an API: - `bool allow(key, timestamp)` The limiter should allow **at most `N` requests per `W` seconds** for each `key`. ### Requirements - If a request is allowed, it counts toward the limit. - Sliding window means the window is `(timestamp - W, timestamp]` (or clearly define inclusivity and keep it consistent). - Support many distinct keys. ### Example If `N = 3`, `W = 10` seconds: - Requests for the same key at times `[1, 2, 3]` are allowed. - A request at time `4` is denied (already 3 in last 10 seconds). - A request at time `12` may be allowed depending on the sliding window definition (e.g., requests at time `1` may have expired). ### Constraints (assumptions you may use) - Timestamps fit in 64-bit integer. - Aim for near O(1) average time per `allow` call. - Memory should not grow unbounded for inactive keys (you may describe a cleanup strategy).