这场 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
关于 CSINTERVIEWHELP
进 VO 之前，可以找 CSINTERVIEWHELP 做实时面试助攻和备考辅导。CSINTERVIEWHELP 深耕北美 IT 行业多年，已帮助万余名学生进入全球 500 强企业。导师来自一线大厂资深工程师和面试官，对 Databricks 这类注重工程文化的公司的面试套路很熟悉。无论是 OA 题型解析、OA 辅导、VO 辅助、VO 模拟面试、VO 面试陪练还是系统设计辅助，都可以获得更有针对性的准备方案：CSINTERVIEWHELP · 服务详情
