一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1374|回复: 13
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
jmexe 发表于 2016-2-17 07:09:10 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

面试官还是个三哥,上来自我介绍,然后让我自我介绍一下,然后就开始coding
第一题:
给一个未排序的数组,里面的数组全是正整数,和一个target数字, 判断数组中是否包含一个连续的子数组,其加和等于target。
很快答完,问了时间复杂度,然后让我自己写test case,然后下一题。
第二题:
Sort Colors的变种
给一个getCategory(int num) 函数,返回一个字符表示输入数字的类别,可能的类别包括(Low, Medium, High)。 然后给一个数组,按照类别L->M->H的顺序排列
我说one pass就可以,然后写代码。写完后他给了一个数组,然后让我给他过一遍这个程序是如何把这个数组排好的,过完之后又问了问时间复杂度。. 鍥磋鎴戜滑@1point 3 acres
Follow Up:
他说如果getCategory()返回的category有k种值怎么办。
我说如果可以用Extra Memory的话就用counting sort,不能的话用quicksort。
他让我写了counting sort的伪代码。然后问了quicksort的时间复杂度。
最后问我能不能不用extra memory但是比quicksort还要快,我就傻眼了...我说这有点难啊,如果给你的数组的值是在1-k范围内的话可以用in-place的conting sort,你这个给的数组连个范围都没有。最后乱答了个时间复杂度很高的方法,他说"you're very close",我就无语了...

最后也没想出来更优的办法,还是准备不足啊,三哥让我问问题,我说你能给我讲讲最优的方法不,他一个劲说"no worry",然后让我问别的问题,聊了两句就挂电话了...
看着情况估计是过不了啦,坐等拒信
周五amazon电面,求人品...
. Waral 鍗氬鏈夋洿澶氭枃绔,


. Waral 鍗氬鏈夋洿澶氭枃绔,

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

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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

marthew777 发表于 2016-2-17 09:21:41 | 显示全部楼层
对k种值分别做quick select,每次可以disregard已经partial sorted的sub array, 时间复杂度是 O(N)
回复 支持 1 反对 0

使用道具 举报

 楼主| jmexe 发表于 2016-2-17 10:30:16 | 显示全部楼层
我擦,居然过了
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-17 11:15:18 | 显示全部楼层
marthew777 发表于 2016-2-17 09:21
对k种值分别做quick select,每次可以disregard已经partial sorted的sub array, 时间复杂度是 O(N)

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

使用道具 举报

iwofr 发表于 2016-2-18 04:01:38 | 显示全部楼层
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)呢?
回复 支持 反对

使用道具 举报

 楼主| jmexe 发表于 2016-2-18 04:09:41 | 显示全部楼层
我又想了一下最后一个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小很多的情况下还是有很大的优化的
回复 支持 反对

使用道具 举报

xiyayan32 发表于 2016-2-20 02:18:59 | 显示全部楼层
FB的PhD intern还要match啊? 楼主怎么样了?
被Google的事情搞的对match都绝望了
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-2-20 11:43:27 | 显示全部楼层
这是拿到offer了吗!~
回复 支持 反对

使用道具 举报

 楼主| jmexe 发表于 2016-2-20 12:32:49 | 显示全部楼层
xiyayan32 发表于 2016-2-20 02:18.1point3acres缃
FB的PhD intern还要match啊? 楼主怎么样了?
被Google的事情搞的对match都绝望了

还在match...感觉不妙...
回复 支持 反对

使用道具 举报

 楼主| jmexe 发表于 2016-2-20 12:33:11 | 显示全部楼层
linlin1990 发表于 2016-2-20 11:43
这是拿到offer了吗!~

还有一轮team match
回复 支持 反对

使用道具 举报

xiyayan32 发表于 2016-2-20 23:15:11 | 显示全部楼层
jmexe 发表于 2016-2-20 12:32
还在match...感觉不妙...

FB的pool有多大啊?不会像google家一样是个无比巨大的pool吧
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-2-21 00:49:12 | 显示全部楼层
team match失败率大概是多少呢
回复 支持 反对

使用道具 举报

returning 发表于 2016-2-21 11:06:51 | 显示全部楼层
qucik sort是nlg,如果已知返回category只有k种的话,那么就是k*n时间可以inplace. 其实就是按照sort 3 colors的思路,先是sort 1 和k,然后sort 2, k-1。真正时间肯定小于k*n,但是n的时间是做不到的。
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-2-22 11:51:07 | 显示全部楼层
returning 发表于 2016-2-21 11:06
qucik sort是nlg,如果已知返回category只有k种的话,那么就是k*n时间可以inplace. 其实就是按照sort 3 col ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
time complexity for quick sort is O(n)
worst case is O(n^2)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 03:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表