这篇帖子分享我面试18年google暑期实习的经过，包括一点刷题经验和电面面经。
我17年9月-11月比较集中地刷了一些题。在此之前，我在16年也10-12月也刷过题，不过那个时候是随便做做，没有花很长时间。一直到面试前，在leetcode上做过的题大约有300道。其中，我按照知识点，把一些知识点（比如BFS，DFS，二分法，union and find等）的常考题刷了多次。但是还有很多题做完一遍就忘了，我也没有复习。leetcode的discuss中有很多优秀解法，可以参考。
临近面试之前，我买了会员，开始刷leetcode上tag为google的题目。但是这一部分题目增加非常快，有好几百道，而且没有什么定式，很多不能用之前的刷题常用套路来套。所以我只做了所有easy的和一小部分medium的，练了练做新题的手感。据说Facebook的题目很容易碰到原题，而Google有很大的题库，不容易碰到原体。所以面试的时候也有碰运气的成分，看当时能不能想出来了。
第一次电面在十一月份。面试时，面试官会给你题目，但是不像刷题时有定义好的函数让你填，函数要自己定义。我的第一场遇到了原题，是 merge k sorted lists。用heap来做，分析了一下复杂度，很快就结束了。第二场的面试官解释题目解释了好久，大致是给定一个 tree 和一个 API，要求删除tree中的一部分节点，返回删除节点之后形成的forest。可以对每个节点调用这个API，API会告诉你此节点是否需要删除。比如
1
/ \
2 3
/ / \
4 5 6
删除 2，5 节点的话， 就要返回 forest
［4，1］
\
3
\
6
我本来想直接遍历来做的，耽误了很长时间。后来才想到用 recursion来做。第二问，如果是BST，给你这样一个forest和删除的节点，如果组成原来的tree？我没做出来，没时间了。
我以为挂掉了，结果第二天HR联系我说要加面，约了12月份。结果我12月份回了国，网络出了问题，只好delay到1月份。
第二次面试不是用电话，而是hangout面试。
第一轮，面试官问了三个问题。第一题，一个doubly linked list，给定一个数值，target。让你删除此list中第一个出现值等于target的node。他强调了这个node有可能是第一个。这道题，在前面加一个dummy node就好。第二题是给你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictionary中出现。substring的意思是删除原word中任意数量字母之后，剩余的string。比如. 1point3acres
dictionary = {inter, te, as, ads, innal}, word = “international”， 那么这个substring就是 innal
第三题，给你一个m*n的矩阵，0代表水，1代表陆地。一片相连的陆地叫做一个小岛。操作是：本来这个矩阵全是0（水），每次会提供一个座标（i，j），你就把相应位置的水变成陆地。问你每次变之后，矩阵中小岛的数量。这个题用BFS可以做，但是用union and find复杂度会低很多。我当时说，用union and find做。说完之后，面试官和我都心照不宣地笑了。写完后他甚至没有检查我的代码。
第二场，竟然是个是system design的题目。我不是CS专业，其实有点虚。题目是让你实现两个API：
start（ID，time，msg）
end（ID，time）
说，假如你是个服务器，程序员要用你计算资源跑他们的任务。当他们开始跑的时候，就调用start，并附上相应的时间和message。结束的时候也调用一下你的API。你需要把所以的任务，按照开始时间的顺序，把它们的ID，msg，纪录在一个log里。log只能写入，不能删除。
我不是很漂亮地写完了。第二问，是如何改进这两个API。我只好胡说一气。结束后，得知比较好的答案是，time可以用本地的time，而不依赖于传来的time 参数。因为可能有网络延迟。
第二次面试，第二天就告诉我通过了。但是也有很多人是面试完很久才通知的。这是因为面试官feedback有可能给的很慢，不代表每面好。
我觉得刷题的时候，因为不太好撞到原题，所以还是要注意基本功。另外，面试的时候，hangout面试真的比电话面试感觉好太多了。和面试官能互相看到的话，交流会非常顺畅。他们对面试的打分重要的一项就是否擅长交流，占权重的四分之一。