PocketGems 电面一

对面是中国人，女，问的Inventory题：

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

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

应该跪在Followup 2了，脑子没转过来。



补充内容 (2017-11-18 01:25):
重新想了一下，思路第三步可以用Quick Select

重新想了一下，思路第三步可以用Quick Select

920329 发表于 2017-11-18 01:25
重新想了一下，思路第三步可以用Quick Select

楼主可以在详细说一下吗？我刚觉selection sort 也是可以的吧，只要m << n就可以了吧

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

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

920329 发表于 2017-11-18 01:41
https://en.wikipedia.org/wiki/Quickselect
https://leetcode.com/problems/kth-largest-element-in-an ...

对的！非常感谢！祝楼主二面！

当n很少的时候用heap可以啊，你只需要维护一个大小为n的大根堆，遍历所有份，返回留在大根堆里的k个元素就好了。时间复杂度是nlogn，还有比这更好的方法吗？ 你的quick select也要先得到所有份的金额组成的数组，长度是O(m)，对这个数组进行quickselect的效率没有nlogn高啊，因为已知m>>n

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

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

用堆的时间复杂度应该是O(mlogn）， 用quickselect的时间复杂度是O（m），这里m代表物品数量，n代表多少个物品栏。  因为首先你要得到所有的份，得到的份的数量是O(m）级别的，然后你要遍历这O(m)个物品，所以时间复杂度怎么可能是O(nlogn）呢。

Pass