热乎乎的 Uber 电面 fulltime

如果知道分数范围的话，比如0-100, 可以用counting sort
lz这是哪个组的？

snowwolf 发表于 2015-10-29 07:46
average O(n)找前K个就是quickselect呀，只不过找出来的这k个不是按顺序出来的就是了

这里有详细说法
...

再补充下。。
要求按序输出

woaibai 发表于 2015-10-29 07:46
如果知道分数范围的话，比如0-100, 可以用counting sort
lz这是哪个组的？

嗯，但是面试官没说分数范围，所以犹豫了好久没说

面试官是Real-Time的
我投的是BackEnd 和 Growth

可以先用quick selection找到k-th largest 再扫一遍数组找到比它大的吗。。。这样是o(n)?

话说lz是啥时候投的呀，之前同学帮忙内推了一直没有消息

doudoujiejie 发表于 2015-10-29 18:54
可以先用quick selection找到k-th largest 再扫一遍数组找到比它大的吗。。。这样是o(n)?

QuickSelection就直接能返回前K大的吧
不过他要求有序输出。。。

stormy1991 发表于 2015-10-30 04:28
话说lz是啥时候投的呀，之前同学帮忙内推了一直没有消息

我14号推的，16号让我约时间

再催催？

刚收到邮件，已跪

lcl3356897 发表于 2015-10-30 11:40
QuickSelection就直接能返回前K大的吧
不过他要求有序输出。。。

quickselect后再排序吧，因为k是定值，排序是O(1)。

应该就是quick select啊