终极面筋

昨天收到FB的电话，我的OFFER已经批下来了，这也意味着我的JOB HUNTING结束了，下
面是我这两个月来申请结果汇总：
Applications (7): Facebook, Google, Microsoft, Square, Twitter, Rocket Fuel,
Amazon
Offers (5): Facebook (accepted), Microsoft, Amazon, Rocket Fuel, Qualcomm (
return offer)
Rejections (3): Square, Twitter, Google

OFFER细节就不报了，上次看有人报MS的OFFER细节，结果引发口争，有人将其定性为
SHOW OFF。。。

在版上受益良多，我会陆续呈上各家公司的面试经历和面试题（FB的面试题除外），当
务之急是给LEETCODE捐点钱。

非大牛，版上互赞大牛的风气不可取。有二爷，半海和一帮真牛在这镇着，谁敢放肆！

============
个人背景
============
既然已经被不少朋友认出来了，就提供下背景信息吧。
我是2009入学的PHD＠ECE，今年11月刚毕业，研究方向是Wireless Sensor Networks和
Distributed Systems Design。在过去的四个暑假里，完成三个实习，每个大概14星期
。第二个暑假我没有实习，跑去加拿大和意大利游玩了。

更多信息，比如个人主页，可以站内信。

============
如何准备
============
1. 书籍：
B1. Introduction to Algorithms
B2. Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne
B3. Cracking the Coding Interview
B4. Programming Pearls
毫无疑问，B1是最重要的，其中的基本和中级算法章节我至少读了4遍，高级算法部分
间断地读了2遍。版上很多人非常推崇B3和LEETCODE （我后面会讲），却忽略了这本葵
花宝典。读这本书时，重点不是解上面的题或是背算法，最重要的是理解掌握各个算法
背后的设计思想。面试中遇到原题是你运气，大部分时候是没这种运气的。但是绝大部
分面试题的解题思想非常类似，无非是从各种排序算法，BST算法和基本图论算法中变
化的而来。微软的面试题4.1我从来没见过，好像这个版上也没讨论过，我也是现场灵
光一闪，发现其本质就是QUICKSORT算法，然后给出了最优答案。

B2与B1类似，都是大部头的书，确实需要点勇气的耐心去读。这本书中讨论了很多更为
实用的算法，更适合去解面试题。如果你有时间的话，一定要读一下，网上可以找到
PDF版本。B3可以看下，主要是看解题思路，上面的代码质量很一般。我是在刷完
LEETCODE几遍后，随手翻的。因为我已经把LEETCODE上的题刷得很熟了，所以这本书我
看得很快。B4感觉是个鸡肋，以前版上很多少推荐过，所以我也就看了看，发现这本书
实在是非常非常基础。如果你已经把B1看过两遍了，这本书就没必要了。

题外话，我从来不相信只靠刷题就能拿到FLGT的OFFER。这些顶级公司对个人能力的考
查还是很全面的，有时即便你全部答对了题，也不一定能拿到OFFER。况且现在不少面
试官已经知道LEETCODE这类的刷题网站（他们当中有些人以前就是这么刷进去的），他
们也会尽量避免出原题。当然，如果哪位国人哥哥想放水，出个原题让你水过，也是有
可能的。

话说我面试最怕国人，其次是日本人和韩国人。阿三就不用提了，我已经将他们划为抱
团阴狠的鼠类。

2. 在线资源
MITBBS
LEETCODE
TOPCODER
CAREERCUP
找工作的前一个月，我就开始MITBBS考古，看了不少题。后来在面试期间，基本上每天
早晨都会上来把前一天的所有关于面试的帖子看一遍。从开始感叹各位神人的答案，到
后来我也开始提供答案了。在我看来，LEETCODE是最好的在线训练网站。刷LEETCODE的
目的不是解上面的题，而是通过训练来熟练掌握B1中的算法设计思想，因为LEETCODE上
不少题的解题思想非常类似，还都是那些基本算法的变种。LEETCODE每道题我认真
地写了两遍，都是自己努力想答案，如果实在不行，才去看别人的解法。因为大部分题
是自己做出来的，所以印象非常深刻。到后来，我两三天就能快速地过一遍；随机挑个
题，我很快就能写出来。

TOPCODER上有非常好的TUTORIAL，讲得深入简出，非常值得认真读一下。我以前就一直
没太明白KMP算法，看过上面的TUTORIAL后，一切都明朗了，LEETCODE上的STRSTR那题
我也是用KMP算法解的。在面试RF时，一个阿三一上来就考这个STRSTR题，而且还很卑
鄙地把那个最基本的逐个比较的算法说出来了，意思是说你不能用这个基本算法解了，
然后那个SB一脸欠揍的得意表情。我当时就是现场用25分钟左右时间写了KMP算法，那
个SB又变成一脸失望的表情。面完那轮后，我后面心态就非常随意了，因为已经决定不
去这家充斥着阿三的公司了。

当我已经把LEETCODE做得非常熟了后，我就开始随机做TOPCODER上DIV1和DIV2的题了。
DIV3的题就不用看了，太难，不适合面试。在面每家公司前两天，我会去CAREERCUP把
这家公司前4页的题都看一下。只是看看，过过脑子既可，没有去写代码。

3. Design
总结贴：
http://blog.csdn.net/sigh1988/article/details/9790337

其它资源：
http://www.mitbbs.com/article_t/JobHunting/32498535.html
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/photo.php?v=572283147938&set=vb.9445547199&type=3&
permPage=1
http://vimeo.com/11280885

必看论文：
Google: Google File System, MapReduce, BigTable
Facebook: Cassandra
Amazon: Dynamo

其实读懂这5篇论文后，很多系统设计题就应该大概明白怎么做了，因为很多重要的设
计思想都在这些论文中。

============
Facebook
============
下面更新FB的面试经历吧，因为已经从了，所以不想说具体题目，只说我这个非典型经
历吧。
第一次和FB打交道是在今年２月份，当时我突然想在毕业前再去实习一次，于是网投了
FB的实习，没有找人REFER。一个月后收到HR的通知，安排面试。他家效率非常之高，
一周之内就搞定了两轮电面，进入PROJECT MATCH。可惜时间太晚了，没有MATCH上。

我今年９月向我老板确认我可以４年半毕业，于是开始申请工作。我直接发信给我上次
的那个HR，说我想申请正式职位，看她能不能安排下电面。她非常爽快地说，我们不用
浪费大家的时间了，电面就不用了，你直接来ONSITE吧。于是安排两周后电面。ONSITE
一共四轮，第一轮是PHD JEDI，主要是让我在白板上讲解的我DISSERTATION，最后问了
个无限数据处理的问题。第二轮和第三轮是CODING NINJA，每轮两个题目，可以有点小
BUG，但要能自己发现。最后一轮是DESIGN，主要是讨论设计思想，根据面试官提出的
种种问题进行改进。

一周后收到OFFER，可惜在那周的星期三我已经ACCEPT了微软的OFFER。话说微软很不自
信，三天两头催我做决定，最后说在周三之前必须做决定，大概是因为他们知道我还在
面FB吧。比较了两个OFFER，发现在考虑税收和LIVING COST下，FB的只多个两三W，我
不想为了这么点钱伤人品，于是发信给FB，说已经接了MS的OFFER，非常不好意思。不
过我明年会跳槽过来的。

然后FB的HR没理我，我想她们很少见过有为了MS的OFFER，拒掉FB的OFFER的傻B吧，还
是在FB给的钱多的情况下。三天后，突然接到HR的邮件，说面试我的几个人都强烈推荐
我，他们想再给我加一轮DESIGN面试，来决定是否要给我加工资。我一想还有这种好事
，于是就同意了，当天下午就SKYPE面试了。几天后收到新的OFFER，说如果我愿意拒掉
MS的，他们会把我的PACKAGE提高１２％。话说他们这么没有节操的硬抢，我也就没有
节操的同意了。。。

这个故事可以打消很多的关于反悔OFFER的顾虑。上次还有人担心拒人别家，从了FB的
话，FB知道后会收回OFFER。其实FB还是很喜欢抢人的，只要你有货。

============
Twitter
============
话说我和T家非常没有缘分。今年2月申请实习时，让我朋友REFER，结果他家HR连电面
都没有给，就把我给拒了。今年我换了另一个朋友REFER我，电面是拿到了，第一面就
挂了。电面先是一个LEETCODE原题，Palindrome Partitioning II ，我给了O(n^2)的
解法。然后是问LINUX里面BASH SHELL是如何实现的，运行一个命令时，系统有哪些步
骤，系统STACK是如何转换的。我对LINUX底层的东西不熟悉，第二部分答得不好，磕磕
碰碰的，然后就没有然后了。

============
Square
============
这家我是网投的，两天后拿到面试。电面有两轮，间隔两天：
1. 经典的小偷问题：一排房子，每个房子里有一定价值的东西，小偷不能偷相邻的两
个房间。即如果小偷光临了房间i, 那么就不能再偷房间i - 1和房间i + 1。要求返回
小偷能偷到东西的总价值的最大值。这是个经典DP问题，版上讨论过。
Sol: Suppose v[i] = the value of house i, and totally we have n houses.
f[0] = v[0], f[1] = v[1], f[i] = max{f[i - 1], f[i - 2] + v[i]} for i >= 2

A modified version of this problem is that all houses form a circle, whose 
solution is very similar. We need to run DP twice.
1st: f[0] = v[0], f[1] = 0, f[i] = max{f[i - 1], f[i - 2] + v[i]} for i = 2,
3, ..., n - 2 ==> ans1 = f[n - 2]
2nd: f[0] = 0, f[1] = v[1], f[i] = max{f[i - 1], f[i - 2] + v[i]} for i = 2,
3, ..., n - 1 ==> ans2 = f[n - 1]
return max{ans1, ans2}

Sample code: https://gist.github.com/krisys/4089748
More explanation (Bad Neighbors): http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=tccc04_online_rd_4

2. 扑克牌问题：给一副扑克牌排序，先是按花色，同一花色按数字排序。主要是扑克
牌这个CLASS应该如何设计，如何表示花色和面值。我给出了他想要的JAVA enum表示法
，但我以前在JAVA中很少用enum，导致里面有些方法都忘记了。
FOLLOW-UP：现在你有一手牌，你要计算其分值，规则如下：如果两张牌相同，或这两
张牌的面值和为15，则计2分。ACE可以是1或者11.

这家公司对代码简洁度有着变态的要求，凡是能一行写出来的东西，绝不会让你写两行
代码，哪怕两行代码的版本更容易理解和维护。写完代码后，其余的时间全是在按他们
的要求简化压缩代码。最后代码的行数是减少了不少，可是可读性也是一样。第二面挂
掉，我觉得主要是用enum的时候，明显不熟。

============
Google
============
与FB类似，我在今年3月申请实习的时候，也过了前面两轮电面，进入HOST MATCH，最
后也没MATCH上，于是他们直接让我去ONSITE。我当时还没准备好正式找工作，就把
ONSITE推到了10月，也就是在FB面试的后面几天。面试一共四轮，全是CODING，只有一
个人稍微问了下我的研究内容，这点就明显没有FB给我的感觉好。

第一轮是个香港帅哥，人很好，这轮是我表现最好的一轮。题目如下：
1.1. Tokenize a string to words. Ignore any space and punctuator

1.2. Design an distributed file system to store files of TB size
Follow-up: How to find and store the top-k most frequent keywords among 
documents stored on all Google servers

第二轮是个阿三，感觉很吊的样子，一副大爷样地坐在那里，让我很不爽。他就问了很
简单的一道题，然后就是不停地问我如何改进。
2. Given a list of words, find two strings S & T such that:
    a. S & T have no common character
    b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm

第三轮如下：

3.1 Design an interface that can convert both a sorted linked list and a 
sorted array into a balanced binary search tree. Implement it in both bottom
-up and top-down approaches

3.2. (Leetcode 原题) Given a matrix of size m * n, matrix[i][j] stores the 
number of carrots in cell (i, j). Now a rabbit starts from the left upper 
corner and wants to reach the right below corner. It can only move either to
the right or below. Compute the maximum number of carrots that it can 
collect along the way, and output that path.
Follow up: how many different ways are there?

第四轮就是个悲剧，一个更年期日本女人，英文听得让我想死。进来后没有任何问候，
连自我介绍都没有，坐下来就板着个脸开始问。整个过程中就是我在说，她没有任何回
应或是表情，我还不如去她们日本买个漂亮的充气娃娃来对着面试呢。这轮我从一开始
就很紧张，发挥得也不好，到最后快结束时才写出代码。这题其实想明白了，算法极简
单。只是我当时不知道怎地，居然卡在这上面了。
4. Given a byte array, which is an encoding of characters. Here is the rule:
    a. If the first bit of a byte is 0, that byte stands for a one-byte 
character
    b. If the first bit of a byte is 1, that byte and its following byte 
together stand for a two-byte character 
Now implement a function to decide if the last character is a one-byte 
character or a two-byte character
Constraint: You must scan the byte array from the end to the start. 
Otherwise it will be very trivial.

============
Microsoft
============
一共五轮，过程没什么好讲的，标准流程，直接上题吧：

1.1. What are the two ways to implement hash tables? How to add, delete, and
lookup an key? How to deal with collision?

1.2. Given an integer, return the next prime number bigger than it. 
Follow-up: If this function will be called frequently, how to optimize the 
performance?

2.1. What's a full outer join in database? Implement a full outer join given
two tables.
Follow-up: If two tables are very big (i.e., no enough RAM to load them), 
how to deal with it?

2.2. Given random() that can return 0 or 1 uniformly, implement random_new()
that can return 0 with 90%, and 1 with 10%.

3.1. Given an image represented by byte[][] image, return its mirror image.

3.2. Design a distributed LRU

4.1. Given an array [a1, a2, ..., an, b1, b2, ..., bn], transform it to [a1,
b1, a2, b2, ..., an, bn].
Requirement: time complexity O(nlogn), space complexity O(logn)
Sol: the base idea is to use quicksort techniques. Suppose the current array
is A, whose size is 2k.
1. Divide A into four segments: A = [A1 A2 B1 B2], where A1.size = B1.size =
k / 2, B1.size = B2.size = k - k / 2;
2. Swap A2 and B1, and we get A = [A1 B1 A2 B2]. In this step, we actually 
need to rotate [A2 B1] to the right by k - k / 2 items. This can be done by 
reversing [A2 B1] first, and then reversing [A2] and [B1] respectively.
3. Recursive on [A1 B1] and [A2 B2] respectively.

Example: A = [1 2 3 4 5 6 7 8 9 10]
A1 = [1 2], A2 = [3 4 5], B1 = [6 7], B2 = [8 9 10]
After 2nd step, A = [1 2 | 6 7 | 3 4 5| 8 9 10]
For the 3rd step, process [1 2 6 7] and [3 4 5 8 9 10] repectively

4.2. Design: suppose you have a cluster, and each machine in this cluster 
has a large number of numbers. How can you find out the median of all the 
numbers on all the machines.

5. Design: How to design a crawler?


============
Amazon
============
题目比较简单，感觉他家标准降低好多好多。。。

1. Given a string, find the longest palindromic substring

2. Given a binary tree, find the length of the longest path in the tree. A 
path can start and end anywhere in the tree (i.e., not necessary from the 
root to a leaf).

3. Given a large number of integers, return the largest K numbers. How to 
process them using MapReduce?

4. Implement a priority queue: enQueue, getFront, deQueue

5. Given a set of points on a plane, and a list of circles centered at the 
original point, find the ring containing the most number of points.

6. Design: You have a HTML page, which contains many strings describing 
potions in a CSS file, how can to compress these strings to reduce the size 
of the HTML page.
Follow-up: Users complain that your website becomes slow recently, how can 
you find out the problems, and how to fix them?

7. Java OO concepts, dissertation and behavior questions from CC150.