Facebook onsite 面经汇总 1

Tags: ,

2013(10-12月) 码农类 硕士 实习@Facebook – 校园招聘会 – Onsite 校园招聘会 |Pass

实际上我FB的offer2个多月前就拿了, 当时一直想发个帖分享经验, 但是当时竟然没有发现面经版… .

闲话少说, 当时facebook网申和career fair都投过简历, 后来在career fair一周后收到了on-campus面试通知。入围面试的人实际上并不是很多, 我觉得我能被选中是因为我在career fair上和一个FB的员工聊了一下以前做的项目, 他似乎也对我说的挺感兴趣, 再加上简历也写得不错, 所以我就荣幸地入围面试了吧。所以说, career fair大家还是要重视的, 不要草草地扔了简历就了事, 要尽可能地和展台上的员工沟通一下。

当时on-campus面试是我来美帝的第一面, 觉得特别紧张。他问的题是Dynamic Programming中最经典的问题coin change, 就是给定一个面额(比如100), 以及一些不同面额的硬币(2,3,5), 求所有的硬币组合, 使得他们的面额之和为100. 当时我还不懂DP, 所以就只提供了一个brute-force的解法, 就是假设100 = 2i+ 3j +5k, 先遍历所有的j和k, 然后看剩下的100-3j-5k是不是偶数。正确的解法应该是用DP, 大家可以去google一下, 结果很多。当时是一个45分钟的面试, 按理说应该要做两道题, 我却只做了一道, 当时觉得估计跪了, 不过老天保佑, 我竟然又庆幸地进入了on-site面试。

on-site面试题觉得更简单, 有两道题, 不过我现在就记得后一道了。问的就是给你一个字符串的list, 把它们重新排序一下, 使得互为anagram的词放在一块。对于anagram的题, 一般情况下只要把所有字符串按字母表顺序重新排列一下就成了, 这题也不例外, 如果是Java写的话, 只用自己写一个判断两个词是否为anagram的comparator就行了。

on-site之后的第四天我就收到了offer,能在那么早的时候收到facebook这么好的offer, 我只能说我这肯定是我上半辈子积下的德。facebook是一个效率超高的公司, 从我第一轮面试到最终收到offer, 只花了不到一个月的时间, 非常符合它的”Move fast and Break things”的理念。并且从面试过程中, 我能感觉到facebook的员工之间的交流成本肯定很低, 所有的邮件都是简洁到极致, 不像我面Google的时候邮件里面各种rules, tips写一大堆(作为一个被Google拒的人, 我觉得我没有资格黑它..)。

另外, 我觉得面试的时候要注意以下两个方面:
1) 多和面试官沟通, 边写代码的时候边说自己的想法, 不要只自顾自地写代码而把面试官晾在一边。说完想法的时候, 问一下:”Does it make sense to you?”, 一来可以和面试官进行沟通, 二来也可以确认面试官明白了你的想法。
2) 尽量避免代码中的漏洞, 不要等到面试官指出来, 要尽量自己发现, 当然能一口气写出来一个bug-free的代码更好。我曾经以为只要做对了题就一定能过面试, 但我Google也是做对了所有题, 可是最终还是被拒了。我猜测是我写代码的时候有几次让面试官指出了其中的错误, 减了很多印象分。

能分享的也就这么多了, 希望大家都有能找到好的实习。 

 

2015(10-12月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Passfresh grad应届毕业生

uni day, 大概40多个人吧,不过貌似一半都是Intern

1. lc那个括号题,新出的,不过我面的时候还没有出,面完几天就出了。+各种FOLLOW UP
. 1point 3acres 璁哄潧
2. behavior + project

3. “43868643” 中间放+, – 计算能不能达到一个target, 复杂度多少?如何优化?
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
4. Post order iterator, 然后问了TEST CASE设计之类的,还有一些莫名其妙的复杂度问题答的奇奇怪怪的. from: 1point3acres.com/bbs

FB今年拿面试很难,感谢我给力的内推人,他的帖子: http://www.1point3acres.com/bbs/ … adio%26sortid%3D192

没有内推人面试拿不到啊。。。

感受:一定要Bug free一定要。。然后多刷刷面经吧。。。然后culture fit注意了解fb的文化吧(move fast)。。。另外3天出结果。pkg一般吧,今年好的都给intern了,不过谁叫fb好呢。。。怎么说呢在我心里fb的地位超过google..

2013(1-3月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Pass

实在很感谢论坛里的内推,还有大量分享面经的亲们。背景是国内微电子985,硕士转Computer engineer中途再转软件,40+排名学校gpa3.9。4个月实习经验(中型公司)。其中过程也是特别辛酸挂了无数公司 呆在无数冷宫都要放弃了去小公司了,没想到最后在luck和4遍leetcode(最后一遍每天20道)助力下斩获facebook。

因为签了啥NDA…我就聊聊我做的一些有趣的题目和准备面试,基本来自leetcode,如跟面试雷同,纯属巧合。

1. 简单5题游string to int、palindrome string、palindrome int、linkedlist int palindrome(iterate & recursion)认真implement并且除bug.
2. 印度哥最喜欢让人弄prefix tree的构建和搜索和优化(带regular expression的“.”
3. 美国人听说我做题多,总是出一些怪题,find longest subarray 等于0 还要O(n)话leetcode那道find max retangle in boolean 2d array真是有趣啊,面试的话15分钟至少讲清楚演示清楚。
4.3sum。以前project和前公司(老板啊前teammates). 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴

基本确定去湾区了。

补充内容 (2015-2-25 00:58):
Rejected: Google Yelp  Yahoo MeridianLink LifeRay RockFuel Bloomberg Sears AristaNetwork OepnX Medallia Epic Broadcom Esri
Processing: Blizzard Amazon Twitter

 

2015(4-6月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Passfresh grad应届毕业生

时间线:
3月份内推Fb,不久就收到拒信,但是说信息已经在系统里了。5月初收到hello from facebook,中旬第一轮电面,加面在一周后。六月中旬onsite,几天后通知要reference,前两天收到offer。把前前后后搜到的所有面经和解法都拿出来,已经放在附件里供大家下载。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
一面:
给定任务AABCB, 冷却时间k(相同任务之间的最短距离时间),任务顺序不能变,问完成任务的总时间。
例子:AABCB, k=2, A**ABC*B, 时间为8.
解法:用hashtable保存上次的时间。
Followup1:如果k很小,怎么优化?
解法:之前的hashtable的大小是unique task的大小,如果k很小,可以只维护k那么大的hashtable。
Followup2: 如果可以改变任务的顺序,最短的任务时间是多少?
例子:AABBC, K=2, AB*ABC, 时间为6.
解法:根据每个任务出现的频率排序,优先处理频率高的。但是具体细节没有时间讨论。
感觉前两问回答的还好,就是细节和反应有点慢,最后一问没时间讨论。预感非常强,肯定会被加面,果然。
. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

加面:
华裔小哥放水了。
1. strstr, 不需要kmp算法,brute force

2. first bug version, 就是找左边界

onsite:. from: 1point3acres.com/bbs
据说new grad是没有design的,没准备也没碰到。三轮,两轮ninja,一轮jedi。jedi的题一般很简单,主要是扯淡。
因为签了NDA,具体的就不说了,但是感觉难度还行,主要是要准确、快、最优解和对复杂度的掌握。
1. 三姐,但是说了两句后,感觉是个靠谱的妹纸。虽然在问复杂度的时候还是奇葩了下,而且最后被拍照了。
只有一题,leetcode原题。

2. 华裔小哥,一进门就春风满面,有种不用担心,我会放水的哦的感觉。然而并没有….. Waral 鍗氬鏈夋洿澶氭枃绔�,
第一题时没好好交流,以为是原题,就把答案嗖嗖写上去了,还解释了好半天。其实是简单变形,但又写了两次才对。
后来想想其实有个小bug,但是小哥用java,所以没看出来,哈哈哈哈。
第二题,还没吸取教训,以为很简单,谁知道是要往图上去想。不难,但是以为最多到树,所以根本没好好思考。
不过以我和小伙伴的经历来说,到了图或者trie这块,只要能想到思路,不用具体实现就行。
.
3.白人小哥,扯淡扯淡扯淡扯淡。突然来了个特别特别特别简单的题。

关于fb的几句话:
1. 刷面经啊小伙伴们
2. 准确、快、最优解和对复杂度的掌握.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
3. 多准备几个扯淡的问题,不然好尴尬. Waral 鍗氬鏈夋洿澶氭枃绔�,
4. refer请直接消息我

关于找工作的几句话:
1. 虽然运气重要过实力,但是每个看似分分钟找到工作的人背后,也许是数月的挣扎
2. 别老想着题刷好了再申请。在fb看到一句话,done is better than perfect.
3. 道路阻且长,找个基友一起吧

 

2016(1-3月) 码农类 硕士 实习@Facebook – 内推 – Onsite 校园招聘会 |Passfresh grad应届毕业生

本帖最后由 candy_shmily 于 2016-3-2 17:04 编辑

失眠了4天以后终于解脱了 直接大病一场 积劳成疾啊 大家注意身体

以下长篇大论,非重点已注释,请安心使用. more info on 1point3acres.com
.
lz是去年10月初内推的 新年才跟我说二月oncampus给我安排了面试。。这拖延症就像a家一样 让lz一度以为简历被刷了。

某周五的oncampus: 全程走神的印度小哥。因为白板笔没水了 所以我写纸上了
1. 3sum lc原题//印度小哥说完题目之后 我直接刷刷刷告诉他解法。。小哥说你做过这题是吧。。我。。是的 于是被迅速move on
2. 找树上最长链//有recursive的写法 其实也有其他算法。 我跟小哥说了那个其他算法。。小哥不信一定是最优解。。。我表示要给他证明。。他说还是写recursive了吧
                       //我说recursive 如果是java的话得有全局变量 不然就得设个innerclass。。小哥说没问题没问题 然后问我c++呢 我说c++直接用指针可以改不用全局变量 刷刷刷写完后下一题
3. decodeways lc原题//就是那个数字串转字母的。。刚好做过。先给小哥说了个思路。。小哥说开始写吧。。然后我就刷刷刷写了。。但是。。我用了o(n)的空间。心想要挂 
                              //写完后给小哥看。小哥说这储存空间有其他做法吗。。我恍然大悟。。。说只要存两个就够了。。结果小哥看完一遍我的代码后。。又问了一次。。我简直给他走神跪下了
//最后小哥把我纸要去了。。然而那个纸背后是我python和perl的小抄(虽然没用到)。。。。一度以为自己要挂。。于是打算剃发读phd去。。

//结果紧接着那个周一告诉我要onsite。。我看了一眼os的due。。和各种midterm。。还有lab的proj。。感觉药丸。。。于是定在了第三个周五
//本来以为会有性别优势。。结果那天是girls’ day。。。。6个人。。清一色的妹纸。。把有个女性hr激动的。。我懂她。。

某周五的onsite:人很nice的华人大哥。看起来就像刚出校园啊!万万没想到
就一题类似lc的68(现在才看到竟然是hard。。)。给个text文档,然后限定屏幕宽度,将文档打印到屏幕上,要做到
a. 不能切断单词
b. 标点符号要处理好。华人大哥给了, 和. 的例子
c. 会有单词超出长度 自行处理
  //lz看了一下题目。 说有多种做法。。比如用split 把所有的都给切断成string[] 然后while一下
  //或者用两个pointer 用substring输出 . From 1point 3acres bbs
  //最后华人大哥要求我用第二种做法
  //这是lz第一次在白板上写代码。。刷刷刷写完都是bug。。。
  //华人大哥说你写一写testcase吧。。我刷刷刷列完了 然而并没有检查代码。。。
  //华人大哥说 testcase你都对了 但是你代码有bug。。。吃枣药丸。。于是我说啊对不起我没有检查。。。看了一遍好多bug。。。华人大哥说你还有bug。。于是lz又检查了一遍发现一个超级大的bug
  //那个超级大的bug华人大哥还要我用不同颜色的笔修改。。所以lz一度以为一定是挂了。。。 最后他还拍照存正。。
c.follow up: 之前写代码的时候 lz问了华人大哥关于多种标点符号要怎么处理 比如:”这个情况 :和” 是可以分开的 于是华人大哥就问我该怎么处理。

  //我说在判断条件那里加进去。因为写多很丑。。所以可以新建个check函数. 1point3acres.com/bbs
  //感觉华人大哥不是很满意 因为他说有多种语言 grammer规则复杂。。我说check函数挺好的啊 不同语言只要换个check函数内容就可以了 像api一样。。
d.follow up:如果颜文字怎么办。。。颜。文。字。
  //lz听到这就疯了。。。。回答了一个on效率的答案。。感觉药丸。。最后华人大哥就放过我了。。
  //回家后发现用regular expression挺好的。。。但是我当时没想到。。。
  //华人大哥还安慰我说这是他当年面试的题目。。我表现得比他好。。excuse me???? 大哥你是微软15年了跳槽。。我是实习生。。说好的同胞爱呢。。。

//一起面的那些妹子 都是考的lc上fb原题。。。都说是medium。各种刷刷刷写出来。lz只记得其中有个妹子考的297 因为我只刷了lc上的fb题。。lz68题没做过。一阵心虚
//我followup回答的不好而且写代码第一遍有bug还是被告知的 所以等结果的时候每天心神不宁 什么事情都干不下去 一直刷论坛。。
//感谢小伙伴们一直给我喂定心丸。。。不然lz早疯了。。

紧接着的周一hr告诉我第二天约电话。。可能有消息。。。大哥能不能告诉我是好消息还是坏消息。。
后来是offer。。还装逼地告诉了hr要决定一下是接offer还是申phd//小s冷漠脸

lz只申了fb家的sde intern和amazon家的research intern岗位(后者已跪 hr说要招更有(p)经(h)验(d)的candidate。。好。。吧). 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
对于找sde intern吧 弱弱地说下自己的看法:
1. lz觉得刷题重质量不重数量。lz刷题的方法是:
   a. 如果要面某公司了 那就刷那公司的题 不然的话 按分类刷
   b. lz每次做题是定时的 hard 25分钟 medium 15分钟 easy 10分钟。。。早点写完还可以上b站看看视频。。
   c. 即使做出来了 也要看下速度排名。。发现自己算法不行的话。。会上discussion看他们答案。如果有答案更优。。对此题做标记 隔天再做一次//这个方法被学长打脸了
   d. 完全没思路的。。必须着重标记。。必须再做好几次。。。。.
2. 最后几天lz被学长教育了。学长不是刷题流。。他都没怎么做题。学长说面试重要的是交流。。一定要白板写。边写边说。 不过lz本来就有紧张起来写代码会自言自语的习惯。。。于是
   a. 抽题目练习 找个讨论室就开始讲。。练习如何一边讲一边写。
   b. 被学长教育了 算法高不高效不重要 重要的是逻辑思路要清晰。。代码要美。。
   //lz 没怎么练 于是纯粹靠得运气过的。lz觉得如果有小伙伴各种刷题但是没有用的 可以试试练这个
3.对于fb lz在oncampus的时候刷了medium和easy题 偏easy; 在onsite的时候 刷了hard和第二遍medium 偏medium。. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
//4. 家里老一辈又去文曲星庙上了香了(大误)

2016(10-12月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Passfresh grad应届毕业生

11月17日面的onsite 不是u-day.
第一面: behavoir 跟一个manager聊 聊项目 实习经历 他会问一些问题 聊的感觉不错 聊了有半个多小时吧 剩下10多分钟 问了一道palindrome的题
第二面: 技术面试 三哥 题目是Intersection of Two Arrays 结果需要是unique的 就这一道题 问了很多很多的follow up 每个都问了时间复杂度:
        开始我说用set存 过数组就可以 -> 不让用set 我写了一个两个指针的做法 因为要排除重复 所以我每个指针都check了一下duplicate -> 又问有米有方法不这样check两次 -> 答:结果用一个hashset存 返回           的时候根据hashset 生成一个arraylist返回:return new ArrayList<Integer>(set) -> 说这个操作太费时间 -> 答每次找到一个答案就跟result里的最后一个数比较一下 一样就不存 -> 又问 如果一个很         大[1,2,3,….. 1 million] 另一个是[1,1 million] -> 答其中一个用binary search
        -> 怎么判断哪个好 -> 如果一个数组[1,2,3.. 10, 100, 200, 300…1000, 10001, 10002,…..] 另一个[1, 100, 101, 102, 103,…. 1000, 1100, 1200…]就是上一个数组间隔密集的         地方另一个数组间隔很或者反之(上疏下密, 上密下疏)怎么办 -> 需要分段 -> 设置一个upbold一类的东西 判断两根指针的移动位置 超过这个就用换binary search 这个实现了一下
        然后就是问问题
第三面: 技术面试 一个数组 A[i + 1] = A +/- 1; 找出有所有peek和valley的坐标 最方便 过一遍 o(n) 需要优化 -> 优化出来不能确保是o(logn) 应该是o(logN)~ O(n)之间 最差还是o(n);
        优化方法是binary search一个 每次找出一个数 就看一下它是不是peek活着valley 是的话 就加入result里面 然后检查mid – start == Math.abs(A[mid] – A[start]) 排除这一段全部上升或下降的可能. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
        mid跟end之间也是这样, 如果一直在上升或者下降 就不用再check这一段了 不然需要继续递归进去check 直到start + 1 < end
        整个程序写出来是一个递归 有一点像divide and conquer的感觉 最好聊了一会就把我送出去了

2016(10-12月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Passfresh grad应届毕业生

周二的university day . 1point 3acres 璁哄潧

9点一刻到的,大概等所有人signup完9点40 领进去一个房间等着面试官来叫人
. 1point 3acres 璁哄潧
第一面 白人小哥
上来先问简历,问之前在别家实习做了什么,一开始我解释得比较细,但他却要求high level概括。。最后帮我给出总结做的东西是time saver,就是帮助提高效率的工具

第一题找一个无向图中的所有联通分量,要求输出每个联通分量的点集。.
很快答出用bfs,然后也写出来了,基本上bug free
然后用复杂度,这个时候尴尬的事情来了,先答了一个O(E),E是边的数量,他又问如果图里没边咋样,那我说这种情况是O(N),N是点数,然后这个时候也许是前天飞久了没睡好脑抽说那复杂度是O(max(N, E))。。。 其实他想要的是O(n^2),n是点数,在这里两个人交流得很没默契,气氛很尴尬,然后答空间除input之外是O(n)

第二题输出一颗二叉树的从root到叶子的所有路径(字符串). visit 1point3acres.com for more.
这里不给任何pre define的结构,所有东西自己定义,然后我按照lc上的TreeNode,写了个recursive的遍历, 然后又问复杂度,又问call stack的复杂度是多少(stack里有多少个string)然后又脑抽答了个stack是O(height),其实他是想要答O(n),因为极端情况是一条链,又问我如果是balanced tree咋样,那我说logn。

最后反正感觉小哥没啥笑容了,感觉很不好
. 1point3acres.com/bbs
第二面 白人摇滚风大叔

上来先说这面要面behavior,但是我们先来个code题吧
说在pascal里面字符串是以[5, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’]的形式存储,现在要你用C++将这样两个东西连接起来。。。比如[3,’a’,b’,’c’]和[2,’x’, ‘y’]变成[5, ‘a’, b’, ‘c’, ‘x’, ‘y’]
我问那这个在c++里的输入应该是啥,他回答:you tell me。。。
然后我说char*? 他纠正是两个Byte*, 然后再返回一个byte*
因为我根本没有用过byte…所以连蒙带猜的写,运气好写得差不多,在他提醒下改了几个小bug. 鍥磋鎴戜滑@1point 3 acres
然后问这种形式会有什么问题,猜可能字符串会太大?他说然后呢?我又猜那占用太多空间?他说不是 又猜那第一位可能存不下整个字符串的长度? 他说是的
又问那怎么解决?且不能改变这个结构。。。扯了半天结果想要的是先判断能不能存下,否则throw exception。。。

之后开始问behavior
1. why fb
2. most chanllenge work
3. how to solve conflicts with workmates.. more info on 1point3acres.com

传言很简单的coding面的很纠结,behavior还行,一直在说

第三面,放水中国小哥

第一题,和第一面第一题很像,给一个无向图,再给其中的一些点,找出和这些点联通的所有点
我跟小哥说刚第一面做过类似的,小哥说没关系,所以很快bfs写完,复杂度有了第一面的经验也答得不错

第二题 有一些账号,账号里面有一个或多个email, 如果两个账号有共同的email,则认为这两个账号是同一个人,找出哪些账号是同一个人
我说账号之间如果有公共email就连边,然后就变成类似于第一题了,然后让我写了个连边的过程,我写了个O(n^2*e),n是账号数,e是单账号最多email数
然后问可不可以更优,我说可以用并查集直接合并email,简单讲了下思想然后简单写了几行,说good
然后中午吃饭下午参观

三天之后hr告诉说过了

2016(10-12月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Passfresh grad应届毕业生

  • 利扣91,做完dp解之后,又被问了不用dp怎么做(不限算法时间复杂度)
  • 给n个d维的vector和一个first selected的vector, 选出k个vector,每次选择下一个时要求:选离所有selected vector最远的vector, 计算距离的函数已给出D(v1,v2)并假设调用此函数时间复杂度为O(1), 某vector与所有selected vectors的距离定义为这个vector与其nearest selected neighbor的距离。在面试官的提示下最终找到了复杂度为O(nk)的最优解,对每个unselected的vector存下其与selected vectosr的距离,每次遍历unselected vectors找出距离最远的vector为下一个selected vector, 用这个vector与每个unselected vector的距离去更新距离(若小于原距离,表示nearest selected neighbor更换了)  
  • 给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行时间为5(B_ _ _ B, _ 表示wait). 写一个函数输入task序列和interval, 输出总的运行时间。 follow up是给一个序列和interval,task的执行顺序可以打乱,输出optimal(总执行时间最短)的执行顺序
  • 最近在做什么以及细问了简历。给一个手机键盘(只有0-9,不考虑*#那两个位置)样式的棋盘,骑士初始在数字1的位置,问走了s步以后(每步走日字),有多少种可能的走法。提示是可以hard code下一步的位置, 比如1->(6,8)。 应该可以用dp解,时间不多用了DFS/backtracking暴力解了

2016(1-3月) 码农类 硕士 全职@Facebook – 内推 – Onsite |Pass在职跳槽

这周一面的facebook
1. 半轮culture flt, project deep dive. 算法题是convert binary tree to linked list.
2. Coding: (1)跟number of islands 非常类似,只是变成matrix里是各种颜色,用字母表示,让统计每种颜色的number of connected component,用dfs就可以解决。另一个道题实在是想不起来了:(,想起来后会补充到下面。
3. System Design: Design URL Shortening service.
4. Coding. 先出了一个题是convert binary tree to doubly linked list.我说第一轮做过了非常类似的题。然后就直接写了他的Backup problem.leetcode 211 原题, add and search word.. more info on 1point3acres.com

所有的算法题面试官都会问你空间时间复杂度,worst case, best case, avg case都要知道。

补充内容 (2016-3-10 02:44):.
终于想起另一个算法题了,check if a binary tree is mirrored,就是与根节点镜像对称。

补充内容 (2016-3-10 02:45): .
最后一轮的follow up是如何利用trie做google 的type ahead feature。我的做法是每个trie node加一个weight,和维护一个top n words priority queue for his subtree。