## Implement a Rolling-Window Rate Limiter Implement an in-memory rate limiter that accepts at most `limit` requests in any rolling interval of `window_seconds`. The method should return `True` when the current request is accepted and `False` when it is rejected. After explaining the single-stream version, extend the design so each client IP has its own independent rolling-window limit. ### Constraints & Assumptions - For this practice version, request timestamps are supplied as integer seconds in nondecreasing order. - Only accepted requests count toward the limit. - A timestamp exactly `window_seconds` older than the current request is outside the active window. - `1 <= limit`; `1 <= window_seconds`. - The implementation is in-memory and single-process; distributed coordination is out of scope. ### Clarifying Questions to Ask - Do rejected requests count toward future decisions? - Is the interval left-open or left-closed at the oldest boundary? - Are timestamps guaranteed to arrive in order? - For the follow-up, should inactive IP state be removable? ### Hints - Identify which past accepted requests can still affect the current decision. - Avoid rescanning requests that have already fallen outside the active window. - In the per-IP extension, consider how and when an inactive key can be discarded. ### What a Strong Answer Covers - Exact rolling-window and boundary semantics. - A data structure that expires old accepted timestamps efficiently. - Correct handling of rejection without consuming capacity. - Time and space complexity for one stream and for many IPs. - Per-IP state isolation plus a safe cleanup policy for inactive keys. ### Follow-up Questions - How would the algorithm change if timestamps could arrive out of order? - Can you reduce memory if a very large limit is configured? - How would you test requests that land exactly on the window boundary? - What information is needed to delete an inactive IP without changing future decisions?