Implement a Rate Limiter (with follow-up)

Problem: Implement a Rate Limiter (with follow-up) Design and implement a Rate Limiter that controls the rate at which requests are allowed. Core requirement Given a rule: within any continuous time window, the number of requests must not exceed a threshold. Implement one of the following interfaces (choose either style): Function: allow(timestamp) -> bool Class: RateLimiter(limit, window) with method allow(timestamp) -> bool Where: timestamp is an integer time value (seconds or milliseconds, but keep it consistent) limit is the max allowed requests within the window window is the window size allow(timestamp) returns true if the request is permitted, otherwise false. Constraints / edge cases Timestamps may or may not be strictly increasing (state assumptions; default assumes increasing). Must be efficient for high-throughput scenarios (discuss time/space complexity). Example ("max 3 requests per 10 seconds") limit = 3, window = 10 request timestamps: [1, 2, 3, 4, 11, 12] expected outputs: [true, true, true, false, true, true] Follow-up (common directions) Discuss and/or extend your design to support at least one of: Per-user / per-key limiting: allow(key, timestamp) with independent limits per key. Distributed rate limiting: multiple machines enforcing the same limit; how to keep correctness and performance (e.g., Redis, consistent hashing, approximate approaches). Smoother limiting: switch from fixed window to sliding window or token bucket; compare trade-offs. Example Input limit=3 window=10\ntimestamps=1 2 3 4 11 12\n Output true true true false true true