Databricks SWE OA 面试复盘｜75 分钟两题，限流器和快照迭代器如何写

这场 Databricks SWE OA 给 75 分钟，两道题都不是刷完模板就能交：第一题要把限流、突发流量和排队放进同一个状态机，第二题要求迭代器稳定地读出某个时刻的集合。时间不长，代码结构一乱，后半程就很难补回来。

第一题：按客户限速的网络节流器

题目描述

每个客户有独立带宽上限。请求带着客户 ID、数据大小和到达时间；系统需要在滑动时间窗口内统计已用额度，把超额请求放入等待队列，并在额度恢复后按顺序释放。空闲客户可以短暂突发，但累计额度不能无限增长。 这份 L4 候选人的题目记录 把关键约束写得很清楚：令牌按速率回补，请求按大小消耗令牌。

解题思路

用 Map<clientId, Bucket> 保存每个客户的 tokens 、 lastRefillTime 和等待队列。处理请求前先按时间差回补令牌，回补上限固定为 bucket capacity；令牌够就立即通过，否则入队。每次回补后继续检查队首，直到令牌不足为止。队列不能跳过头部请求，否则同一客户的顺序会被打乱。测试时要覆盖同一时间戳的多条请求、长时间空闲后的突发、请求大小刚好等于余额，以及队首请求大于容量的输入约束。 复杂度 ：单次入队或通过是 O(1)，每条等待请求只会出队一次；状态空间随活跃客户和排队请求数增长。

第二题：支持快照的集合迭代器

题目描述

实现一个集合，调用 snapshot() 后得到的迭代器必须看到创建快照时存在的元素；快照创建后，live set 的新增和删除不能改变该迭代器的结果。题目要求在集合仍可继续变更时维持快照视图。

解题思路

给集合维护单调递增的版本号。每个元素记录 bornVersion 和 deadVersion ； snapshot() 保存当前版本，迭代时只返回满足 bornVersion <= snapshotVersion < deadVersion 的元素。删除不直接抹去节点，而是写入当前删除版本。这样能保留历史可见性，也避免为每一次快照复制整个集合。实现时要把重复 add、重复 remove 和“删除后再加入”拆开处理；后者需要新的生命周期记录，不能复用已经死亡的版本区间。 复杂度 ：写操作为 O(1) 到 O(log n)，取决于底层索引；一次完整迭代为 O(n)。

做题过程

先花 5 分钟把状态、时间推进和输出顺序写在草稿上。第一题优先完成单客户正确性，再抽出 refill() ，最后加入多客户 map；第二题先确定版本不变量，再写 iterator 的过滤条件。两题都要留出运行样例和补边界的时间。Databricks 的全流程不只看算法，另一些工程师候选人记录里还出现了 Pair Programming、HLD 和行为面，这意味着代码解释不能只停在“能跑”。

FAQ

Databricks OA 里限流题先写滑动窗口还是 Token Bucket？

题干同时要求平滑限速、突发额度和排队时，Token Bucket 的状态更紧凑。优先把回补公式和容量上限写成独立函数，主流程会清楚很多。

快照迭代器为什么不能直接复制整个 set？

复制能保证结果，但多次快照会把空间成本放大。版本区间让元素只保留一份，并把“某个快照能否看到它”交给迭代时判断。

参考来源

Databricks SWE Interview (L4)：75 分钟 OA 与两道实现题 Databricks L4 Interview Experience：DSA、Pair Programming 与 HLD Databricks Software Engineer Interview Questions

联系 VOPathway

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

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

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