F家详细面经，有工作经验被拒(超长慎入)# JobHunting - 待字闺中
w*k
1 楼
简单总结：CS博士，奔5了，申请facebook software engineer，不是headquarter。
onsite后第三天收到据信。估计死在system design上。面试简况如下。详细的在后面。
Screening 和final round头两个都是coding interview，都做到了bug free。题目不
难，即使没刷过题，也容易有思路。唯一不足的是，有一个coding写的代码不是时间复
杂度最低的。虽然后来给出了优化的办法，但是没有时间写优化的代码了。
下一个是system design，感觉不太好。其中一个问题是估计要多少个server，我解答
的时候，最大的失误可能是没有问每秒钟多少个transaction，面试官也没给这个条件
。面试官指出问题后，也没给机会修改。
最后一个人，是career+behavior+coding,coding也是bug free的，其他的问题完全没
感觉。
个人背景：
本人奔5大叔一枚，标准孩奴。不在加州。有名校/名公司情结。可惜，大学在中国30名
以外，来美国读研学校100名以外。毕业时也曾冲刺过Google未果，现在“大”公司混
日子。
最近Facebook recruiter不断骚扰，不是headquarter，这个branch离家也不算太远，
不需要relocation，遂动了邪念。
因为平时很忙，只能吃午饭是在手机上看看career cup上的面试题，开车时想想解法，
有次还差点闯了红灯。汗！
经验教训：
1.奔5的就不要折腾了
2.coding看career cup或者leetcode就可以了。
3.system design就不要准备了。我看了很多，面试时想多了。
HR:
未料到HR这关还挺曲折。给HR回了两年前的email，说我动心了，约好时间
HR：blahblah了五分钟，介绍了这个branch有什么组.你现在做什么？
我：blahblash
HR:你会Java,Python吗？
我：我工作中用C，会一点Java,没用过Python
HR:（好像有点不满意）你对哪个组感兴趣？
我当时懵了，只能捡几个我记下来的（本人记性很差）说了一下，谁料HR都说我的背景
不适合，就说thank you 了。挂了电话我一天都没回过劲。其实我已经开始准备面试了
，就这样结束了？晚上一怒之下，给HR发Email，那你给我一个组适合我背景的！不是
你先跟我联系的吗？HR第二天回信，你做distributed吧，我给你安排screening。靠，
哪个组不是distributed呀？是不是看自己工作量没完成？
Screening:
一个排序二叉树，转换成doubly linked list，还是排序的。
因为我用C，面试官直接给出C的数据结构
struct node{
node* left,
node* right
}
函数返回时，不能有新的node，left指向前一个节点，right指向后一个节点。
我用递归写的。然后：
IO:时间复杂度
我：O(N)
IO:空间复杂度
我：O(logN)，average case
IO:废话，肯定是问average case。那worst case呢？
我： O(N)
IO:给worst case 的例子
我：树的深度为N的时候
IO: Are you sure?
我：（鬼迷心窍了）应该是平衡二叉树的情况
IO: Are you sure?
我：（出汗了！明摆着欺负我这年近半百，头发灰白的码农，想唬晕我。定了定神）树
的深度为N是空间复杂度的worst case.
点评：career cup上看过这道题，可是网上的题目要求没有写清楚，当时也没有细想怎
么做。好久不面试，刚开始白板上写代码的时候，还有点哆嗦。而且中途卡壳了。还好
最后bug free完成了。面试官很精，最后几个are you sure想搞死人！
Final round person 1, coding:
计算vector dot product。我有点晕，what is that?考完研就忘了！ IO给我解释：
A=[a1,a2,a3]
B=[b1,b2,b3]
A和B的dot product是a1*b1+a2*b2+a3*b3
我心里足足盘算了半分钟，想陷阱在哪里。问输入在内存里面能存下来吗。回答可以。
一闭眼，硬着头皮写了一个三行的函数。IO说ok,这才放心。问了时间空间复杂度，然
后大戏出场了。
IO:如果vector很大，内存里放不下。很多值是0。怎么做。原来好戏在这呢！我设计了
一个数据结构
struct item {
int idx;
int val;
}
每一个矢量可以表示成一个item的数组，只有非零值。然后写代码。时间空间复杂度。
IO又问，如果一个矢量有很多非零值，譬如1000个，另一个只有很少几个非零值，怎么
优化。不用写代码。（幸亏不用写代码，要不我要吐血了）。我用一个例子解释我的算
法。譬如
矢量A中非零值的index：1，5，...，2000，2100
矢量B中非零值的index：5，6，1200，2000
对第二个数组每一个值，在第一个数组中做binary search。然后时间空间复杂度。
点评：算很容易的题吧。虽然以前没看见过，很容易有思路。
Final round person 2, coding:
一个小岛，要选址建机场。要修两条跑道，一条南北走向，长度v；一条东西走向，长
度h。两条跑道两端可以一直修到小岛海边。两条跑道在机场中心相交。机场建在哪里v
+h最大。要求函数返回这个最大值。
我问怎么表示这个小岛，IO说由我来决定。我说用一个矩阵表示，陆地用1，海洋用0。
第一个思路：逐行扫描，找出所有东西向的可能的跑道；再逐列扫描，找出所有南北向
的可能的跑道。最后穷举所有可能的组合。IO说，你给个伪代码吧，看看可行性。然后
我写:
for each row
get possible horizontal runways
for each column
get possible vertical runways
max = 0;
for each rw_h in all horizontal runways
for each rw_v in all vertical runways
if ( cross (rw_h, rw_v) is TRUE and rw_h+rw_v > max)
max = rw_h+rw_v
IO说，这里面的逻辑，譬如get possible horizontal runways， 很复杂。你不可能写
完了。换个办法。我心里面嘀咕，这个算法可是时间复杂度低呀。
第二个思路：上brute force吧。对矩阵中的每一个元素，水平方向向左向右扫描，直
到碰到海洋。垂直方向向上向下扫描，直到碰到海洋。所有元素都扫描过，就直到最大
值了。IO说代码吧。写的过程中，我用了两个子函数，分别是扫描垂直方向和水平方向
的。IO让我写一个就可以了。刚写完，IO说有bug。还好，我自己找出来了。
IO：如果矩阵N行N列，时间复杂度。
我：O(N^3)。
IO：这个算法可以优化到O(N^2），但是我们没时间了
我心里很想踢他，前面第一个思路还让我写伪代码，浪费很多时间。不过我灵机一动，
想起以前看过的一道类似的题，赶快说出优化办法。例如，某一行是
0 1 1 1 1 0 0 0 1 1 0
扫描一遍，得到
0 4 4 4 4 0 0 0 2 2 0
每个非零值表示已该点为中心，最长的东西方向跑道长度。南北方向同样做一遍，就可
以了。
一点插曲：因为我写函数第一个参数写成 int* a[].IO让我说int** 和 int* a[]的区
别。
点评：这个题目容易有思路，但是想有优化的解法，不容易。写代码的过程中也容易出
bug.我在career cup上看到一个道类似的:一个矩阵，元素非0即1，让找最大的十字，
十字上每个元素都必须是1.我当时已经想到了O(N*N)的解法，可是面试的时候，一开始
没有反应过来。
Final round person 3, system design:
面试前还做了一个梦，让我设计facebook messenger，我画图，从白版一直到地上，打
开门继续画，来了一个developer给我了一杯啤酒，我喝完直接躺到我画的图上:-)结果
遇到的问题大相径庭！
IO：我们现在要设计一个facebook privacy system. 假设facebbook现在没有这个
feature。 每一个resource，譬如post, image, video,只有owner和owner的friends可
以看到。
我：画了一个三层结构的图。客户端，web service, database。需要添加一个
resource table，标明每个resource的owner，或者在现有的table中添加一个列。另外
假设facebook已经有一个friend table存储用户之间的朋友关系
IO：那你怎么设计这个friend table表示朋友关系？
我：（咯噔一下，怎么问题跨度这么大）我有两个方案。方案1:两个column，user和
friends.假设A有三个朋友B，C，D，对应一条记录，user is A, friends is “B,C,D
” （我准备面试的时候考虑过friend table的问题。看网上说,facebook的大部分信息
都是key value pair存储了，就有了这个想法，好处是select的时候只返回一条记录，
估计面试官不喜欢这个方案）。方案2：两个column，user和friend.同样的例子，要三
条记录(A,B), (A,C), (A,D)
IO：I am confused，你到底要用哪个方案？
我：（心里觉得IO不爽了）方案1。因为读取一个用户的朋友的时候，只返回一条记录
。方案2要返回很多条记录，很耗时间，因为要读硬盘。
IO：如果有很多用户，一个服务器上放不下这个table，怎么sharding到多个服务器上？
我：根据user column，计算hash value。根据hash value分配到不同的服务器上。
IO：如果一个用户很多朋友，friends column可能很长。如果要update 这个column，
譬如删掉一个朋友，需要操作一个很长的字符串，很耗时。
我：（我当时想，操作很长的字符串是在cpu上完成的，和磁盘操作时间不是一个数量
级，但是没有和IO硬碰硬）我没有考虑这个问题。如果update是个问题的话，那我用方
案2。
IO：（给了一个例子，大概四五个用户，标明用户之间的朋友关系）那怎么用你的方案
表示这个朋友关系。
我：（给出例子，不难）
IO：那怎么查询一个用户所有的friend？要查询多少台机器，如果table使用了
sharding?
我：(迟疑了一下）那得查询所有的机器。（我以为他会让我优化，谁知道...）
IO：(马上问)那你估计一下要多少台服务器存放这个table？
我：facebook一共多少用户，每个用户平均几个friends?
IO：（给了个大概的数字）
我：（我直接算friend table的大小，给出个服务器的数量）
IO：这么少的服务器能处理那么多transaction吗？
我：（糟糕！！！）处理不了。我没有考虑。（正想问IO每秒钟多少个transaction,IO
根本没给机会，接着问）
IO：那刚才我问怎么查询一个用户所有的friend，你说要查询所有的机器。有没有办法
只查询一台机器。
我：（想了半分钟）如果A和B是朋友关系，放两条记录，（A,B）和（B,A），第一条记
录放在Hash(A)对应的机器上，第二条记录放在Hash（B)对应的机器上。
IO：写一个函数的伪代码，判断一个指定的用户能不能看一个指定的resouce。
我：（这个我不怵，刷刷刷写完）
IO：（现在才露出一点点笑容）完事！
点评：
1.最后一根稻草是估算多少个服务器，完全没有设计分布式系统的概念。IO也很无情，
没有给修改答案的机会.
2.用一个长字符串存储一个用户的所有朋友是一个败笔!
3. 讨论如何sharding这个table的时候，如果说按照用户地理位置sharding会更好一些。
Final round person 4, career+behavior+coding
先问了很多behavior方面的问题，然后一个coding
尽可能列出所有问题(肯定有遗漏，而且IO经常在我的答案的基础上给出新的问题，就
不方便写在这里了)：
1.为什么来facebook?
2.你现在做什么？
3. 一个project，如何说服别人用你的solution？
4.如果你和同组的一个人一起开发一个project，不配合你工作，拖后腿。你怎么办？
如果这个人不是你们组的，怎么办？
5.给出一个你以前做过的project,到后期才发现有一个更好的design.
Coding问题如下：
一个数组，最大值可能出现多次。要求等概率返回最大值的位置。例如:
(1, 10, 4, 10, 2, 10)
应该以各1/3的概率返回1, 3, 5.
这个问题看似很容易，但是，如果没有任何优化，需要扫描数组三次。如果用
reservoir sampling，只需要扫描数组一次。我虽然看过这道题，但是没有仔细研究，
担心reservoir sampling说不清楚，所以写了一个代码，需要扫描数组两次。bug free
.因为没有时间，IO没有要求优化，也没有时间空间内复杂度。
onsite后第三天收到据信。估计死在system design上。面试简况如下。详细的在后面。
Screening 和final round头两个都是coding interview，都做到了bug free。题目不
难，即使没刷过题，也容易有思路。唯一不足的是，有一个coding写的代码不是时间复
杂度最低的。虽然后来给出了优化的办法，但是没有时间写优化的代码了。
下一个是system design，感觉不太好。其中一个问题是估计要多少个server，我解答
的时候，最大的失误可能是没有问每秒钟多少个transaction，面试官也没给这个条件
。面试官指出问题后，也没给机会修改。
最后一个人，是career+behavior+coding,coding也是bug free的，其他的问题完全没
感觉。
个人背景：
本人奔5大叔一枚，标准孩奴。不在加州。有名校/名公司情结。可惜，大学在中国30名
以外，来美国读研学校100名以外。毕业时也曾冲刺过Google未果，现在“大”公司混
日子。
最近Facebook recruiter不断骚扰，不是headquarter，这个branch离家也不算太远，
不需要relocation，遂动了邪念。
因为平时很忙，只能吃午饭是在手机上看看career cup上的面试题，开车时想想解法，
有次还差点闯了红灯。汗！
经验教训：
1.奔5的就不要折腾了
2.coding看career cup或者leetcode就可以了。
3.system design就不要准备了。我看了很多，面试时想多了。
HR:
未料到HR这关还挺曲折。给HR回了两年前的email，说我动心了，约好时间
HR：blahblah了五分钟，介绍了这个branch有什么组.你现在做什么？
我：blahblash
HR:你会Java,Python吗？
我：我工作中用C，会一点Java,没用过Python
HR:（好像有点不满意）你对哪个组感兴趣？
我当时懵了，只能捡几个我记下来的（本人记性很差）说了一下，谁料HR都说我的背景
不适合，就说thank you 了。挂了电话我一天都没回过劲。其实我已经开始准备面试了
，就这样结束了？晚上一怒之下，给HR发Email，那你给我一个组适合我背景的！不是
你先跟我联系的吗？HR第二天回信，你做distributed吧，我给你安排screening。靠，
哪个组不是distributed呀？是不是看自己工作量没完成？
Screening:
一个排序二叉树，转换成doubly linked list，还是排序的。
因为我用C，面试官直接给出C的数据结构
struct node{
node* left,
node* right
}
函数返回时，不能有新的node，left指向前一个节点，right指向后一个节点。
我用递归写的。然后：
IO:时间复杂度
我：O(N)
IO:空间复杂度
我：O(logN)，average case
IO:废话，肯定是问average case。那worst case呢？
我： O(N)
IO:给worst case 的例子
我：树的深度为N的时候
IO: Are you sure?
我：（鬼迷心窍了）应该是平衡二叉树的情况
IO: Are you sure?
我：（出汗了！明摆着欺负我这年近半百，头发灰白的码农，想唬晕我。定了定神）树
的深度为N是空间复杂度的worst case.
点评：career cup上看过这道题，可是网上的题目要求没有写清楚，当时也没有细想怎
么做。好久不面试，刚开始白板上写代码的时候，还有点哆嗦。而且中途卡壳了。还好
最后bug free完成了。面试官很精，最后几个are you sure想搞死人！
Final round person 1, coding:
计算vector dot product。我有点晕，what is that?考完研就忘了！ IO给我解释：
A=[a1,a2,a3]
B=[b1,b2,b3]
A和B的dot product是a1*b1+a2*b2+a3*b3
我心里足足盘算了半分钟，想陷阱在哪里。问输入在内存里面能存下来吗。回答可以。
一闭眼，硬着头皮写了一个三行的函数。IO说ok,这才放心。问了时间空间复杂度，然
后大戏出场了。
IO:如果vector很大，内存里放不下。很多值是0。怎么做。原来好戏在这呢！我设计了
一个数据结构
struct item {
int idx;
int val;
}
每一个矢量可以表示成一个item的数组，只有非零值。然后写代码。时间空间复杂度。
IO又问，如果一个矢量有很多非零值，譬如1000个，另一个只有很少几个非零值，怎么
优化。不用写代码。（幸亏不用写代码，要不我要吐血了）。我用一个例子解释我的算
法。譬如
矢量A中非零值的index：1，5，...，2000，2100
矢量B中非零值的index：5，6，1200，2000
对第二个数组每一个值，在第一个数组中做binary search。然后时间空间复杂度。
点评：算很容易的题吧。虽然以前没看见过，很容易有思路。
Final round person 2, coding:
一个小岛，要选址建机场。要修两条跑道，一条南北走向，长度v；一条东西走向，长
度h。两条跑道两端可以一直修到小岛海边。两条跑道在机场中心相交。机场建在哪里v
+h最大。要求函数返回这个最大值。
我问怎么表示这个小岛，IO说由我来决定。我说用一个矩阵表示，陆地用1，海洋用0。
第一个思路：逐行扫描，找出所有东西向的可能的跑道；再逐列扫描，找出所有南北向
的可能的跑道。最后穷举所有可能的组合。IO说，你给个伪代码吧，看看可行性。然后
我写:
for each row
get possible horizontal runways
for each column
get possible vertical runways
max = 0;
for each rw_h in all horizontal runways
for each rw_v in all vertical runways
if ( cross (rw_h, rw_v) is TRUE and rw_h+rw_v > max)
max = rw_h+rw_v
IO说，这里面的逻辑，譬如get possible horizontal runways， 很复杂。你不可能写
完了。换个办法。我心里面嘀咕，这个算法可是时间复杂度低呀。
第二个思路：上brute force吧。对矩阵中的每一个元素，水平方向向左向右扫描，直
到碰到海洋。垂直方向向上向下扫描，直到碰到海洋。所有元素都扫描过，就直到最大
值了。IO说代码吧。写的过程中，我用了两个子函数，分别是扫描垂直方向和水平方向
的。IO让我写一个就可以了。刚写完，IO说有bug。还好，我自己找出来了。
IO：如果矩阵N行N列，时间复杂度。
我：O(N^3)。
IO：这个算法可以优化到O(N^2），但是我们没时间了
我心里很想踢他，前面第一个思路还让我写伪代码，浪费很多时间。不过我灵机一动，
想起以前看过的一道类似的题，赶快说出优化办法。例如，某一行是
0 1 1 1 1 0 0 0 1 1 0
扫描一遍，得到
0 4 4 4 4 0 0 0 2 2 0
每个非零值表示已该点为中心，最长的东西方向跑道长度。南北方向同样做一遍，就可
以了。
一点插曲：因为我写函数第一个参数写成 int* a[].IO让我说int** 和 int* a[]的区
别。
点评：这个题目容易有思路，但是想有优化的解法，不容易。写代码的过程中也容易出
bug.我在career cup上看到一个道类似的:一个矩阵，元素非0即1，让找最大的十字，
十字上每个元素都必须是1.我当时已经想到了O(N*N)的解法，可是面试的时候，一开始
没有反应过来。
Final round person 3, system design:
面试前还做了一个梦，让我设计facebook messenger，我画图，从白版一直到地上，打
开门继续画，来了一个developer给我了一杯啤酒，我喝完直接躺到我画的图上:-)结果
遇到的问题大相径庭！
IO：我们现在要设计一个facebook privacy system. 假设facebbook现在没有这个
feature。 每一个resource，譬如post, image, video,只有owner和owner的friends可
以看到。
我：画了一个三层结构的图。客户端，web service, database。需要添加一个
resource table，标明每个resource的owner，或者在现有的table中添加一个列。另外
假设facebook已经有一个friend table存储用户之间的朋友关系
IO：那你怎么设计这个friend table表示朋友关系？
我：（咯噔一下，怎么问题跨度这么大）我有两个方案。方案1:两个column，user和
friends.假设A有三个朋友B，C，D，对应一条记录，user is A, friends is “B,C,D
” （我准备面试的时候考虑过friend table的问题。看网上说,facebook的大部分信息
都是key value pair存储了，就有了这个想法，好处是select的时候只返回一条记录，
估计面试官不喜欢这个方案）。方案2：两个column，user和friend.同样的例子，要三
条记录(A,B), (A,C), (A,D)
IO：I am confused，你到底要用哪个方案？
我：（心里觉得IO不爽了）方案1。因为读取一个用户的朋友的时候，只返回一条记录
。方案2要返回很多条记录，很耗时间，因为要读硬盘。
IO：如果有很多用户，一个服务器上放不下这个table，怎么sharding到多个服务器上？
我：根据user column，计算hash value。根据hash value分配到不同的服务器上。
IO：如果一个用户很多朋友，friends column可能很长。如果要update 这个column，
譬如删掉一个朋友，需要操作一个很长的字符串，很耗时。
我：（我当时想，操作很长的字符串是在cpu上完成的，和磁盘操作时间不是一个数量
级，但是没有和IO硬碰硬）我没有考虑这个问题。如果update是个问题的话，那我用方
案2。
IO：（给了一个例子，大概四五个用户，标明用户之间的朋友关系）那怎么用你的方案
表示这个朋友关系。
我：（给出例子，不难）
IO：那怎么查询一个用户所有的friend？要查询多少台机器，如果table使用了
sharding?
我：(迟疑了一下）那得查询所有的机器。（我以为他会让我优化，谁知道...）
IO：(马上问)那你估计一下要多少台服务器存放这个table？
我：facebook一共多少用户，每个用户平均几个friends?
IO：（给了个大概的数字）
我：（我直接算friend table的大小，给出个服务器的数量）
IO：这么少的服务器能处理那么多transaction吗？
我：（糟糕！！！）处理不了。我没有考虑。（正想问IO每秒钟多少个transaction,IO
根本没给机会，接着问）
IO：那刚才我问怎么查询一个用户所有的friend，你说要查询所有的机器。有没有办法
只查询一台机器。
我：（想了半分钟）如果A和B是朋友关系，放两条记录，（A,B）和（B,A），第一条记
录放在Hash(A)对应的机器上，第二条记录放在Hash（B)对应的机器上。
IO：写一个函数的伪代码，判断一个指定的用户能不能看一个指定的resouce。
我：（这个我不怵，刷刷刷写完）
IO：（现在才露出一点点笑容）完事！
点评：
1.最后一根稻草是估算多少个服务器，完全没有设计分布式系统的概念。IO也很无情，
没有给修改答案的机会.
2.用一个长字符串存储一个用户的所有朋友是一个败笔!
3. 讨论如何sharding这个table的时候，如果说按照用户地理位置sharding会更好一些。
Final round person 4, career+behavior+coding
先问了很多behavior方面的问题，然后一个coding
尽可能列出所有问题(肯定有遗漏，而且IO经常在我的答案的基础上给出新的问题，就
不方便写在这里了)：
1.为什么来facebook?
2.你现在做什么？
3. 一个project，如何说服别人用你的solution？
4.如果你和同组的一个人一起开发一个project，不配合你工作，拖后腿。你怎么办？
如果这个人不是你们组的，怎么办？
5.给出一个你以前做过的project,到后期才发现有一个更好的design.
Coding问题如下：
一个数组，最大值可能出现多次。要求等概率返回最大值的位置。例如:
(1, 10, 4, 10, 2, 10)
应该以各1/3的概率返回1, 3, 5.
这个问题看似很容易，但是，如果没有任何优化，需要扫描数组三次。如果用
reservoir sampling，只需要扫描数组一次。我虽然看过这道题，但是没有仔细研究，
担心reservoir sampling说不清楚，所以写了一个代码，需要扫描数组两次。bug free
.因为没有时间，IO没有要求优化，也没有时间空间内复杂度。
