最近整理到一道 Acceldata 的 Coding Interview 真题，要求实现一个基于滑动时间窗口的限流器（Rate Limiter）。

这类问题在后端开发和分布式系统中非常常见。API 网关、用户请求控制、数据库查询服务以及数据处理平台，都可能需要通过 Rate Limiter 限制请求频率。

Acceldata 面试题目原文

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 non-decreasing order.
• Analyze time and space complexity.

举个例子

假设限流器的配置如下：

maxRequests = 2
windowSizeInSeconds = 10

这意味着每个用户在最近 10 秒内，最多只能有 2 次成功请求。

依次执行以下操作：

这里约定窗口为 (timestamp - 10, timestamp]，也就是恰好相隔 10 秒的旧请求不再计入当前窗口。

注意时间戳 109 被拒绝的请求不会被记录，因此不会影响 UserA 后续的请求判断。

思路：HashMap + Queue + Sliding Window

最直接的办法是为每个用户保存全部历史请求时间戳。

当收到新请求时，遍历该用户的所有历史记录，统计最近一个时间窗口内的请求次数，再判断是否允许通过。

这种方式可以得到正确结果，但随着运行时间增加，历史数据会不断积累，每次都重新扫描也比较低效。

更合适的做法是使用 HashMap 配合 Queue（队列）。

HashMap 用来保存不同用户的请求记录。每个 userId 对应一个独立队列，队列中只存放该用户已经被允许通过的请求时间戳。

由于题目保证时间戳按照非递减顺序到达，因此队列中的记录天然按时间排序。

对于一次新的请求，只需要检查队列最前面的时间戳，判断它是否已经超出当前滑动窗口。

如果过期，就将其从队列中移除。持续执行这一操作，直到队列中不再存在过期记录。

清理完成后，队列长度就是该用户当前窗口内已经成功通过的请求数量。

如果长度小于 maxRequests，将当前时间戳加入队列，并返回 True。

如果长度已经达到 maxRequests，直接返回 False，不修改队列。

整个过程中，只操作当前用户对应的队列，因此不会影响其他用户的限流状态。

为什么使用 Queue 而不是普通数组？

这道题的关键操作是删除最早的请求记录。

如果使用普通数组，在头部删除元素可能涉及后续元素移动，增加额外开销。

使用支持高效头部删除的双端队列，例如 Python 的 collections.deque 或 Java 的 ArrayDeque，可以在 O(1) 时间内完成队首元素的移除。

与此同时，由于时间戳已经有序，不需要额外排序，也不需要每次遍历全部请求记录。

这也是题目提供时间戳非递减条件的意义所在。

平均摊还时间复杂度为 O(1) 每次请求，总时间复杂度为 O(n)。

需要区分的是，如果某一次调用恰好清理了大量过期记录，该次调用本身仍可能花费 O(m) 时间，其中 m 是本次删除的记录数。

空间方面，假设共有 U 个用户，每个用户最多保存 maxRequests 条有效请求记录，那么：

空间复杂度为 O(U × maxRequests)。

这里还需要注意，若某个用户长期没有再次发起请求，其队列中的旧记录不会自动清理。实际工程中通常还需要针对长期不活跃的用户设置额外的数据清理机制。

这道题还有哪些容易出错的地方？

首先是滑动窗口的边界。

对于时间戳为 t、窗口长度为 W 的请求，如果采用 (t-W, t] 的定义，那么所有时间戳小于或等于 t-W 的记录都应该被移除。

具体采用哪种边界定义，需要保持一致，不能在实现过程中混用。

其次是被拒绝请求的处理。

题目明确要求 rejected requests are not counted。也就是说，只有返回 True 的请求才能被放入队列。

如果把所有请求都记录下来，即使用户停止发送请求，也可能因为之前大量被拒绝的记录而继续触发限流。

另外，需要考虑 maxRequests = 0 的情况，此时所有请求都应被拒绝。对于正常的正数时间窗口，按照上述队列方案即可完成处理。

CSoAHelp：真实 Coding Interview 题目与面试辅助服务

CSoAHelp 长期整理北美科技公司的真实技术面试题目，涵盖 Google、Amazon、Meta、TikTok、Apple 以及其他科技公司。

我们提供 Online Assessment（OA）和 Coding Interview 相关的准备与技术支持，包括真实面试题目分析、算法思路讲解、模拟练习，以及针对具体面试环节的辅助服务。

在算法面试准备中，我们尤其关注候选人对题目条件的理解、数据结构的选择、边界测试和时间复杂度分析。这些细节往往会直接影响最终的代码正确性。

如果您近期正在准备 Acceldata 或其他北美科技公司的 Coding Interview，欢迎通过 CSoAHelp 了解我们的相关服务。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~