这个月正好是我来到美国的第四年。恰好我们的小书《程序员面试白皮书》即将出版，加上受编辑邀请，我正好趁此机会随便谈谈我在美国硅谷求职工作的经历，也为自己的职业初期做一个小小的总结。
这个月正好是我来到美国的第四年。恰好我们的小书《程序员面试白皮书》即将出版，加上受编辑邀请，我正好趁此机会随便谈谈我在美国硅谷求职工作的经历，也为自己的职业初期做一个小小的总结。
我的求学之路确实顺风顺水，高中竞赛保送北大，毕业后来到地处南加风景如画的加州大学分校，并且在硕士阶段顺利拿到全额奖学金，以及直接读博的机会。但是经过一段时间的科研，我觉得似乎直接工作更适合我的兴趣，于是在研究生的最后阶段准备好好面试，找一个心仪的工作。
我用了两个月的时间前后on site了十家公司：Cisco, Arsita, Akamai, Oracle, Zynga, Facebook, Juniper, Google, Apple, Amazon。最后运气比较好，拿到了八家公司的全职offer。那段时间我一边准备发Paper，一边准备面试，是我最为努力的时间段之一：两个月内完成了100多项自己给自己制定的目标。
回到找工作的话题，先对这些公司进行下分类：
1. Networking Company：Cisco, Arista, Juniper
2. 工作与我的科研相关：Akamai， Apple
3. 分布式系统：Oracle
4. 互联网，general SDE: Google, Zynga, Facebook, Amazon
其实现在想想找工作的时候不应该投这么多方向，1到2个方向可以使得精力更加集中。我之前主要是一直想转phd，并没有特别想好想要做什么方向，所以把能做的几个方向包括移动开发，网络，系统等都尝试了一下。如果很早地明确自己想干什么，可能准备得更有针对性，也会更轻松。准备面试的时候以重要性排序如下：算法-》数据结构-》简历项目-》网络-》操统/底层-》数据库。如果职位特别要求某方面的知识，那还需要针对性地看一看。对上述公司，面试题难度分类如下：
Apple ~ Google > Facebook ~ Amazon > Oracle ~ Arista ~ Zynga ~ Akamai > Cisco > Juniper
挑几个比较有意思的公司简单介绍下。由于签了保密协议，对于题目不方便透露。并且我觉得大家也不需要过于执迷于能够碰巧碰到相同的题目，毕竟这个概率和中大奖差不多，并且进了公司还得靠自己的真本领。
Amazon：
总部地处西雅图的亚马逊在当地最大的竞争对手就是微软。我个人面试感觉亚马逊更显的年轻活力一些。面试主要强调基础算法数据结构知识，夹杂系统设计。亚马逊效率还是挺高的，一天就出offer了。再分享一件事：面试的时候我问了对于本科，硕士，phd的工作有什么区别。面试官回答：本科开始会做些更基础的事情，包括写文档，标记注释，整理版本等，之后基本大家都干的事情差不多。入职的时候定级不同，比如亚马逊Software Engineer 有SE1, SE2,... SE5, principle, senior principle，那么本科就是SE1，硕士基本SE2，博士基本SE3，升一级基本要3年时间，所以无所谓那条是“捷径”，基本看个人喜好和能力。其实这反映了北美公司的一贯作风：除了特别偏向科研的组，并不是特别在乎面试者的出身背景，只要能力够强，进了公司都会有足够好的发展空间。国内我并不是特别了解，不过根据我同学的反馈，对学历的门槛卡的比较紧。仔细想想也不无道理，毕竟人口基数大，画一条硬指标能够更快的筛选人才。
的确是最难的。面试的时候会有张单子，记录之前面过的问题。而且问题会按照涵盖的范围分类，范围包括算法数据结构，系统，系统设计，网络，底层等。面试官会挑不同的方面提问。如果挂了一个基本就没有太大希望了。所以面试Google的时候说，如果不是觉得自己面得很好，基本就是跪了，这句话还是有道理的。面试结果会提交到commitee，一共有两轮，第一轮根据面试官反馈做出决定，第二轮会再次审核申请者背景和面试结果，如果结果在可上可下的范围里，而背景又不是很匹配，也有可能会被刷掉，概率据说1/5左右。Tip：面试之前充分准备，面试的时候随缘。
Apple
还是一家挺神秘的公司。如果没人内推说实话进的可能性不大。但是一旦有人内推，应该能给面试。电面主要是看你的背景和该组是否匹配，不匹配可能会推荐你去其他组。我自己的经验来看，onsite面试难度比较大，当然组与组之间都不尽相同。Tip：果断抱认识的人的大腿，找人内推。
面试官分为两类，一类叫“忍者”，主要面算法，数据结构，期望45分钟内做两道。一类叫“绝地武士”，主要是面试之前做过的项目，问问behavior question，时间多的话也会加一道题目。Facebook面试和Amazon一样，给人的感觉就是熟悉：风格和career cup 或者leetcode上面的题目比较像。我运气特别好，基本都见过类似的，所以面完就基本知道挺有希望了。Tip：最应该好好准备的公司，就多做题，提高准确度和效率。
Oracle
名校控加GPA高是事实，传说中的“学霸集中营”。但onsite也不是说都是聊聊天就进的，manager面试，问了我一道设计题，花了40多分钟写了100行以上代码。我面试的组叫Exadata，作为high-end级别的数据库整体解决方案，那个组还是很有前途的。职位主要是关于分布式系统，query load balance design。如果有GPA3.8+加好学校的，可以尝试一下。
Zynga
面试题难度不大，主要是要在面试中表达对于游戏的兴趣，最好之前玩一下zynga的热门游戏。对于我最后reject的结果，HR打电话过来说Hiring commitee认为你对我们公司兴趣不大。。。Tip：虽然我不想去zynga，但是学到了一个经验：公司的确会因为非技术性的原因拒绝你。那反过来想，有一点应该也是适用的：如果公司感受到了你对他们的强烈兴趣，哪怕面试结果可上可下，也可能因此招了你。所以充分展现自己的兴趣，对于dream company应该会有加分。
Square
square是一家做移动支付的startup，是一家我唯一没拿到onsite的公司，原因是面试题目的确不容易。先是在网上做两道题目，然后电话面试。电面1小时希望做出两道题目。我拿到的题目是四则运算和Unicode string。想当年我面试的时候Square是硅谷最火的公司之一，现在两年过去了，Square的前景日趋暗淡，由此可见硅谷的残酷：在有无数人通过公司上市成为百万千万富翁的同时，更多的人默默地被技术变迁的车轮碾压过。
时至今日，我也从interviewee换成了interviewer，加上平时也乐于帮朋友改改简历，指导指导面试，我一直有遇到一个普遍的问题：朋友总说，我cc150（北美流行的面试参考书）刷了两遍，leetcode（在线编程网站）刷了两遍，算准备好了么？还应该做什么题目？去看看EPI（另一本难一些的面试书）？是啊，其实我自己也在想，怎么样做题算是“够了”？就和准备高考一样，3年模拟题做完做5年的？本地的做完了做全国的？
我高中参加数学竞赛，那时具体的题目、公式都忘得差不多了，但学到了一点终生受益：要把做过的题目联系起来，然后总结方法。寻求为什么这么做，而不是怎么做。否则，不通过举一反三，而寄希望于在考试／面试时出现做过的内容，那就真是“以有崖求无崖，殆哉矣”。这里，我只谈方法。给个实例：
大家可能都觉得，算法题中动态规划是比较麻烦的问题。但当你碰到这类问题时，仔细总结过方法么？考虑过题目为什么要用动态规划么？动归和递归的区别在哪里？
我觉得，从子问题解决原问题, 无非是两种方法，自底向上(Bottom-Up)与自顶向下(Top-Down)，形式上前者对应iteration，利用循环将结果存在数组里，从数组起始位置向后计算；后者对应recursion，即利用函数调用自身实现，如果不储存上一个状态的解，则为递归，否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子：
1) 自底向上
int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
array = array[i-1] + array[i-2];
事实上，额外空间可以进一步缩小到O(1)：利用几个变量记录之前的状态即可。由于记录了子问题的解，故给出的方法就是DP。事实上，自底向上的方式往往都是通过动态规划实现。
2) 自顶向下
int Fibonacci(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
为计算Fibonacci的第n个元素，我们先自顶向下地计算子问题：第n-1个元素和第n-2个元素。由于没有储存子问题的运算结果，给出的方法是递归。然而，Fibonacci(n-1)与Fibonacci(n-2)包含很多重复的子问题，所以DP效率更高。如果用一个全局数组，将子问题的解储存到数组的对应位置，在重复计算的时候直接读取计算结果，那么就是DP的解法。
动态规划的核心在于，如果通往一个问题的solution，subproblem被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。在递归过程中用hash table记录中间计算结果的DP，称作Memoization。
Memorization的一般形式是: 建立以input为key，以output为value的hash table：
T func(N node, HashTable<N, T>& cache) {
If (cache.contains(node)) {
return cache.get(node);
}
…
T sub_res = func(next_node, cache);
…
T res = G( sub_res … ); //当前子问题的解，依赖于更小的子问题(s)
cache.set(node, res);
return res;
}
从解决问题的角度来说，用Bottom-Up的DP，固然通常可以节省递归本身的空间开销，但有很多缺点和局限：较难理解，边界条件较难处理，只适用于问题的节点空间是离散的整数空间，必须一步步邻接、连续地计算(无论是不是每一个节点的结果都会被用到)。而Memoization，则灵活得多：可以从递归形式轻易修改得到，也更符合普遍的思维过程，并且没有上面说的这些局限，子问题只有在被需要的时候才会被计算。尤其是在某些情况下，不仅需要aggregate的结果，还需要获得achieve这个结果的路径，这时候就算用Bottom-Up的DP，也需要记录prev节点，最后需要递归回溯得到路径，那么节省递归空间开销的优势，也荡然无存了。
因此，当理解到了一定的深度，真不是特别在乎做了多少题目。与之相关的另一个问题是，准备周期得有多长？就我个人的经验，如果准备的时候极其认真，真正投入加仔细思考方法，几个月搞定心仪的工作也不是不可能。就看你理解的有多深。
如果一味地只追求做题目，这样的只练不想还有两个问题：
1. 看到类似的题目就硬套方法。当面试官要求换个思路时会感觉很困难
2. 看到没见过的题目有时就会慌，结果连正常水平也没发挥出来。
总而言之，希望大家能换个方向看刷题，与其做上两遍，三遍，不如花相同的时间认真总结下适合自己的方法。希望我们总结的《程序员白皮书》，能给初入职场的你带来一些面试准备上的灵感。