Ramp Backend OA 面试复盘｜限流器题里，窗口边界和拒绝请求如何处理

Ramp Backend 的 CodeSignal OA 考过请求限流器。 美国候选人的笔试记录 提到，收到邀请后有三天完成测试。这个邀请期限和测试倒计时是两回事，拿到邮件先分别记下来。 限流器最容易写错的是“最近一段时间”到底包含哪些请求。下面给出一个明确的练习约定：同一用户在长度为 W 的窗口内最多放行 L 次，只统计成功请求，输入时间戳不递减。例子和接口用于讲解解法；正式作答时按题面定义调整。

第一题：实现按用户隔离的请求限流器

题目描述

实现 allow(user, timestamp) ，依次返回每条请求能否放行。当前时间为 t，统计区间约定为 (t-W, t] 。同一毫秒到来的两次请求分别计数，不同用户独立计算额度；被拒绝的请求不消耗额度。 设 W=10、L=2，用户 A 在 1、4、8、11、14 时刻发送请求。前两次放行，8 被拒绝；到 11 时，时间为 1 的请求已经离开窗口，因此 11 放行。14 时清掉时间为 4 的请求，14 也放行。用户 B 在时间 8 的请求不受 A 影响。

解题思路

用哈希表把用户映射到一个双端队列，队列只保存这个用户已经放行且尚未过期的时间戳。处理请求时，先反复弹出所有 timestamp <= t-W 的队首元素，再检查队列长度。长度小于 L 就追加 t 并放行，否则直接返回拒绝。清理必须发生在比较长度之前。 拿时间 11 手算一遍：队列原来是 [1,4] ，清掉 1 后剩 [4] ，追加 11 得到 [4,11] 。这里用 <= ，因为左端点不属于窗口。若题面定义闭区间 [t-W,t] ，过期条件就要改成 < 。这一个符号决定边界测试能否通过。 不要把拒绝请求也追加进去。在上述例子里，如果把 8 记入队列，11 就会被错误拒绝。反过来，若另一道题明确要求所有尝试都计数，则应维护尝试记录；两种规则不能混用。 每条成功请求至多入队、出队各一次，处理 n 条请求的总时间为 O(n)，哈希操作按平均 O(1) 计算。一次请求能清掉多个旧记录，所以这里说的是摊还 O(1)。每个用户最多保留 L 条有效成功记录；长期运行还要回收不活跃用户，否则哈希表的键仍会持续增长。

做完主逻辑后，补哪几组测试

先固定 W=10、L=2，分别测试时间 10 和 11 到来的第三次请求，检查左边界。再把两名用户的请求交错输入，确认额度没有共用。对同一时间戳连续请求三次，应放行两次、拒绝一次。 长时间没有流量后突然来一条请求，要一次清掉全部过期记录。若允许 L=0，直接拒绝即可。题面若给出乱序时间戳，队列的单调性前提就不成立，应先确认是离线排序处理，还是按到达顺序查询历史窗口，不能偷偷排序后改变业务顺序。

Ramp OA 备考如何练

先写一个保存全部成功记录、每次遍历计数的慢版本，作为小数据校验器。随机生成多用户请求流，把它和队列版本逐条对比。出现差异时打印当时的用户、时间和有效请求列表，比只盯着最终得分更容易定位问题。 现场 Coding 也出现过按用户做滑动窗口限流的题。它和 OA 的具体输入格式不同，练习时把字符串解析与 allow 分成两个函数；即使输入从数组换成日志文本，也只需修改解析层。

FAQ

限流器需要实现成分布式服务吗？

这道练习先完成单进程、顺序输入的接口。只有题目追加多线程或多节点条件时，才讨论原子性、共享状态与时间来源。不要让网络和存储配置占掉算法实现时间。

固定窗口计数为什么不能直接替代？

固定窗口在周期交界处能连续放行两批请求。例如每十秒两次，在第九秒末放行两次、第十秒初再放行两次，就超过任意十秒内两次的限制。滑动窗口必须保留请求实际发生的时间。

拒绝结果要返回剩余等待时间如何办？

在只统计成功请求的约定下，额度耗尽时，最早释放额度的时刻是队首时间加 W。先完成过期清理，再用这个时刻减去当前时间；不要从最近一次被拒绝的时间重新计时。

参考来源

Jointaro：美国 Backend 候选人的 CodeSignal 经历 一亩三分地：Ramp 全职 SDE 限流器笔试记录 Reddit：纽约 Backend 候选人的完整面试流程

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。