发信人: subchap (subchap), 信区: JobHunting
标 题: FG面经和感想
发信站: BBS 未名空间站 (Mon Mar 10 00:32:02 2014, 美东)
看了本版很多面经，获益良多，所以我也把我近期面试的过程写下来，并且给出一些我
对系统设计题的想法，希望对正在找工作的人会有一点帮助。我的背景非cs非ee，不过
和编程相关，而且平时自己也经常写写程序。cc150和leetcode各刷了两遍。这次只申
请了F和G，最后F悲剧，G offer。
由于我有一些iOS的经验，所以申请F时申请的是iOS developer的职位。
F电面只有一轮：
先问了一些近期做的项目，然后编程是实现UIControl里的几个method，比如addTarget
什么的。不难。电面过后一周就安排了onsite。
F onsite 有4轮，全是白人：
1. 问了一些behavior的问题，比如简历里写的项目什么的，然后还问了最喜欢
facebook app的哪个功能，有什么可以改进的地方，怎么改进。还有为什么想去
Facebook。这些问题我基本都已经准备过，所以应该都答得不错。最后给了一个简单的
coding题，就是逆序打印链表里的值。我说了三个方法，一个是递归，一个是用stack
（和递归也差不多），还有就是先反转链表，按顺序打印，然后再反转一次恢复原状。
面试官好像很满意，让我选一个方法写code。我说前两个方法都很容易写，所以我就选
第三个方法。总体感觉这轮面得不错。
2. 这轮开始的时间完了5分钟，所以只面了40分钟，要求设计facebook iOS app的news
feed，不需要考虑服务器端的情况，只需要说app端的实现方法。这个我之前稍微准备
了一些，可是从来没有面过系统设计题，实在不知道应该怎么说，而且不知道会被问得
多深入，所以基本上一直是很被动的跟着面试官的指示走。画了几个框框以后就开始被
问各种细节，比如从服务器读数据的格式是什么，写一下json的example，界面和后台
怎么传输数据，等等。总体感觉这轮答得不好。回去后想了一下，感觉回答的方式有些
问题。比如说实现一个功能有两种方法A和B，他问我用哪种方法，我就直接说我倾向于
用A。这种答法很不好。应该先说清楚A和B各有什么优缺点，然后我选A是因为什么。这
样的话就会让人感觉我对于A和B都了解的比较多。
然后中午吃午饭，我跟recruiter说了第一轮不错，第二轮的设计不好。他说没关系，
只要下午的两轮都答好了就没问题。不过现在看来，设计题还是非常重要的，因为问设
计题的一般都是比较senior的人，所以估计他们的意见比较重要。（这只是我的想法。）
3. 又问了一些最近的项目的问题。这些都是warm－up questions，所以都只需简短的
回答。然后出了一个编程题：有两个一样的树A和B，每个节点都有父指针，要求写一个
函数，参数是A的一个子节点x，和B的根节点，要求返回B中对应x的那个节点。也就是
说A的根节点未知。这题挺简单，所以我没怎么想就说了先找到A的根节点，然后同时对
A和B做一个DFS或者BFS来找出B中对应x的节点。面试官说可以，让我写代码，写完以后
分析了一下复杂度。然后就问有没有更好的方法，我马上就意识到不需要用DFS或者BFS
，只需要在找A的根节点时记录下当前路径就行了（只需记录每个子结点是父节点的第
几个孩子），然后按同样的路径扫一下B树。复杂度只有O（height），面试官好像还很
满意。这轮面试没有一下就想到最优解，所以我还比较担心会不会结果negative。
4. 上来又是先问了一些项目的问题，然后拿出电脑来让我看一段程序，找出里面的不
合理或者有错误的地方。我说了10分钟，每说一个错误他都记下来，最后他说可以了，
已经写满一页了。然后出了一个编程题，要求用trie tree进行字符串匹配，字符串里
有可能有‘？’，代表任意一个字符，trie的结构是面试官给的，也不需要构造tree，
只需要使用就行了，所以还是比较简单的。写的时候有一个小错误，在测试时候发现了
就改正了。总体感觉还不错，应该比第3轮答得好一些。
面试完了以后recruiter来接我，说第3轮的面试官已经提交feedback了（效率真高），
是比较正面的。所以我觉得第1，3，4轮都应该能拿到正面的评价，因为第1和4轮都答
的比第3轮好，第2轮比较悬。之前我了解到有人的feedbacks是两个正面两个负面，最
后加面一轮了以后拿到offer，所以我还比较乐观，觉得最多准备一下加面一轮系统设
计。
面试完了以后就是圣诞假期，所以一直没有消息，到了一月份写信问recruiter，他说
今天和hiring team见了面，他们说不move forward了。。。我感觉可能是那个系统设
计拿到比较负面的评价。还是面试经验不足，不知道怎么回答这样的题。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
－－－－－－
G是general hire，电面也是一轮，以前发过面经，特别简单，编程题是leetcode的原
题。
面完第二天就被告知准备onsite，然后就是圣诞假期。。。一月份收到F的据信以后没
多久，G的onsite才定下了时间。
G的onsite有5轮，没有遇到leetcode原题，题目就不发了，毕竟签了NDA，我就说一下
过程吧：
1. 面试官是同胞。题目不难，是有关树的（和leetcode中等难度差不多）。这轮感觉
答的不太好，确认题意用了不少时间，然后写code的时候有一些小的错误被指出了以后
改正了，写的也比较慢。写完以后让我说一下可能会有哪些corner case可以用来测试
，这个我好像说的还不错，面试官还比较满意。
2. 第二轮面试官又是同胞，真是幸运啊。题目是有关概率的，出了3道题。最难的那题
不怎么会做，是在各种提示下慢慢做出来的。非常感激同胞的帮助。
3. 面试官是白人，出了一题不太难，可是很麻烦，就像leetcode里的valid number那
样有很多corner case。所以我一开始先把最重要的test case写一遍，没有马上写代码
。写test case时面试官也一起帮着想了一些。这个上面花的时间有点多，面试官说现
在还剩下20分钟了，我觉得你可以开始写代码了。于是开始狂写。写完后发现有个条件
没判断，又用箭头加了几个地方，然后面试官说你这个test case好像没考虑到，我一
看确实是忘了，写test case时写了，然后写代码时忘了，于是再改了一下代码。最后
面试官说代码还行。我问他是不是有什么fancy的解法，他说：没有，你的代码还行，
我看过更差的。。。然后他再稍微看了看白板，说其实你写的挺好的。。。
4. 第四轮有点非典型，面试官是白人，一上来就说他今天脑子不是很清楚，然后想了
半分钟题目。。。。然后出了一题我从没见过的，除了暴力法不知怎么做。面试官说：
我不在乎代码，你主要说思路，然后写pseudo code就行了。我说了下最简单的暴力法
，他说很好，你先把代码写出来。我说应该还有更好的方法，他说你先别急，把简单的
写出来再说。于是我把代码简单写了一下，也就十几行，复杂度是n^6。然后他开始想
下一步怎么办（这时我都插不上话。。。），然后说是不是可以用一个数组保存一些数
值，然后把其中的两层循环去掉，我说是的（这也是我本来想说的），于是改了一下代
码，成了n^4。下面怎么优化就比较难想了，我在想（当然，想的时候也在不停的交流
），他也在一直想，不知是不是在想怎么提示我。我实在想不出怎么优化，感觉dp什么
的都没法用。因为题目是一个两维的问题，我索性先把它简化成一维的，他夸我这个简
化做的好，这样就比较容易解释了。于是在他再次提示下我想到了用sliding window的
方法，确实可以解。他说很好，我们没时间来证明这个方法了，不过你现在把复杂度降
到了n^3，我说是的（没有再写代码），好像没法再优化了吧，他说这应该是最优了。
然后他说我们开始的时间晚了几分钟，所以现在没时间继续讨论了，他会把这个也写进
报告里。回来以后我又想了一下，还是不知道怎么把一维扩展到二维。。。这轮实在感
觉很乱。
5. 最后一轮是系统设计题，白人面试官。给了题目以后我就问了一些问题，其中有一
个就是这个系统会有多少用户，需不需要考虑large scale。他说这个问题很好，平时
一般都是应聘者回答到一定程度以后他主动问他们，让他们开始考虑large scale的。
我说我也会从单机开始说，因为比较好解释，他说这很好。于是我先画了几个框，把
components分一下，然后具体讨论一下。说了20分钟以后面试官说：不错，现在我觉得
是时间开始讨论large scale的问题了，于是我就开始画master － slave等一些图。这
次面试吸取了教训，每说到一个问题的解决办法，我都不直接说怎么解决，而是说有哪
几个方法，每个方法的优缺点是什么，选这种方法的话会遇到什么问题，我觉得哪种方
法比较合适，等等。然后有时会问他有没有什么preference，他也会说他更倾向哪种方
法。整个过程都比较顺利，我每说到一个点，他都会记录下来，所以我就更有信心了。
最后我还说了一下前一天看的consistent hashing，还画图解释了一下。
面完觉得算法题都面得很一般，只有设计题还不错，总体感觉比面F的时候差多了，所
以感觉基本悬了，希望比较渺茫。没想到过了一周recuiter说HC已经过了，有一个team
也很快对我有强烈的兴趣，再过了一周就送到VP那里了，然后过了几天就收到电话给了
offer。这次真是运气好啊，估计同胞给我的评价比较好，然后系统设计那轮也还不错
，另外两轮的评价也不是太负面，所以就给过了。当然都是我的猜测，不过真得谢谢同
胞们！
下面主要说一下我怎么准备系统设计题的吧。我对large scale system没有任何实战经
验，G的onsite之前专门花了两天时间准备系统设计题。最主要的是把cc150的
scalability的那一章非常仔细的看一遍，不只是记住最好的方法，而是把每个方法都
记住，特别是那章最后那个关于cache的题，虽然碰到的题不是关于cache的，但是还是
可以换汤不换药的把方法套用上去。然后看了一下gfs，mapreduce，和big table的三
篇论文。由于时间不够，我只是仔细读了gfs，然后泛泛的看了一下mapreduce和big
table。虽然这些文章里的内容在面试时没有直接用到，但是有些思路还是相通的。然
后我把consistent hashing看了一下，感觉这是万金油，很多地方都能说。另外还看了
一下“秒杀99%系统设计题”的博文，最后在highscalability.com里随便找了两三篇文
章看了一下。其他的东西全都没时间看了，但是如果有时间的话肯定是看看比较好。
由于我只面了F和G，面试经验还是比较少的，所以说的东西不一定对，只希望对大家有
帮助。
--
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 74.]
Saturday, June 7, 2014
FG面经和感想
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment