新鲜谷歌on赛面经

新鲜谷歌on site面经，还在等结果~写得尽可能详细了，求加大米~

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

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

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

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

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

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

第三题我的想法也是个O(klogn)，就是把每一行看成一个sorted list， 然后就是相当于find k smallest from n sorted list，利用PQ，先push进每一行的第一个，然后每次都pop最小的那个，再push进这个元素的右面元素。不过这样的话就没有利用到在col方向上也是sorted这个性质，不知道lz是用的什么方法。

第三轮 感觉是 三七八 follow up, 请问lz 怎么做的呢

同问第三题思路

yourdoraemon 发表于 2020-8-10 07:35
第三轮 感觉是 三七八 follow up, 请问lz 怎么做的呢

我咋感觉就是378，没有follow up。用一个list 记录每次heap pop出来的数字就是结果了。

请问，第四问的follow up应该怎么回答比较好？

请问一下楼主面的是L4吗？

如何validate invalid input map?  这问应该是考如何确认这个图是一棵树，我觉得解答是N个点，N-1条边，同时score(Root) == N（或者用Union-Find证明这个图是联通的）

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

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