Google SWE Coding：证明和 Follow-up 怎么练

💡 核心要点 (Key Takeaways)

• Google coding 题更重推导和证明，不能只背最终代码。
• 每题都要讲清 invariant、为什么最优、复杂度和边界。
• follow-up 来时要先重新定义约束，而不是直接改代码。

用一道题看评价重点

以 CoolMap 或 grid path 这类题为例，Google 面试官不只看你最后写出的代码。他会观察你如何定义状态、为什么旧方案不够、关键性质从哪里来、能不能用反例打掉错误直觉。候选人如果一上来背最优解，反而会丢掉展示推导能力的机会。

第一步不是最优解

更稳的开场是先给出暴力解，说明它为什么慢或不稳定，然后再找可优化的性质。比如 tree reroot 题先从每个 root 做 DFS 讲起，再推导父子换根时距离和如何变化。暴力解不是浪费时间，它让面试官看到你在控制问题规模。

• 先说明 naive 做法和复杂度瓶颈。
• 再指出可以复用的信息或单调性。
• 最后把优化写成状态、转移或数据结构选择。
• 如果提示出现，先把提示转成明确约束再改方案。

证明要落到不变量

Google coding 经常要求候选人解释为什么这个算法不会漏解。不要只说“因为这样最优”。可以把证明压成一句不变量：循环里始终维护什么、堆里始终代表什么、二分左右边界分别表示什么、DP 状态已经包含哪些历史信息。

• Invariant：循环或状态转移过程中什么一直成立。
• Correctness：为什么不会漏解，为什么不会重复算错。
• Complexity：时间和空间瓶颈分别是什么。
• Edge case：n=0/1、重复值、断连、无法到达、溢出。

Follow-up 的处理顺序

Follow-up 往往改变输入规模、返回目标或约束条件。处理顺序是：复述变化，指出旧解哪里仍然有效，说明哪里失效，再给新复杂度。直接改代码会让面试官听不到你对约束变化的判断。

复盘时只看三件事

每次 Google coding mock 后，不要只记录题目名。第一，哪一步推导是跳过去的；第二，哪一个 edge case 是面试官提醒后才想到的；第三，哪个 follow-up 改变了复杂度。把这三点补齐，比再刷一题更有价值。

45 分钟时间分配和开口方式

phone screen 通常 45 分钟，建议分四段。前 5-8 分钟澄清需求：问清输入输出、边界、规模，确认题目理解。接下来 10 分钟写暴力解，说明它为什么慢或不稳定。中间 20 分钟做优化解，边写边讲不变量和复杂度。最后 5-10 分钟补 edge case 和测试。写代码时不要沉默，把当前在哪个循环、状态代表什么、复杂度卡在哪说出来，面试官才能跟上你的思路，也能在你跑偏时早点提示。卡住时不要闷头硬想，明确说卡在哪、需要哪个提示；在 Google 面试里，把提示用好也是评估的一部分。建议录音复盘，专门听自己哪些地方沉默太久、哪些关键判断没说出来，针对性补表达。时间不够时先保证正确性再优化，别为了炫技写一半的复杂方案。开口前先花 10 秒复述题意和边界，避免方向跑偏返工。

• 先澄清再动手：输入输出、边界、规模、是否允许原地修改。
• 边写边说：当前状态的含义、复杂度瓶颈、下一步计划。
• 用提示：先把提示翻译成明确约束，再说明旧方案哪里失效。
• 卡住时：明确说卡在哪、需要哪个提示，不闷头硬想。
• 留时间测试：最后留 5 分钟，别让方案停在没测过的代码上。
• 录音复盘：听自己哪里沉默太久、哪个关键判断没讲出来。

R1 到 R2 的题型跨度怎么练

Google 流程里 coding 轮的难度会逐轮变化，公开面经里普遍提到后面的轮次规模更大、follow-up 更多。建议按题型建小题库：reroot DP、sliding window、monotonic stack、binary search on answer、区间题，每类 2-3 道就够。每道题练两遍：一遍正常 45 分钟完整流程，一遍在完成后追加“规模变大”或“返回目标变了”的 follow-up，现场重新做复杂度分析。这个练法最接近真实面试的追问体验。关键是养成复杂度重推的习惯：follow-up 后先复述新约束，再说旧方案哪部分仍有效、哪里失效，最后给新方案和新复杂度，而不是直接跳到改代码。题库不用多，每类吃透两遍比贪多强，重点练的是应对约束变化的反应。约束变化时先复述新约束再动手，给面试官看到你重新分析的过程。如果新约束让原方案失效，要能说出哪里失效、怎么改。

• 题库按 pattern 建：每类 2-3 道，追求覆盖不追求数量。
• 双版本练习：正常版加一个追加规模约束的 follow-up 版。
• 复杂度重推：follow-up 后先复述新约束，再改方案。
• 有效与失效：说清旧方案哪部分仍有效、哪里失效。
• 新复杂度：改完后给出新的时间空间，并解释为什么更优。
• 反应速度：从听到 follow-up 到给出新复杂度，控制在几分钟内。