谷歌中国（Google）SDE面试经验

Google猎头联系的。然后一次电面，问了基本的语言知识，没有什么难度。 搞笑的是问你各种语言的熟悉程度，我说我C++ 8分，HR不信，非要让我最后说只有5分。

一共两轮面试，第一轮问了一道算法题，内容跟leetcode一个原题很类似，是read4 byte的变体。 第二轮问了两个eady题，主要是string manipulation。总体来说比较简单，问了一下时间复杂度和空间复杂度的问题。

总共面了四轮： 第一轮：定义buddy system为一棵complete binary tree。一个node可能为0也可能为1 . 它的 value为1，当且仅当它所有的child的value均为1. 1 | 1 2 | | 1 2 3 4 | | | | 1 2 3 4 5 6 7 8 实现下列的method。 1' clearBit(int offset, int len); 2' setBit(int offset, int len); 第二轮：设计一个task dispatching system，里面有一个task queue和两个function。 1’ trigger。这个function运行并清空task queue中所有的tasks。 2‘ addTask。在trigger之前把task加入task queue，在trigger之后直接运行task。 第三轮：产生一个圆上的所有坐标。不用sqrt, sin, cos等内建函数。 提示：所有的点都是整点。首先我们可以利用对称性把圆分成8块，先画出0-45度角内 的点，然后映射之。对于其中0-45度角中的点，当X＋1时，Y的值或者不变或者－1，然 后放入圆方程中看哪一个是对的。 第四轮：设计一个Map，满足下面的复杂度。 add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of elements)。 提示： 如果我们用randomly accessed array，复杂度如下： add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate: O(size of array) 如果我么用sequential array, 复杂度如下： add: O(1) deletion: O(number of elements) lookup:O(number of elements) clear: O(1) iterate:O(number of elements) 所以我们需要把这两个方法整合起来。

问了一道c++语法题，还有一道算法题，算法题与面试者的思路不一致，感觉双方没有在一个频道交流。