非死不可一面面筋

9/25号星期二 下午三点顶着感冒面试。
面试官是个白人，主要使用JavaScript，所以我用Python写代码的时候，还要给他解释一些语法。
互相自我介绍
蠡口溜玖二+follow up
第一步，我按max heap把题目秒了，写完用了大约

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

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

y。结束。


补充内容 (2018-9-27 05:39):
重新确认了下，是蠡口伞司其，不好意思记错题号。两个题目都可以用max heap解决。

heyheyforhello 发表于 2018-9-27 05:03
构造一个数组容器bucket，大小为n。第i个数组包含频率为i的数字，比如1出现3次，那么bucket[3] = [1]。
...

蠡口原题要求相同频率的单词按字典序输出，面试有这个要求吗？有的话用bucketsort挺麻烦的吧

最近经常在地里看到的一道fb的follow up跟这个很像，是给很多二维坐标，求离某一坐标最近的k个

首先从heap着手，如果维持heap里面只存k个，可以把复杂度从O(nlogn)优化到O(nlogk)。只是堆要换成小根堆，输出的时候也要reverse一下。

剩下的就是把O(nlogn)的排序优化成O(n)的问题了。
如果只要第k个，或者输出前k个但是不在乎次序，可以用QuickSelect。
或者就是用楼主想到的BucketSort。

祝尽快收到好消息！

mintyc 发表于 2018-9-27 02:45
最近经常在地里看到的一道fb的follow up跟这个很像，是给很多二维坐标，求离某一坐标最近的k个

首先从he ...

非常感谢，祝好运

祝好运。

楼主能简单讲讲这题怎么用bucket sort 做吗？

nhqgoal 发表于 2018-9-27 04:54
楼主能简单讲讲这题怎么用bucket sort 做吗？

构造一个数组容器bucket，大小为n。第i个数组包含频率为i的数字，比如1出现3次，那么bucket[3] = [1]。
比如[1,1,1,2,2,3]构造出的bucket是[[3], [2], [1], [], [], []]
从bucket末尾遍历到开头，输出k个element。

nhqgoal 发表于 2018-9-27 05:24
蠡口原题要求相同频率的单词按字典序输出，面试有这个要求吗？有的话用bucketsort挺麻烦的吧

抱歉我记错，应该是伞司其

感谢楼主分享

nhqgoal 发表于 2018-9-27 05:24
蠡口原题要求相同频率的单词按字典序输出，面试有这个要求吗？有的话用bucketsort挺麻烦的吧

可以在同一个bucket key里面用ArrayList来存多个value，然后直接sort ArrayList就可以了