发信人: wlk (呵呵), 信区: Computer
标  题: 贴个Google电面经历吧 zz
发信站: 哈工大紫丁香 (Mon Dec  5 13:23:49 2005), 站内

【 以下文字转载自 Work 讨论区 】
发信人: Lerry (驴是的念来过倒·杏红等头墙上爬), 信区: Work
标  题: 贴个Google电面经历吧 zz
发信站: 哈工大紫丁香 (Mon Dec  5 02:40:52 2005), 转信


    发信人： Wonlay （Wonlay），信区： Career_Plaza 
标题：贴个Google电面经历吧
发信站：水木社区（Fri Nov 11 20 ：10：32 2005 ），站内

    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了，大概就是这个样子……

--
RULE 8 - Your school may have done away with winners and losers, but life has 
not. In some schools they have  abolished  failing grades; they'll give you as 
many  chances as  you  need to  get  the  right answer. This  doesn't bear the 
slightest resemblance to ANYTHING in real life.
                                                                ——Bill Gates
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 你猜你猜你猜猜猜] 


※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 222.32.17.43]