Google面经

from here




这周之内刚刚面的，趁还没忘，记下来给大家分享一下。因为签了NDA不想混不下去，具体题目内容就不说了，大概以leetcode难度为参考说一下。

总体感受：难度不是特别大，着重用算法知识解决问题的能力（当然还有算法复杂度分析的方法）。个人觉得Cracking the Code Interview里三句话很重要：

1. 做过的题就老实说做过了；

2. 如果你想要做任何假设，请先和面试官确认，尽量别等他/她问；

3. 重新看一遍你找工作时给recruiter的简历，确保别人问到上面的每个项目你都说得出来。




早上第一位面试官（第一位就迟到了，差点误了整天的日程）好像比较junior，所以问的问题比较入门+标准：

1. （easy）二叉树输出

2. （easy）矩阵输出

note: 第二题上来就花时间想了时空复杂度最优的方法，所以也没什么follow-up的讨论。




第二位显然比前一位淡定多了，可能是看前一位问的太简单了，所以加了一点难度：

1. （easy/medium）大量数据找少量最大值

2. （medium）字符串分割相关

notes:

1. 第一题是常见套题，就不细说了；

2. 第二题写了一白板的code，不过我先讲了思路，然后follow-up questions也回答上来了，估计面试官还算满意。

3. 第二题限于面试官约束的数据结构，写出的不是平均时间复杂度最优的方法。




中间是午饭不叙。




第三位目测介于上午两位中间，还没看同事问过什么问题，就甩出了一个和上午第一位本质类似的问题。我老实说我已经答过了，他又甩出了这个问题的扩展版：

1. （easy/medium）二叉树输出的扩展版，区别在于二叉树里的数据都有规律，问怎么迅速输出某一个节点的值，我用了log(N)的方法（懒得算数学的情况下是最优的）；

2. （easy）多路数据合并。

notes:

1. 第一题有follow-up是问怎么写test case测试我的算法是对的；

2. 第二题也是常见套题的变形，主要是实现细节；

3. 面试官问了很多简历上的问题。




第四位面试官感觉可能是四个人里最senior的，临时顶替另一位同事都毫无压力。只甩出了一个他自己的原创问题，看我怎么解决。
notes:

1. 问题细节不便透露，但总体来说是一个很开放的问题，他在不断观察你设定了什么假设，以及利用你的知识背景做出的什么样的决定；
2. 有什么疑问随时和面试官交流，在这种开放性问题里这个很重要；

3. 在面试官提示的时候积极思考解决方案，尽量不要让他指出你的bug，并给出合理的解决方案；

4. 这位面试官是street view组的，所以问的问题里面工程性的坑非常深，需要你做出很多合理假设，并规避一些可能存在的现实问题。