Google电面经历 Google, 经历Google, 经历

yesxu

  09月底或者10月初投的resume，都快忘了这码事了，突然11月02日接到一个电话，就是前
面贴子提到的那个回电说空号的那个号码，一个估计是hr的mm通知说11月04日上午09时有
个电话interview，之前也没自报家门，难怪前面那位老兄会当成骚扰电话挂掉，
cmft...11月04日上午09时10分接到电话，来电显示是+1951101，面试官是身在Mountain
View的华人，在Google做Software Engineer，中文面试。开头先是寒暄几句，问了问做
过的最得意的项目和最大的项目分别是什么，然后进入正题，第一个题目问一个二叉树，
把它所有节点打印出来，我一开始以为是要在终端印出一个树型的样子，所以就说广度优
先，然后他讲只要把所有节点打印出来即可，就是一个普通的遍历，他要我写出代码，然
后一个字符一个字符读给他听，我写了几行，懒得写了，就直接讲给他听，说先定义一个
struct tree_t，里面三个成员，叫value，left和right，然后定义一个函数叫process，
里面三行代码叫print value，process(left)和process(right)，就ok了，给果让他抓了
把柄，说这是个infinite的递归，很ft很弱智的疏忽，偶说偶对电面不太适应，难以集中
精神思考，事实上的确如此，改了if NULL的问题，他又问给出两个节点，要求它们在这
个binary tree里面的最深层的公共节点，我思考了大约几秒钟，很快回答说只要在
process返回一个值，如果left和right又一个等于给出的节点，就返回true，否则返回
false，当检测到process(left)和process(right)都是true，那个结点就是所就结点，结
果又让他抓了把柄，问value怎么办，只好认输，更正说检测left和right的同时再检测一
下value。他又问如果给出N个节点，求它们的公共结点又如何，这次我几乎马上就说只要
不返回boolean型，而是返回一个整数就ok了，他最后问道这种先打印value的递归怎么称
呼，我回答前序遍历，他把这个词用英文对我重复了一遍，换第二个问题。他先问对网络
协议是否熟悉，如果不熟悉可以换题，我说我对HTTP协议比较熟，于是他问TCP连接建立
时，客户端和服务器端是如何交互的，我以前做过sniffer，所以对TCP还比较了解，于是
答三次握手，客户端先请求服务器，服务器返回，客户端再请求，他问这三个请求的具体
细节，他一边问我一边就打开了http://en.wikipedia.org/wiki/TCP，凭借快速在网上搜
索信息的技巧，找到了SYN/ACK的具体细节讲给他听，他又问TCP header都会有什么数据
成员，我一时手忙脚乱，竟一时没从那网页里找到相关的内容，就凭感觉说一定会有端口
，而且是两个，source和destination，又说应该没有ip，ip应该在ip层里面，他又问还
会有什么，我凭以前sniffer的印象，说应该还有序列号和checksum，他问序列号英文叫
什么，我一时想不出，就快速搜索wikipedia上面的文字，看sequence number比较像他问
的，就说给他听，然后他问seq num有什么用，我以前搞过p2p protocol，所以比较容易
猜到seq num在网络协议里面的一般用途，说是确认ACK时该ACK哪个seq num的packet，他
听了似乎比较满意，说你了解的东西还蛮广泛的。第三道题目他先是说这东西可能没用，
说stack和queue哪个更基本一些，我马上说stack，并告诉他我知道是stack，但不知道为
什么是stack，他又具体举了个例子，说1和-1哪个更基本，我几乎没思考就说是1，他说
是-1，因为-1*-1可以得到1，而1怎么也得不到-1，我辩解说这要看你怎么定义“基本”
这个词，于是他回到了stack和queue，说其中一个可以模拟另一个，而反之不行，我重复
了他的问题，说等同于系统只提供了stack这个数据结构，没有提供queue，要我用stack
模拟queue，但是最后我绕了一大圈，把问题搞得很复杂，甚至往hanoi方向上想，也没想
出如何解决这个问题，当然挂了电话以后很快就知道怎么弄了，一只手拿着电话听筒确实
没法思考...最后他问有一个random number generator，是生成真实的随机数，而不是伪
随机数，这个东西会生成几千亿个32位整数，要我打印数出现次数前100的整数，我马上
就说我的方法空间效率很差，但是这是唯一我能很快想到的办法，就是建一个4294967296
个元素的数组，读generator，然后说如果你要前100，我会循环100次逐一找出，如果你
要前10000或者更多，我会先做一下排序，因为排序是O(nlogn)，可能对于top N，N比较
大时会更好些，但N多大采用快排要实验决定，他说他只是想到了快排，并对我提出N比较
小时逐一找出表示赞同，他又问还有没有更好的办法，我这时不知道想到哪了，胡说一通
哪也不挨哪的方法，说完发现把他之前问题的原意搞混了，于是说恐怕没有好很多的办法
，但可以细节上进行优化。他问如果我不要精确解，而是要近似解又该如何，我说可以随
机从生成器抽取样本，不必把所有数据都进行处理，这样可以大大提高排序的效率。一共
就是这四个问题，答得还算马马虎虎，事先说要45分钟的interview整整花了1小时53分1
秒，偶的电话是全球通，耗资45.60元，不过最后pass了，大概就是这个样子...
[ 本帖最后由 darkheaven 于 2006-3-20 03:16 PM 编辑 ]