s*****r 发帖数: 43070 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: wsclock (精确), 信区: JobHunting
标 题: F家详细面经,有工作经验被拒(超长慎入)
关键字: facebook,interview
发信站: BBS 未名空间站 (Fri Sep 22 20:45:31 2017, 美东)
简单总结: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没有要求优化,也没有时间空间内复杂度。 |
s*****r 发帖数: 43070 | 2 老留混得太悲催了,年过半百的CS PHD,还要去回答这些垃圾问题 |
n********g 发帖数: 6504 | 3 Facebook在扩建。目测要扩大一倍。俺这样的土本科最不值钱的就是面子,不怕小妞面
试我垃圾问题。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老留混得太悲催了,年过半百的CS PHD,还要去回答这些垃圾问题
|
d*****u 发帖数: 17243 | 4 考PHD做题本身就是一种羞辱。就是这些IT公司带坏的 |
t******l 发帖数: 10908 | 5 估计就是想工资单上多点钱,也算是人之常情。
但老实说奔五的孩奴混滋傻真心没必要折腾。面试抱着练习和玩玩的心态即可,得知我
幸、不得我命 。。。 其实得了也不好说,后面还有 bootcanp 和 PIP 。。。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老留混得太悲催了,年过半百的CS PHD,还要去回答这些垃圾问题
|
i*****t 发帖数: 9074 | 6 洗脚哥你把你扔Top2简历的那段等出来一定很精彩。。。
面。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老留混得太悲催了,年过半百的CS PHD,还要去回答这些垃圾问题
|
t******l 发帖数: 10908 | 7 Facebook 没有那么多非 Top 2 不可的岗位 。。。 录用标准高更多的原因是有钱可少
,竞争者多就水涨船高 。。。 这种情况,孩奴工作不那么努力,可能也容易拿 PIP
。。。
【在 i*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 洗脚哥你把你扔Top2简历的那段等出来一定很精彩。。。 : : 面。
|
n********g 发帖数: 6504 | 8 所以我target E3呀。
收入再高有村姑在也就是为龙虾党交税。收入再低即使离了婚也是村姑多给赡养费而已。
重点是多点时间泡妞呀。
【在 t******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Facebook 没有那么多非 Top 2 不可的岗位 。。。 录用标准高更多的原因是有钱可少 : ,竞争者多就水涨船高 。。。 这种情况,孩奴工作不那么努力,可能也容易拿 PIP : 。。。
|
n********g 发帖数: 6504 | 9 苦主不是top 2的。本科学校只比交大哥高十几位而已。
【在 i*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 洗脚哥你把你扔Top2简历的那段等出来一定很精彩。。。 : : 面。
|
t******l 发帖数: 10908 | 10 多草几十次碧能解决的问题,就不要考虑离婚了。
: 所以我target E3呀。
: 收入再高有村姑在也就是为龙虾党交税。收入再低即使离了婚也是村姑多给赡养
费而已。
: 重点是多点时间泡妞呀。
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 苦主不是top 2的。本科学校只比交大哥高十几位而已。
|
|
|
i*****t 发帖数: 9074 | 11 所以我说不够精彩啊。。。。
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 苦主不是top 2的。本科学校只比交大哥高十几位而已。
|
c*******a 发帖数: 1879 | 12 你怎么也知道PIP?
莫非你也是马农?
半夜鸡叫被ONCALL?
【在 t******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计就是想工资单上多点钱,也算是人之常情。 : 但老实说奔五的孩奴混滋傻真心没必要折腾。面试抱着练习和玩玩的心态即可,得知我 : 幸、不得我命 。。。 其实得了也不好说,后面还有 bootcanp 和 PIP 。。。
|
s*****r 发帖数: 43070 | 13 隔三差五给俺发小传单,还邀请俺去吃饭,想想那么累,还是在狗家舒服,每天一半时
间在发呆
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Facebook在扩建。目测要扩大一倍。俺这样的土本科最不值钱的就是面子,不怕小妞面 : 试我垃圾问题。
|
i*****t 发帖数: 9074 | 14 那你还不写一段扔简历的?
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 隔三差五给俺发小传单,还邀请俺去吃饭,想想那么累,还是在狗家舒服,每天一半时 : 间在发呆
|
n********g 发帖数: 6504 | 15 你要去了FB上班通勤从5分钟变成30分钟。宾夕法尼亚的房子岂不是买亏了。
我在非盟,FB是通勤最近的FANG了吧。你狗通勤实在糟糕,真是给钱都不去。每天把
101堵了多少个小时。
【在 s*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 隔三差五给俺发小传单,还邀请俺去吃饭,想想那么累,还是在狗家舒服,每天一半时 : 间在发呆
|
n********g 发帖数: 6504 | 16 俺总觉得石崩别是俺同学吧。害怕ing。虽然可能性不大。
【在 c*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你怎么也知道PIP? : 莫非你也是马农? : 半夜鸡叫被ONCALL?
|