Startup / VO 面试真题解析：滑动窗口 Rate Limiter 设计与实现

Implement a RateLimiter that allows at most maxRequests per user within a sliding window of windowSizeInSeconds.

• allowRequest(userId, timestamp) returns True or False.
• Each user has an independent limit.
• Expired requests are removed; rejected requests are not counted.
• Assume timestamps arrive in nondecreasing order.
• Analyze time and space complexity.

这道题要求设计一个支持按用户限流的 RateLimiter：每个用户都要独立统计自己在最近一个滑动时间窗口内的请求数，如果超过 <code>maxRequests</code> 就拒绝，否则放行。由于时间戳是非递减的，最常见的做法是为每个用户维护一个队列，记录已通过的请求时间；每次新请求到来时，先把窗口之外的过期时间弹出，再判断当前队列长度是否已经达到上限。这样可以保证被拒绝的请求不会进入统计，逻辑清晰，也方便分析复杂度。