12/17 号 – Google – Intern 电面 总结

原帖地址:一亩三分地

1小时前刚刚面完,来地里回馈社会。

第一轮是中国小哥,非常非常nice, 题目非常非常简单。
给一个positive数组,比如[1,2,3,4],代表 数字 1234,要求对这个数字 1234 加一,然后依然按照数组的形式返回结果:[1,2,3,5]

int[] increment(int[] input);

题目太简单了,只要把carry注意一下就可以了。
但是人生第一面,LZ太紧张了,差点搞出麻烦。不过面试小哥超级好,几次犯错都给提示了,最后直接讲中文聊天。。
后来他又问了一下如果数组是negative怎么处理。依然很简单。
他直接告诉LZ会给高分。。

第二轮是个白人大叔,感觉很严肃的样子,完全不废话,自我介绍都省了,直接做题。但是问的也超级简单。

第一道题,String 数组去重,但是保留原来的顺序。超级naive..
[‘a’,’b’,’a’,’c’] => [‘a’,’b’,’c’],几乎没什么好说的,O(n)时间复杂度,O(n)空间复杂度。

第二道题是问答题,问了问hash function. 问如果hash function 产生confilict 该怎么办。 比如:F(‘A’) = 123,F(‘B’) = 123.
LZ直接说 用linkedList 解决。他又问会产生什么负面效果。LZ回答再坏情况下contains()操作需要O(n)时间。然后就过了。

第三道题考杨辉三角。

1
1 1
1 2 1
1 3 3 1
。。。。

问题:假定row number 从0开始,给定一个row number, 返回这个row. 比如, pascalRow(0) => [1], pascalRow(3) => [1,3,3,1]

超级简单有木有啊。
LZ直接说了一下一层一层往下迭代就行,O(n) time, O(n) space, 然后就写代码了。

写完后他问楼主可不可以换成 recursive 的方法。LZ想了一下,果断可以。
然后他又问recursive 有什么缺点,lZ回答会大量使用栈内存,递归层数太多会出问题。
他说没错。

然后就结束了。。。

最后结果怎么样,看人品喽。

最后祝大家good luck.