FB Intern 一面

受到地里的帮助，准备FB面试。特此献上热腾腾的面经。
一个国人小哥的面试。人很Nice， 聊了大概4-5分钟， 开始做题。

从N个点中找到离原点第K近的点。
讨论了直接sort, quickselect, heap各种

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

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

补充内容 (2017-2-14 06:12):
FB速度真快，一个半小时就通知约第二轮了~~

magichqg 发表于 2017-2-15 06:29
N固定，K很大的时候，maintain 一个 N-k+1大小的max heap，这样heap pop出来的就是第k小的，不需要再trav ...

应该是min heap吧。。。。

ericshape123 发表于 2017-2-14 05:30
请问楼主, k很大相对于N来说么？难道是反过来求第N  - k + 1远?

对的，构造一个max heap 求N - k + 1远

请教一下楼主，如果是仅仅找第K个近的点，那直接quickselect用O(n)的时间就可以找到了把。
如果是找前K个近的所有点的话，如果不要求排序，先quickselect用O(n)的时间找到第k个近的点，然后在traverse所有点，凡是比这个点更近的才保留，这样也是O(n)就够了。
如果所有点要排序的话，那只能用max_heap了，就是O(nlog(k))了。

lz知道fb大概什么时候说一面的结果吗？

请问楼主, k很大相对于N来说么？难道是反过来求第N  - k + 1远?

结果好迅速，马上通知有二轮了

二轮是电话还是onsite还是可以自己选呢？

所以当K值非常大的时候应该怎么办呢

求问楼主k非常大的情况？是maintain一个长度为n-k大的heap，存n-k largest，然后再traverse所有的点，找到不在这个heap里面的吗？感觉这样复杂度并不小啊。。heap是nlog(n-k),但是再traverse感觉是O(nk)啊？是不是我哪里想的不对，求教楼主~~~

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

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

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

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