Facebook面经！（Uber Zillow MSFT

Facebook
一面：meeting room II
二面：input：二维平面上很多点，以及一个target点；output：离target最近的k个点
用quickselect做（面试官是caltec

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

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

oncampus是个中序遍历。。。。。我觉得很神奇，到现在所有的面试都是一道题，圆润的暑假全靠放水！！祝大家好运！！！

小A要当码农 发表于 2015-11-27 00:01
求问 quick select是什么意思呀。。这题我只会用最小堆。。

是快排的思想，partition之后返回的数组，左半部分全部小于右半部分，数数有几个，够k了在左边递归找前k个，不够k在右边递归找不够的个数。。。。不太懂的话可以看这个https://www.youtube.com/watch?v=aOhyCdxGJvY

begg930 发表于 2015-11-27 00:09
是快排的思想，partition之后返回的数组，左半部分全部小于右半部分，数数有几个，够k了在左边递归找前k ...

额，多谢告知啦， 但是这个方法不能保证O(n)呀？ 最坏情况还是O（n^2）吧？

begg930 发表于 2015-11-27 00:09
是快排的思想，partition之后返回的数组，左半部分全部小于右半部分，数数有几个，够k了在左边递归找前k ...

楼主这个题是不是其实是一个加强版的find kth largest number

请问楼主，facebook第二题是建一个class见面放x y 和笛卡尔距离吗，然后快排吗？

bobzhang2004 发表于 2015-11-26 01:51
请问楼主，facebook第二题是建一个class见面放x y 和笛卡尔距离吗，然后快排吗？

对的~对ddddddddddddddddddd

bobzhang2004 发表于 2015-11-26 01:51
请问楼主，facebook第二题是建一个class见面放x y 和笛卡尔距离吗，然后快排吗？

啊 不对，不是快排，是quick select，O(n)的

begg930 发表于 2015-11-26 05:21
啊 不对，不是快排，是quick select，O(n)的

谢谢，口误, 是quick select

begg930 发表于 2015-11-26 02:22
对的~对ddddddddddddddddddd

求问 quick select是什么意思呀。。这题我只会用最小堆。。

小A要当码农 发表于 2015-11-27 00:33
额，多谢告知啦， 但是这个方法不能保证O(n)呀？ 最坏情况还是O（n^2）吧？

算法导论上证明的是O(n)

begg930 发表于 2015-11-27 01:14
算法导论上证明的是O(n)

嗯嗯，应该是average case O(n), 刚写了一下，感觉好容易出bug。。。 多谢楼主的分享啦，