h*****k
发帖数: 8 | 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的，还是挂了。发面经攒点人品吧，希望后面的一切顺利。 |
l*******2
发帖数: 36 | 2 怎么检测一个程序为什么慢: 是什么样的程序？实现什么样的功能？大体的workflow有
哪些环节？是不是应该先和面试官交流一下具体的use case? |
x**********a
发帖数: 1372 | |
h*****k
发帖数: 8 | 4 你这个也是个很好的往下说的思路，当时面试官跟我说是个general program. 我就没
问功能，workflow，use case之类的了。感觉他不太care我往哪个思路说，更care在一
些细节的处理上，我是否考虑全面了，是否跟上他的思路。
【在 l*******2 的大作中提到】
: 怎么检测一个程序为什么慢: 是什么样的程序？实现什么样的功能？大体的workflow有
: 哪些环节？是不是应该先和面试官交流一下具体的use case?
|
f******4
发帖数: 51 | |
h*****k
发帖数: 8 | 6 是的
【在 f******4 的大作中提到】
: 楼主面的总部？
|
a***b
发帖数: 19 | 7 Lz是有工作经验的ms还是phd？
不是说new grad不面设计题？ |
k**y
发帖数: 12 | 8 怎么求submatrix的和
--> 请问这题是什么意思啊
i,
【在 h*****k 的大作中提到】
: 是的
|
q*****l
发帖数: 124 | 9 不算成绩。。。还能这么玩。。。
请问面过5轮的都有轮design不算成绩么？ |
h*****k
发帖数: 8 | 10 应该是submatrix所有元素的和，比如指定一个submatrix, 左上角是(1,1) 右下角是 (
2,3) sum = A(1,1) + A(1,2) + A(1,3) + A(2,1) + A(2,2) + A(2,3)
【在 k**y 的大作中提到】
: 怎么求submatrix的和
: --> 请问这题是什么意思啊
:
: i,
|
|
|
h*****k
发帖数: 8 | 11 我是有工作经验的，好像new grad是不面design的
【在 a***b 的大作中提到】
: Lz是有工作经验的ms还是phd？
: 不是说new grad不面设计题？
|
H**********h
发帖数: 99 | 12
请问楼主有多少年工作经验啊？现在F家new grad也是要考design的了。
【在 h*****k 的大作中提到】
: 我是有工作经验的，好像new grad是不面design的
|
Q****a
发帖数: 296 | 13 如果给定左上角和右下角的位置，不是可以两个for loop 把每个元素加一遍么，不太
明白为啥要算（0，0）， （i， j）。
直觉不可能这么简单： ）我觉得我可能没太理解你说的题意吧，可以再说说吗？
(
【在 h*****k 的大作中提到】
: 应该是submatrix所有元素的和，比如指定一个submatrix, 左上角是(1,1) 右下角是 (
: 2,3) sum = A(1,1) + A(1,2) + A(1,3) + A(2,1) + A(2,2) + A(2,3)
|
s**x
发帖数: 7506 | 14 看楼主答的不错。真的有时候要看运气，有些面试官比较严，如果有些磕磕绊绊，也可
能把你干掉。take it easy.
千万记住，人没问就说做过了几乎等于自杀，会的装不会也差不多。 严密的推理最重
要。 |
h*****k
发帖数: 8 | 15 算(0, 0), (i, j)是说事先算好，存储起来，以后查询的时候用这个存起来的结果，就
不需要2个循环了。
【在 Q****a 的大作中提到】
: 如果给定左上角和右下角的位置，不是可以两个for loop 把每个元素加一遍么，不太
: 明白为啥要算（0，0）， （i， j）。
: 直觉不可能这么简单： ）我觉得我可能没太理解你说的题意吧，可以再说说吗？
:
: (
|
t*******e
发帖数: 274 | 16 反转数组和实现iterator有具体代码可以参考么？ |
