Implement a Rate Limiter

Implement a rate limiter that decides whether each incoming request should be allowed at a given timestamp. Design an interface/class that supports request admission: Each request contains a key key (e.g., user id, IP, API name) and a timestamp timestamp. Given a rule: for the same key, allow at most limit requests within a time window of length window seconds. For each request, return whether it is ALLOWed or REJECTed. Requirements: Clearly state and implement a consistent windowing strategy (fixed window or sliding window). Timestamps arrive in non-decreasing order (if not, explain how you would handle it). Input format (one possible online-judge style) First line: three integers window limit n window: window length in seconds limit: max allowed requests per window n: number of requests Next n lines: timestamp key Output format Print n lines, each being ALLOW or REJECT, corresponding to each request. Constraints (suggested) 1 <= n <= 2e5 1 <= window <= 1e9 1 <= limit <= 1e5 timestamp is a non-negative integer key is a string without spaces Example Input: 10 2 6 1 alice 2 alice 3 alice 11 alice 12 alice 12 bob Output: ALLOW ALLOW REJECT ALLOW ALLOW ALLOW Example Input 10 2 6 1 alice 2 alice 3 alice 11 alice 12 alice 12 bob Output ALLOW ALLOW REJECT ALLOW ALLOW ALLOW