google电面

耶！没有遇到烙印~45分钟 一道coding+follow up

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

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

第一次google doc里写代码，很奇妙~

迷糊 不知道怎么把份调低，评论区里再发一遍吧

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

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

请问follow up的思路是什么呀

alexisheeee 发表于 2019-9-26 06:50
请问follow up的思路是什么呀

用heap吗? O(N) + O(K) -> O(N) space

ripxdanni 发表于 2019-9-26 11:49
用heap吗? O(N) + O(K) -> O(N) space

是的🙆

樱花虾 发表于 2019-9-26 11:53
是的🙆

请问你一开始的类似merge sort的做法是什么呀？
看了蠡口。你说的follow up 解法是把 K个头结点扔进pq，每次pop然后补一个头结点进去对吧？
但是最后一个 每次merge 一对，类似merge sort的方法，space是O(1)呀，，表现更好

savage811 发表于 2019-9-28 13:12
请问你一开始的类似merge sort的做法是什么呀？
看了蠡口。你说的follow up 解法是把 K个头结点扔进pq， ...

估计楼主应该生成list 的时候没复用原节点，那样做的话，需要nlogK的额外空间

leonYuuuu 发表于 2019-9-28 14:06
估计楼主应该生成list 的时候没复用原节点，那样做的话，需要nlogK的额外空间

请问你是说像这样divide & conquer的时候，额外生成了l和r吗？
l = self.mergeKLists(lists[:mid])
r = self.mergeKLists(lists[mid:])
return self.merge(l, r)

logK是divide&conquer的次数？请问n是什么啊？

樱花虾 发表于 2019-09-25 23:06:57
迷糊 不知道怎么把份调低，评论区里再发一遍吧

赞一个! Lz现在有收到update吗