Google L4 SWE Round1, 1st Interview

本来今天有两场 Round 1 interview，结果第二场昨天临时被 reschedule 到下周了。那就先趁热把今天这场的面试题记录一下。
这场是算法面试。
题目是：给你一棵带权重的 binary tree（edge weight >= 0），需要 cut 掉一些 edges，使得 root node 和所有 leaf nodes 完全分离。这里的 leaf nodes 是固定的，始终指原始 tree 中的 leaf nodes，不会因为 cut 了 edge 而产生新的 leaf node。每 cut 一条 edge，都需要付出对应 edge weight 的代价，求满足条件的最小总代价。
全程直接在 Google Doc 里写代码，没有任何框架可以补全，连 TreeNode 都要自己写。
follow-up：
如果 edge weight 可以是负数，你的算法还正确吗？如果不正确，能不能举一个反例？

接下来是我的思考过程，有兴趣的可以继续看：
我先问了一下数据范围，面试官说 sum of weights <= Integer.MAX_VALUE，node 数量也 <= Integer.MAX_VALUE。
于是我说给我几分钟，先想一下初步思路。面试官提示我：「有什么想法可以 think aloud。」
于是我就开始一边想，一边把整个思考过程说出来并写在 Google Doc 上。
首先，如果完全不考虑最小代价，那最简单粗暴的方法就是直接 cut 掉 root 到 left child 和 righ

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

之后，root 和 leaf 其实已经分离了，但因为第二条 edge 的 weight 也是负数，再多 cut 一刀反而能让总代价更低。
我当时脑子已经完全接受了 weight >= 0 这个前置条件，所以思维被锁死在了「两个 options 二选一」上，根本没想到负权重会直接改变问题的性质。
虽然这个 follow-up 最后没做出来，但我反而还挺开心的。这个题我之前完全没做过，在这种情况下能比较快地从最直接的解法，一步步推到递归/DP 的 recurrence，感觉自己的知识迁移能力确实比以前强了一些。
而且这个 follow-up 给我的感觉特别像脑筋急转弯——面试官一给出反例，瞬间醍醐灌顶：「哦！原来还能这样。」属于没答出来，但确实学到了东西。
总体面试体验还是非常不错的。无论最后过不过，多攒一次这种现场思考和沟通的经验都挺值的。
希望下周的第二场 Round 1 能发挥得更好。

followup好难