facebook面经

发信人: a060601199 (昵称), 信区: JobHunting
标  题: facebook面经
发信站: BBS 未名空间站 (Mon Oct 14 22:19:57 2013, 美东)

已挂

电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)

onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了

onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative

onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n

onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero

最后祝我跟大家都能拿到满意的offer！
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 24.]

http://www.mitbbs.com/article_t/JobHunting/32554229.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

家电大促，京东优惠券京券送不停 ， 更多京东优惠券