Rate Limiter (Sliding Window)

Problem: Implement a Rate Limiter (Sliding Window) Implement a per-key rate limiter with the following requirements: Policy: for each key, allow at most limit requests in any rolling window of windowSeconds seconds. API: allow(key, timestampSeconds) -> bool True if the request is allowed False otherwise timestampSeconds is an integer in seconds (you may assume non-decreasing timestamps if stated). Input (stdin) First line: limit windowSeconds q Next q lines: key timestampSeconds Output (stdout) For each request, print true or false. Constraints 1 <= q <= 2e5 1 <= limit <= 1e5 1 <= windowSeconds <= 1e9 key is a non-empty string without spaces Test Cases (see Chinese version) Example Input 3 10 6 u1 1 u1 2 u1 3 u1 4 u1 11 u1 12 Output true true true false true true