fb电面二轮，估计要跪，攒攒人品

唉，发个面经攒攒人品吧，估计这轮要跪
第一轮面经在这：
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=169778&page=1#pid2202110

面试官还是个三哥，上来自我介绍，然后让我自我介绍一下，然后就开始coding
第一题:
给一个未排序的数组，里面的数组全是正整数，和一个target数字， 判断数组中是否包含一个连续的子数组，其加和等于target。

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

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

坐等拒信
周五amazon电面，求人品...





补充内容 (2016-2-17 10:31):
还有一轮group match，求经验介绍

补充内容 (2016-2-17 10:31):
fb果然神速，吃了个晚饭就有消息了

对k种值分别做quick select，每次可以disregard已经partial sorted的sub array, 时间复杂度是 O(N)

我又想了一下最后一个followup，可以对quick sort进行优化，因为我们只需要根据category排序，同一category内的数字是不需要排序的，所以进行partition的时候以k/2作为比较值，catgory小于k/2的放到左边，category大于k/2的放到右边。然后对左边和右边再次排序。每次partition的时间复杂度是O(n)，但是因为每次partition可以完成一个category的排序，只需要对剩余k-1个category排序，所以只需要做log(K)轮的排序，时间复杂度是O(nlog(k))，在k比n小很多的情况下还是有很大的优化的

marthew777 发表于 2016-2-17 09:21
对k种值分别做quick select，每次可以disregard已经partial sorted的sub array, 时间复杂度是 O(N)

quickselect是O(n), 即使每次select 能把所有值为k的数都放在正确位置上也需要O(kn)，不然要select n次就是O(n^2)， 如何做到O(n)呢？

我擦，居然过了

marthew777 发表于 2016-2-17 09:21
对k种值分别做quick select，每次可以disregard已经partial sorted的sub array, 时间复杂度是 O(N)

恭喜楼主!!!好棒!
感觉quick select需要用到额外的空间吧~~ 能详细讲一下吗

FB的PhD intern还要match啊？ 楼主怎么样了？
被Google的事情搞的对match都绝望了

这是拿到offer了吗！～

xiyayan32 发表于 2016-2-20 02:18
FB的PhD intern还要match啊？ 楼主怎么样了？
被Google的事情搞的对match都绝望了

还在match...感觉不妙...

linlin1990 发表于 2016-2-20 11:43
这是拿到offer了吗！～

还有一轮team match