Rate Limiter

Implement a rate limiter, commonly sliding window, then discuss race conditions, concurrent maps, synchronization, and lock efficiency. Requirements Implement a rate limiter. The interviewer may let you choose the algorithm; a defensible default is sliding-window log. Example API: class RateLimiter: def __init__(self, limit: int, window_seconds: int): ... def allow(self, user_id: str, timestamp: int) -> bool: ... Expected behavior: Allow at most limit requests per key in the last window_seconds. Evict timestamps older than the active window. Support independent users / keys. Return True for accepted requests and False for rejected requests. Discuss what changes under multi-threaded access. Notes Sliding-window log keeps a deque of accepted timestamps per key. On each request, pop expired timestamps from the front, then accept if the deque length is below the limit. This is exact and easy to code; memory is proportional to the number of accepted requests still inside active windows. Token bucket is another strong answer when the interviewer cares about burst smoothing. Fixed window is simple but allows boundary bursts. Sliding-window counter is a production compromise that approximates the exact log with less memory. Concurrency follow-up: the check-and-append operation must be atomic per key. In Java, a coarse synchronized block is correct but may be too slow; better options include per-key locks, lock striping, or an atomic Redis/Lua operation in a distributed setting. Avoid holding a global lock for all users. Preparation Implement sliding-window log and token bucket. Add tests for boundary timestamps, independent users, exactly-at-limit behavior, and expired entries. Prepare a short concurrency answer: per-key synchronization, concurrent map creation, and distributed atomicity.