Google电面详细经历

2019-04-13 12:42发布

Google电面详细经历
关键字: 电面,phoneview,google
发信站: BBS 未名空间站 (Sun Aug 29 22:50:01 2010, 美东)

本来以为要废掉的电面,居然接到电话,让去onsite。惊喜之余,上来发帖,回报社会。

本人背景:烂校 CS PhD,国内有一点点工作经验。年底毕业。方向很偏僻。

经验教训:
(1)Google看重的就是解决问题的能力和思考过程。结果不是最重要的,最重要的让
面试官知道你的思考过程。并不是一开始给一个最快的算法是最好,详见我的电面第一
题。这一点版上有点误导。
(2)位操作是必考的,一定要准备
(3)常用算法,如merge sort, quick sort, binary search一定要熟悉。
(4)犯一点错误不要紧,如果只是面试官说“还有bug”,自己发现所有问题,应该是
可以的。如果面试官直接指出问题所在,就不好了。
(5)讲话小心不要被抓住辫子。Google的人都很聪明。
(6)电面时有一个好的麦克风很重要,因为要在键盘上写程序。我用的手机自带的麦
克风,有时候听不太清楚。

电面经过:

一开始面试官就没有废话,上来就写程序,用GoogleDoc,一共两题

第一题: Reverse一个字节的所有二进制位,例如01110001->10001110
这是一个经典题目。之前准备过,直接写那个最优最经典的

void reverse_fast(….)
x = (((x & 0xf0) >> 4) | ((x & 0x0f) << 4)); //头四位和后四位互换
x = (((x & 11001100b) >> 2) | ((x & 00110011b) << 2)); //01位和23位互换,45位和67位互换
x = (((x & 10101010b) >> 1) | ((x & 01010101b) << 1));//0和1位互换,2和3位互换,4和5位互换,6和7位互换
(注:写11001100b是方便大家理解代码,语法是不允许的。)


第二行刚写到一半,挑战开始了

官:请写一个普通的算法,然后再优化
我:(完蛋了,被看出来是背下来的答案,怎么办?)
于是我开始另一个函数reverse_slow.用for循环写,循环四次,每次用位操作交换两位
。中间犯了好几次错误,都是搞反了“与”和“或”,主要是因为紧张。面试官提醒了
好几次还有错误,幸好都是我自己挑出的错误。其中我用了一个函数pow(2, i).
官:pow函数返回的是 double
我:我可以自己定义这个函数,返回整数
官:请优化你的reverse_slow
我:(愣了一下,来了一个愚蠢的回答)spell out the loop
官:(显然不满意),那还有其他方式吗?
我:让我想想,(停了一下),我可以把pow函数的结果写在一个常数数组里
(注:这里优化的太快了,后来回忆,面试官可能期待我用位移实现pow函数,这个我要
自抽嘴巴。)
官:继续优化
我:让我想想,(停了一下),请给一点Hint
官:(乌拉乌拉说了一大堆,其实我没听懂)
我:(灵机一动)输入一共256个,我把结果放在一个长度为256的常数数组里,这是最
快的
官:好。如果不用这个常数数组,比较你的reverse_slow和reverse_fast
我:(在草纸上算了半天)reverse_slow要x次位操作,reverse_fast要y次位操作
(注:我应该抽自己第二个嘴巴。这个答案显然毫无意义)
官:我不是让你算多少次位操作。从time cost上比较。如果是16位或者32位整数呢
我:(愣了一下)reverse_slow是O(n),reverse_fast是O(logn).

第二题:如何merge两个已经排序的数组

这个我面试前一天还默写过。又是在GoogleDoc上写,可以拷贝粘贴。很快写完。不过
还是有一些 typo。不过应该不要紧,是拷贝粘贴中发生的一些错误,经提醒,改正。
(注:不要把拷贝粘贴理解歪了!!!我不是从网上复制代码,是把一个for循环复制到另外一个for循环。大家看一下 merge sort的代码就明白了.面试官可以实时看见你的typing!!!)

官:怎么测试
我:(说了好多,主要意思是边界情况,一般情况,空数组都要测试)
官:(打断我的话,可能是我有一些意思表达得不清楚)那你说一说这个函数的输入和
输出应满足的性质(Property)。
我:输入是两个排序的数组,输出是两个输入数组的并(union),并且是排好序的
(注:应该抽自己第三个嘴巴,union是一个小辫子)
官:你没有考虑重复出现的数。如果是union,重复出现的数应该被删掉
我:对对对。输出应该包括所有的输入,重复的数应该保留。
(注:这句话没有意义,错误已经犯了)

面试完了,觉得没戏了。因为犯了太多的错误。没想到等来了onsite.