Implement a Per-User Request Throttle Over a Sliding Time Window

Design and implement a throttling API. Given a limit N and a window length W, each user may make at most N requests within any time window of length W; a request that would break that rule is rejected. This was a 30-minute coding question on a whiteboard where the code did not need to compile, so the expected output is a clear, correct implementation together with its interface. An interface to adapt with the interviewer, for illustration: ```python class Throttle: def __init__(self, limit: int, window_seconds: float): ... def allow(self, user_id: str) -> bool: ... # True: let the request through ``` ```hint Test the boundary Try your idea on a burst of N requests just before a clock boundary followed by N more just after it. Does any stretch of length W then contain more than N accepted requests? ``` ```hint Bound the memory Decide which per-user information you can discard, and when, so that memory does not grow with the total number of requests a user has ever made. ``` ### Constraints and Clarifications - N and W are configuration of the throttle; each user is limited independently. - Not reported: whether rejected requests count toward the limit, the time resolution, whether the throttle is shared by many threads or servers, and how many users there are. Ask, or state your assumptions. ### Clarifying Questions - Does "any window" mean a sliding window ending at every moment, or are fixed buckets (such as each calendar minute) acceptable? - Does a rejected request count toward the user's limit? - Is a request exactly W after an earlier one inside or outside that earlier request's window? - Can N and W differ per user or per endpoint, and can they change while the service runs? - Is the throttle called from many threads, or by many servers that must share one limit per user? - Is an exact limit required, or is a small approximation acceptable in exchange for less memory? ### What a Strong Answer Covers - A clear interface with the limit and window as configuration, and an injectable clock for testing - An algorithm that never admits more than N requests in any window of length W, with the boundary rule stated - Per-user memory bounded by N, cleanup of idle users, and the cost of each call - Thread safety, and how the design extends to many servers - Alternatives such as fixed windows, approximate sliding counters and token buckets, with their exactness and memory trade-offs - Tests at the window boundary ### Follow-up Questions - There are millions of users, most of them idle at any moment. How do you keep memory bounded? - The service runs on many hosts but the limit applies to each user across all of them. What changes? - The limit becomes very large. How do you avoid storing one timestamp per accepted request? - How would a rejected client learn when it may try again?