太平洋ＶＳ神器？请给些建议# Living
h*k
1 楼
【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: FB onsite 面经 (jobhunting 发不了匿名帖，谁帮忙forward下吧)
发信站: BBS 未名空间站 (Sat Oct 18 14:26:43 2014, 美东)
直接上题吧。
第一面system design. 先问怎么求submatrix的和，回答说先预先计算好 (0, 0), (i,
j)的和，然后可以用这个和求其它的和。以为他会顺着这个问数据大了怎么design
system，结果没有，问了个跟这个题毫不相关的，怎么检测一个程序为什么慢。然后就
回答先确定bottleneck是cpu, disk io, 还是 network io. 然后针对每项他都详细问
怎么做。交流的过程中有时候没太明白他的问题吧。反正这一面的结果很不好，当天就
给我加了另外一面system design. 最后还是挂在这一面上。
第二面coding. 先是 best time to buy and sell stock. 因为之前练过，讲了下思路
就直接写了最优代码。然后他又让写返回两个index 的代码，这个时候有点慌了，因为
没练过这个。。。然后慌忙中还写出了一个bug, 他提醒之后才发现的。改完后又让写
另一个链表相关的题，单链表k个k个分组，反转奇数组。比如 link = 0->1->2->3->4-
>5->6->7, k = 3
返回 2->1->0->3->4->5->7->6. 当时知道会写不完这个题的，所以就尽量先写构架，
把一些细节用函数代替。最后把构架的代码写完了，留了一个反转单链表的函数没写，
刚开始写这个函数的时候下一个面试官来了，就稍微讲了下思路。
第三面 director. 问了下为什么来facebook, 怎么处理conflict，然后跟项目有关的
技术问题。最后让写sqrt(x)二分算法的代码。
第四面 coding. 先问wildcard matching. 写了个暴力搜索的代码，问怎么优化的时候
，说可以记忆化，记住中间结果。然后下一个题。 实现一个iterator, constructer
传入一个二叉排序树，第一次调用next()返回最小的，第二次返回第二小的，第n次返
回最大的，以后返回null. 刚开始提了几个用O(n)空间的方案，都被他否定了，问他是
否需要O(1)空间时，他说不一定要是O(1), 那必然就是O(logn)了，所以就想到了思路
。其实就是树的中序遍历的非递归实现。把栈存到Interator里面，next的时候改变栈
的状态就好了。写完后有一个细节没考虑到，他提醒后改好了，另外constructor 和
next里面用了同样逻辑的代码，也被他指出来了，他还指出了代码里面一个很小的优化。
第五面 system design. 问的是 shorten url. 因为之前准备过这个题，所以回答应该
是非常好的。面试官没问我是否见过这个题，我也就没说我准备过了。
一周后问hr update的时候，说挂了，system design 没过。我说第五面的system
design面得还不错，她说那一面是不算成绩的，再追问的时候，她说不能透露更多
feedback了。有可能是他们觉得我准备过，所以不算成绩，也有可能最后一面就是一个
模拟面试，陪我玩的。。。
哎，非常想去fb的，还是挂了。发面经攒点人品吧，希望后面的一切顺利。
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: FB onsite 面经 (jobhunting 发不了匿名帖，谁帮忙forward下吧)
发信站: BBS 未名空间站 (Sat Oct 18 14:26:43 2014, 美东)
直接上题吧。
第一面system design. 先问怎么求submatrix的和，回答说先预先计算好 (0, 0), (i,
j)的和，然后可以用这个和求其它的和。以为他会顺着这个问数据大了怎么design
system，结果没有，问了个跟这个题毫不相关的，怎么检测一个程序为什么慢。然后就
回答先确定bottleneck是cpu, disk io, 还是 network io. 然后针对每项他都详细问
怎么做。交流的过程中有时候没太明白他的问题吧。反正这一面的结果很不好，当天就
给我加了另外一面system design. 最后还是挂在这一面上。
第二面coding. 先是 best time to buy and sell stock. 因为之前练过，讲了下思路
就直接写了最优代码。然后他又让写返回两个index 的代码，这个时候有点慌了，因为
没练过这个。。。然后慌忙中还写出了一个bug, 他提醒之后才发现的。改完后又让写
另一个链表相关的题，单链表k个k个分组，反转奇数组。比如 link = 0->1->2->3->4-
>5->6->7, k = 3
返回 2->1->0->3->4->5->7->6. 当时知道会写不完这个题的，所以就尽量先写构架，
把一些细节用函数代替。最后把构架的代码写完了，留了一个反转单链表的函数没写，
刚开始写这个函数的时候下一个面试官来了，就稍微讲了下思路。
第三面 director. 问了下为什么来facebook, 怎么处理conflict，然后跟项目有关的
技术问题。最后让写sqrt(x)二分算法的代码。
第四面 coding. 先问wildcard matching. 写了个暴力搜索的代码，问怎么优化的时候
，说可以记忆化，记住中间结果。然后下一个题。 实现一个iterator, constructer
传入一个二叉排序树，第一次调用next()返回最小的，第二次返回第二小的，第n次返
回最大的，以后返回null. 刚开始提了几个用O(n)空间的方案，都被他否定了，问他是
否需要O(1)空间时，他说不一定要是O(1), 那必然就是O(logn)了，所以就想到了思路
。其实就是树的中序遍历的非递归实现。把栈存到Interator里面，next的时候改变栈
的状态就好了。写完后有一个细节没考虑到，他提醒后改好了，另外constructor 和
next里面用了同样逻辑的代码，也被他指出来了，他还指出了代码里面一个很小的优化。
第五面 system design. 问的是 shorten url. 因为之前准备过这个题，所以回答应该
是非常好的。面试官没问我是否见过这个题，我也就没说我准备过了。
一周后问hr update的时候，说挂了，system design 没过。我说第五面的system
design面得还不错，她说那一面是不算成绩的，再追问的时候，她说不能透露更多
feedback了。有可能是他们觉得我准备过，所以不算成绩，也有可能最后一面就是一个
模拟面试，陪我玩的。。。
哎，非常想去fb的，还是挂了。发面经攒点人品吧，希望后面的一切顺利。
