baidu:我的处女面经

曲一
有幸能得到zdwaiter的内部推荐直接和百度科学家洪涛面对面进行了长达一个小时的交流。由于事先没有任何准备的就去裸面，因此也就谈不上紧张的问题了，本来就是去学习学习的嘛。

PhD 洪非常和蔼的和我互相打了招呼。初见此人感觉分外亲切，邻家大叔的味道。听着他的口音像北方人，但是他却说自己是土生土长的浙江人。于是我就借着这个话题和他攀谈起来。他热情的介绍了一下自己的情况：温州人，留美，微软工作，最后去了百度。说到我的情况的时候他还和我聊起了家常，因为他的舅舅居然在浙工大教书（如果我没听错的话）...

接着，是例行的技术问题，主要围绕了我做得那个Nokia基于移动终端的基于意图的个性化查询支撑系统。问的非常细致，从架构到实现，在到实现中遇到的困难，还问了相关的“个性化”和“查询意图”的理解问题。之后问到了我最近在做的sqlite裁剪的项目，项目思路等。这些都回答的比较顺利，毕竟是手头在弄的东西。

最后说到了两个算法题目，一个是如何判断一个Link-list存在回路的问题，另一个是对一个给定的长度为N的数组（已知这个数组有一个元素的出现次数大于N／2），找出其中出现次数大于N／2的那个元素。第一个问题我20秒就给出了一个可行的解：用一个bit标识是否被访问过，每次遍历之前都检查这个bit即可，但是PhD洪认为这不是最优解，如果这个链的长度在百万级别以上的话空间的开销是十分巨大的；然后又过了几分钟我想到了第二种办法（事后证明这个方法是错误的）：用两个指针，一前一后遍历，pre指着某一个元素，让cur往前走，如果pre和cur有重逢的话那么存在环路。他先停顿了一下，然后问道：你确定这个方法可以保证找出任何环么？原来我忽略了一种情况：非首尾环的问题。但是我觉得我的这两个回答也算过得去了，至少说明我还是懂一点数据结构的:)。第二个问题我开始也是很sb的要开一个辅助空间记录，当然也是不满足大数据量的要求的。时间已经过了1个小时了，Phd洪也就直接和我说答案了，其实真tmd简单，纯粹是个要求细致观察的问题，唉。

临走前他嘱咐我给baidu发一个电子版本的简历，就这么结束了。非常有意思的一次经历。