这篇只保留面经内容，聚焦一道真实 Waymo 面试题。难点不在语法，而在有限时间内做出正确决策、跟进追问并清晰说明为什么这样做。
题目原话
面试官给出的核心问题是：
“你还有一个长度为 K 的权重数组 M。在 Q1 的第 i 次 pop 时，选中的元素分数要乘上 M[i]。你能得到的最大分数是多少？”
面试中可按下面方式理解：
Q1是可选元素集合。- 总共进行
K次 pop。 - 第
i次选择的值会乘以M[i]。 - 目标是最大化总得分。
面试中的第一反应
常见起手式是：
Q1降序排序M降序排序- 大值配大权重
这能快速给出 baseline，但面试官通常会马上追问：
- 你是不是做了不必要的全量排序？
- 如果
K远小于Q1长度，怎么优化？ - 如果
Q1是流式输入怎么办？
关键是从“把所有东西都排好”切到“只维护当前最有价值的信息”。
主解法：贪心 + 堆
在允许重排匹配顺序的前提下，主解法是：
- 先将权重
M按降序处理。 - 用最大堆维护当前可选的
Q1值。 - 每一步取堆顶最大值，与当前最大权重相乘并累加。
这套回答在面试里比较稳，因为它同时覆盖：
- 选择策略（为什么当前取最大）
- 数据结构（为什么用堆）
- 复杂度（为什么可扩展）
复杂度可表述为：
- 建堆
O(N)（或O(N log N)，取决于建堆方式） K次弹出O(K log N)- 总体
O(N + K log N)或O((N + K) log N)
真实追问与回答方向
1）如果 K << N，如何优化？
可答：
- 避免反复全量排序。
- 用堆只做必要的最大值提取。
- 也可补充 partial selection 思路（如 quickselect/nth-element）。
2）如果 Q1 是数据流，怎么做？
可答：
- 维护一个大小为
K的 Top-K 结构。 - 用最小堆保留当前最大的
K个值。 - 每来一个新值，
O(log K)更新。
3）除了贪心还有别的方法吗？
可答：
- 可以提 DP 作为扩展思路（当约束变化时）。
- 但要明确 DP 的状态与复杂度代价更高。
- 在当前目标下，贪心更直接也更高效。
现场编码常见失误
- Python
heapq默认最小堆，做最大堆要取负值。 - 权重顺序和贪心策略没对齐，导致结果偏小。
- 忘记处理
len(Q1) < K的边界。 - 没说明负数值/负权重时的行为约定。
- 代码写完但没有给出最优性说明。
最优性怎么讲更稳
可用简短交换论证：
- 较大的未使用权重应匹配较大的未使用值。
- 如果把大值放到小权重位置，交换后总分不会变差。
- 反复交换，最终得到“大的配大”的结构。
- 堆只是高效实现这个选择过程的工具。
这题考察的核心
这道题表面是 Heap + Greedy，实际考察更综合：
- 能否先快速给出正确 baseline
- 能否在追问下迭代到更优方案
- 能否清楚解释复杂度与最优性
- 能否在压力下保持表达结构
在 Waymo 这类 VO 面试里，解题正确只是起点，思路可解释、可扩展、可落地才是区分点。
如果你也在准备 Waymo / Google / Amazon 的 OA 或 VO，想要更系统的题型拆解、追问演练和表达优化，欢迎联系网站获取资料与备考建议。
需要面试真题？ 立刻联系微信 Coding0201，获取真题。
联系方式
Email: [email protected]
Telegram: @OAVOProxy