Facebook 第二轮电面

ape047

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

刚面完的facebook题目是find kth largest element in array的变形
给一个array of p

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

omplexity

小哥叫andrian 很有趣

mclover

max heap是nlogk+k, min heap是klogn+n, n大k小的时候用max heap比较好吧

Jester_Z

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

BrilliantBean

请问楼主为何有两轮电面啊

lyburke

求问LZ第一题的思路是什么啊

beer

用heap的话，O(nlgn)
用quick select的话，O(KlgN)

如果K很小, N很大的话，用quick select比较好。如果N和K差不多的话，两种方法差不多。

czbnlzd920706

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

eko910817

beer 发表于 2016-2-12 12:00
用heap的话，O(nlgn)
用quick select的话，O(KlgN)

用k大小的heap就可以了，所以heap应该是 O(nlgk)

beer

eko910817 发表于 2016-2-18 04:24
用k大小的heap就可以了，所以heap应该是 O(nlgk)

exactly.

Jester_Z

beer 发表于 2016-2-18 04:46
exactly.

可以讲一下用quick select 的klgn的思路吗~

beer

Jester_Z 发表于 2016-2-18 05:23
可以讲一下用quick select 的klgn的思路吗~

Sorry. 好像我说错了。Quick Select的average expect time complexity 是 O(n).

An important detail here is that there are indeed O(log n) different iterations here, but not all of them are doing an equal amount of work. Indeed, each iteration does half as much work as the previous iteration. If we ignore the fact that the work is decreasing, you can conclude that the work is O(n log n), which is correct but not a tight bound. This more precise analysis, which uses the fact that the work done keeps decreasing on each iteration, gives the O(n) runtime.

复制代码