去三藩面了Dropbox，Uber和Twitter，主要是infrastructure的new grad职位。

Dropbox：

财大气粗的Dropbox不愧为dream company，每天可以报销伙食费90美元，是我面过的公司给的最高的，并且还可以额外住一天酒店并报销100刀的观光费用。HR还很贴心的列出一堆景点，以供游玩。里面的工作环境很赞，食堂不错，白人比例高，由于靠海，view也不错，可以看海边日落。

需要注意的一点是，在代码写完后，不少人会拍个照，所以代码还是写工整一点比较好，这个一开始不知道，字迹潦草了点有些吃亏。

第一轮问research和behavioral questions。

第二轮是Game of life，一个二维数组里，每个元素有生和死两个状态，根据周围元素的生死情况按规则进行状态转换。Follow up就是对大的file操作，而非内存中的数组。基本属于纯实现题目，很简单。

第三轮 实现web crawler。follow up是网页抓取和网页解析的异步实现。其实就是异步实现BFS。我用了三个queue去实现，除开一个本身BFS需要的queue，另外用了两个BlockedQueue，不知道对不对。

第四轮实现两个函数，int allocate()和void release(intid)，每调用一次allocate返回的id需要unique，为1到N之间的一个整数。如果release以后，就可以继续被allocate。之前用array+hashmap，达到O(1)时间和O(N)空间。后来被告知空间用得太多，map空间效率低，最后用了bitmap。这题其实和实现文件系统的metadata区域比较类似，不过最后居然是用时间换空间，有点让我诧异。

第五轮系统设计：对分布式的server，获取对每台server各种信息汇总后的time series。非常的open-ended，反正把各种系统设计原理都用上就行了。

加吃饭一共面了6个小时，还有些题目不记得了。。。

Uber：

最大感觉是公司扩招得很厉害，但是体制的改进以及设施的更新都没有跟上，很多地方都不成熟。面试过程其实也不怎么规范，还要求带上自己的laptop。感觉由于快ipo了，逼格非常的高，题目比起FLAG难不少。

第一个面试官是烙印，感觉挺不友好的，一开始讨论项目经历的时候就各种不以为然。然后40分钟问了四个问题，根本没时间做完。第一题是LeetCode原题，next permutation，秒之。不过烙印一开是怀疑我的思路，后来费不少力气才说服。第二题是实现hash map，指明非要用chaining的方法，CC150上应该有，也秒之。最奇葩的是，刚开始写了一部分代码，后来烙印觉得我代码排版不够好，于是给我擦了，中间划了一条线，让我用双栏排版重写。（总共就只有一块很窄的竖着放的白板，白板上面1/3的空间其实浪费掉了，因为手根本够不着）。无奈就费了一些时间重写代码。之后让我实现concurrent map，有点实现读者写者问题的感觉，没时间写完。还剩5分钟的时候又问如何在chaining的机制下实现load factor，实在不会，后来发现答案其实解法刁钻。其实三哥也就进来了一个月，感觉牛逼哄哄的，做题的时候一直在旁边指手画脚，比如算法设计的时候一开始很容易声明一些多余的参数，等题目探索完了其实往往也就一目了然，自然最后会去掉，可是三哥中途非要指着说认为某参数不必要，严重影响了自己探索问题的乐趣和连续性。另外我也严重怀疑他如果不看标答，是否能够一开始就知道某个参数是最后不必要的，

第二个人就一道题目，感觉很难，想了40分钟才想出来一个解。要求设计一个数据结构，满足insert(int key)，remove(int key)和int getMostFrequentKey()。对于同一个key，每次被insert，计数加1；每次被remove，计数减1；然后需要取最大count的key。要求所有操作都是O(1)复杂度。

这题首先通过尝试排除掉map+maxHeap的组合，然后又联想streaming max等各种尝试。后经过提示数据结构需要保持部分的排序性质（如果保证完全排序，插入删除操作是不可能O(1)的）。考虑到需要统计的count是整数，我就想到了bucket sort，另外联系类似LRU设计思想(doubly linked list + hash map)，设计出了如下结构：

class Node {

         int key;

         int count;

} 

class Bucket {

         Set<Node>set;        // All the nodes with equal count.

         Bucket prev;

         Bucket next;

}

Bucket head;

HashMap<Integer: key, Node: node>

虽然这个解被证明是可行的，但总感觉自己的设计有点过于复杂。做完这题后，脑力废去大半。。。 

第三轮设计一个游戏，从起点到终点有两条不重合的长度相等的路径，每沿着当前路径走一步，需要耗费一定体力，如果切换到另一路径的相同位置，也需要耗费一些体力。每次只能继续往前或者切换路径，要求打印出消耗最少体力的路径。其实就是一个一般难度的DP问题，不过这个年代还考DP的真不多了。后来讨论了functional programming，要求给一个链表和一个filter函数指针，输出一个filter后的新链表，只能用递归写。其实iterative转recursive也不难。之后跟我讨论kmeans的并行实现，然后让我猜另一种clustering算法。我猜了hierarchical clustering和density-based，结果都没猜对，最后告诉我是想让我答EM算法。狂汗啊，我压根就没有把EM放到clustering分类里面。最后跟我聊了下最大似然估计。统计方面的东西自己不怎么懂，有些郁闷：自己明明面的infrastructure team，可是这货怎么总往machine learning上聊呢？这new grad要求也太全面了。。。

第四个人主要聊背景是否跟team match，题目只出了个power set，算是最后放松了下。

Twitter：

问题都不难，这里就不透露太多细节了。

1.      质数问题变种。

2.      各种sampling的问题，大数据的，分布式的。

3.      LeetCode原题：Clone alinked list with random pointers。

4.      设计如何分布式存储tweets，包括保持排序性质什么的。

5.      字符串匹配问题，都还没涉及到什么fancy的方法例如KMP什么的时间就完了。

6.      设计一个Timer class。

 估计由于我的项目经历，很多问题最后都延伸到了分布式实现和用MapReduce实现。

之后去SF面完Airbnb再继续补充。。。

San Fransisco Onsite面经