[朝花夕拾系列] Facebook,Google,Microsoft面试记录---我的奋斗 1/2

[朝花夕拾系列] Facebook,Google,Microsoft面试记录---我的奋斗 1/2

(Note: 最近将之前的博文转到知乎专栏来. 这篇文章是我2010年中写的,所以可能文笔比较幼稚:)

的确好久没有写日志了。朋友你们还好吗? 这里我就应广大fans的要求,总结一下最近发生的有意义的事情,明确一下成功的原因和失败的教训,希望对自己和别人有帮助。

我找facebook是从去年6月开始的,那时因为TopCoder Open 2009 Final的缘故,去拉斯维加斯见到一群facebook的recruiter,其中有个也是我们CMU的校友,于是与她建立好了network。去年秋季的时候,facebook来校园招聘,曾要求我和他们的员工一起吃饭,只可惜当时还在日本,没能如愿。这学期来到匹兹堡,开始全力找工作。好在我在这几个大公司还是有点人的,顺利拿到了面试。Google和Microsoft的面试都很顺利,Google的recruiter今天问我是要继续面试full time还是参加秋季的实习,我还在考虑。Microsoft给我安排去西雅图onsite interview,不过最后得知只是夏季intern的职位,而且它的recruiter还说我毕业是明年一月,只能下半年面试全职,他们不能这么早的给面试。我说那就算了吧,我也不来西雅图了。recruiter说好,说8月份开始招聘的时候找我,我说太好了,谢谢。Facebook的人很好,给我安排了full time的面试,最后我一不小心,拿到offer,赶在facebook上市之前搭上了末班车,园了我追了一年的梦。

大体上就是这样,下面我说说具体面试的过程。

CMU果然剽悍,学期一开始很多大公司就相继来学校找人。我投了简历给Facebook, Google和微软,都拿到了面试的邀请,参加他们的在校面试。面试的过程无非是先问问你做什么,对什么感兴趣,对他们公司有什么了解,对他们产品有什么建议之类的问题。然后就给你出coding的题目,一般是很基础的算法和数据结构的问题,叫你在纸上写程序。3个公司的面试都在2月份,于是我12月底和一月份都在准备这些coding的小问题。毕竟当年哥也面试过中国的微软和google,知道问的是些什么东西,面试官需要的是如何的答案。我总是认为,面试要成功,要表现出一种气场,可以打动面试官,与他有共鸣。可以是Flash(星际)的那种重剑无锋,大巧不工的感觉,也可以是IU在唱GEE的时候那种华丽的感觉。总是你要有自己的闪光点,有个性,或者说有一个geek所应该具有的气质。

第一个面试的公司是微软,就只有一轮的在校面试,面试我的是一个30多岁的华人。我觉得他应该不是个coder,因为我说的很多东西他都不懂,比如说在一个n*m的矩阵里,一个人从左上到右下,只能向下一步或者向右一步,总的可能的走法我说是C(n+m,n), 他竟然都不明白。。。 而且他不是故意装不懂,而是数学有欠缺。另外,我说KMP,他也没听过。Anyway,写代码的题目我正常发挥,于是就过了。但是过不过也无所谓,去的可能性不大。我始终觉得硅谷的天气和氛围有着独特的吸引力,毕竟那里是全球的IT中心,是每个对计算机感兴趣的人都梦寐以求的地方。

第二个公司是Google,他们的面试感觉安排的比较细致,他们占了CMU一半的面试房间,而且给每个人安排了2轮的面试。我去面的时候,“发现一群莘莘学子都和我一样穿着西装革履,还有几个刚从面试房间里面出来的人一股凯旋归来的感觉~”,奇怪为什么穿正装的这么多。签到的时候发现,一半的房间是Google的,另外的一半而是Goldman Saches...好强阿,什么时候我也去面一次。我的第一轮面试也是一个华人,或者ABC,英语很好,出的问题也相当NB,一个矩阵里,里面元素是0或者1,要你找一个面积最大的全1的子矩阵。这题我原来有印象,但是我忘记解法了。一般的新手在这时可能会不知所措,但是我毕竟是职场面试的老油条了。我先分析一下问题的关键,又说如果不要求是矩形只要求是一块任意形状的区域的话,可以使用FloodFill,O(N*M). 然后这里是矩阵,然后我们转换。扯了几句后,说了一个大体思路,来套他想要的答案。他说用brute force就可以,于是我说枚举左上和右下两个点,然后判断是否全1,这样是 O(N*N*M*M)的算法,因为判断是否全1可以用sum数组来减一下,O(1)就够了。他说很好,就这样。于是继续出其他的题目,接下来的题目关于比较简单,还有一些应用类型的,比如怎么让一个网站的浏览速度变快之类的,我自我感觉还答得不错。第二个面试我的人来自Gmail team,我说我很佩服你,因为我在google实习那年,年终奖授予的产品就是gmail,因为是gmail建立了一个用户的平台,让用户有了一个帐户和密码,后来Google的许多web产品都是用gmail邮箱来标识用户,比如google doc, picasa, google code,甚至谷歌拼音的词库也这样。我想他肯定那几年做得很爽,股票也分红不少。最重要的是做了个改变世界的产品,想当年的email,30MB的空间,经常要删邮件等。 他问的问题比较正统,类似于string permutation的问题。我写了一个DFS就解决了,难度在acm题目里属于最基础的那种。就这样,2轮面试我表现的还不错,过了几天HR给我寄来一些表格要填写,然后就开始说给我找intern的project,于是就杳无音信了,直到今天下午。。。

面完Google的第二天,我还是对矩阵的那个题目念念不忘,我记得碰到过。后来去Pku online judge一找,果然有,一模一样的题目(acm.pku.edu.cn/JudgeOnl),有O(N*M)的算法,思路是转换成直方图然后维护一个栈。我那天下午刚好没课,于是实现了一下代码,A掉了那题。接着又顺便把直方图找最大矩形的题目也做了。心想POJ上面还是有许多很有用的题目呀!

最后的面试来自Facebook,也是我最重视的一个。能在最重视的事情上面取得成功,是最快乐的事情。当这种事情降临到我身上的时候,我应该感激。这次facebook照例,也邀请了CMU的20多个人和他们的员工一起吃饭。我有幸名列其中。参加的dinner的人没一个是中国人,让我能私下聊中文的机会都没有。和我一个桌子的8个人,3个是员工,其余和我一样都是学生,只不过大部分来自CS的本科,都是那种看起来很睿智的白人。他们说话很快,有点像看big bang theory的感觉,我和我旁边的那个员工聊了很多,Facebook的安全阿,进中国市场的打算和他们的网站的总体架构之类。

那个周中是面试。第一轮面试的题目是斐波那契数列求第n项(n>0),我开了一个长度为3的滚动数组来递推,其中犯了个小错误,卡了一下,不过总体还好。这个题目我特别提醒一下,千万别写成那种递归的程序,比如:

int Fibonacci(int n) { // we can assume n > 0
     return (n<3) ? 1 : Fibonacci(n-1)+Fibonacci(n-2);
}

程序短小精悍,结果也对,但是写成这样,面试就几乎挂了一半。原因自己想!

接着他又问了我什么是二叉搜索树,我正确回答,然后他要我写验证程序。我之前看过linglin的面试总结,所以我之前想过这个题目。我记得我半年前在纸上写过,但是代码比较乱,后来今年一月的时候重新思考这个题目的时候,想到一个比较满意的代码。当然,原理还是比较直接,就是中序遍历此树,看他是否是递增。

int prev = INT_MIN; // 用户每次调用前需要手动设置这个prev为一个最小的int
bool check(NODE* root) {
     if (!root) return true;
     if (!check(root->left)) return false;
     if (prev > root->value) return false;
     prev = root->value;
     if (!check(root->right)) return false;
     return true;
}

其中对于输入是null的树我们返回true。这是得到面试官的批准的,因为一个null的树并没有违反二叉搜索树的要求。我想我上面的程序已经足够体现我的功力了,而且思路非常清晰。(事实证明面试官也一点毛病也挑不出来,而且看我程序写得一气呵成,就点点头称赞一下。幸好他没说全局变量不太安全,或者不推荐用这样的SB问题。我一直不屑于谈这些,就好像goto一样,前几天我写一个题目的时候,刚好再用,我觉得goto用起来可以让程序很清晰和简洁。但是现在已经没有几个人程序员能驾驭goto了,很多人连它的语法都不知道。我很多时候也用不好它,只能将其写成函数。)回到面试,面试官觉得我合格了,就问我对他有什么问题,我随便提了一个问题,接着我们聊了几分钟,于是第一轮面试就如此通过了。判断树的题目还是得感谢linglin的blog,很多时候我之所以成功,是因为我站在了巨人的肩膀上(Isaac Newton)。同时,自己准备了这么久的代码终于可以在面试时用上,真是件兴奋的事情。机会只属于准备好的人,当我在面试的时候碰到这个问题时,我觉得自己之前所付出的努力全部都是值得的!

其实,上面的代码还可以精简,比如这样:

bool check2(NODE* root) {
return !root ? true : (check2(root->left) && prev<root->value && (prev=root->value, check2(root->right)) ? true : false);
}

但这样不够清晰,只适合装B.所以我觉得还是不要写到面试上面去。


晚上我接到邮件,说我通过第一轮面试,明天第二面。第二面的题目也类似是string permutation,所以一下子我就写好了。接着她又出了用anagram来分组字符串的题目,之前写过,问题不大。总之这轮感觉就是show time,面试题目之前都实现过。面试的时候我大量使用了STL里面的set和map,这让我的代码比较短小,同时查询的时间还是保持在O(logN). 当然,如果面试官要我手写一个二叉搜索树或者hash表,我也是没有问题的,毕竟哥是练过的。在面试之前的一个月,我专门去练习了手写链表,反转链表,字符串,插入删除或者查询二叉搜索树等等。甚至连快排和归并排序我也自己重新手写一遍熟练熟练,毕竟经过多年的调用STL sort,那些排序我都忘得差不多了。

接下来,我发信给facebook说我不能做summer intern,能不能让我面试full time。CMU校友的那个recruiter对我很好,给我在期中考试后安排了onsite的interview。于是,在3月7日,我踏上了去Facebook总部的飞机...... (To be continued)

「真诚赞赏,手留余香」
还没有人赞赏,快来当第一个赞赏的人吧!
文章被以下专栏收录
27 条评论
推荐阅读