首页 > 笔试面试题 > 2013百度校园招聘面经

2013百度校园招聘面经

2012年10月4日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

百度校招在大连站比较早,也比较迅速,十一假期前已经发放offer,我投的研发职位,有幸拿到了offer,这里贴个面经。

笔试

笔试前面是考察知识型,后面算法设计和系统设计还是比较有意思,题目就不一一列举了,这里有童鞋都码出来了。简单说下算法设计和系统设计,欢迎讨论。

算法设计1,锦标赛排序,赢者树;

算法设计2,程序写起来简单,但是写完程序也不知结果,哈,如果要直接分析出答案,有一定难度,网上有分析很给力,在这里

算法设计3,多路归并,败者树

系统设计题

这个题目比较复杂,原因是需要检索出的结果可以是电话号码中的连续子串匹配结果,也可以是姓名拼音的匹配结果,我没有好的思路,只有个模糊粗糙的方案,列出来欢迎讨论。

数据结构:Trie树,树的节点结构大致包含Next指针数组与存储resultUser的Vector。

方案:对电话列表进行预处理,建立索引系统;索引即trie树,不过这里不是字符trie,而是数字trie,因为用户输入是数字号码串;考虑到电话号码的连续子串也进行匹配,我做如下处理(比较粗糙)。

对于UserList<UserName, PhoneNo>中的每一条记录进行如下两步处理:1)电话号码的每个后缀串插入trie树,同时插入该联系人入相应Vector;2)对于UserName的姓与名皆转化为拼音,然后将拼音对应的数字串插入trie树,同时插入相应的联系人于Vector。大致就是这样。

面试

注:所有的面试题目这里不做详细整理,等忙过这段再细细总结,欢迎留言讨论。

研发面试一共三面,木有HR面,三面都是技术面试,只不过第三面是经理面,主要是讨论项目,各种聊天。

一面

一面只面了25分钟,可能是百度一面只问4-5个问题,如果碰巧顺一些就能比较快结束。

首先是自我介绍,一般报完姓名就说一下自己的研究方向、兴趣,最好说一下自己擅长什么,也有利于后面面试;然后就是开始做题

题一:因为我项目的原因,问我URL去重,答:用哈希;问了哈希缺点,答:内存利用率不高,数据量大,易冲突;问内存放不下怎么办,答:bloom filter;问还放不下怎么办,答:分布式,URL哈希分配到不同的机器上;

题二:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

我先给出了一种暴力方案,O(nm)的复杂度;之后想了一段时间给出了一个优化的O(n)思路,但是面试官说我的想法和方向都是对的,只是会有特例解决不了,到现在我也不知道特例是啥,最优的解法是什么,欢迎牛牛们留言指导

一师兄给出方案:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。好方法啊<大拇指>;

题三:括号匹配合法性,考察栈

题四:给定字典,输入一单词,查找兄弟单词;这个问题《编程珠玑》有讨论,但是它提供了一种比较费时费空间的方案,可以直接使用trie树来做,估计也是面试官所希望的

题五:new与malloc区别,答出最重要两点即可(new自动分配空间大小;new会执行构造),考察理解

题六:纯粹知识型问题,进程与线程区别

结束,问我是否有问题,提了两个问题面试官就说到这里了,走人;第二天晚上接到二面通知。

二面

二面就比较惨了,面了75分钟,问的问题较多,先说个大概。

先是问了问项目哪个自己觉得ok,最大的收获是什么,我bla说了大概有三五分钟的样子;然后开始做题,上来就是一道DP,没答上来。

题一:POJ原题2192,开始没向DP方向考虑,这个题目跟面试官讨论了很久,我想了好多思路去沟通,但不是太复杂就是有特例解决不了,后来我也考虑过DP,但是没想出来子问题,比较挫,大概有20分钟吧,就跳过了,这个时候我已经有点傻了

题二:最近公共祖先问题,不准使用父节点指针;这个先是跟面试官说了下如果是二叉搜索树怎么做;然后对于一般二叉树先给出了一个比较暴力的方法,最后想了大概3-5分钟才给出了面试官满意的方案。

题三:最长距离叶子节点;这个问题《编程之美》中有讨论,注意各种情况考虑全面就行;

题四:如何判断是否存在连续子数组和为0;

题五:n个数,求n-1个数的乘积;这个问题在《编程之美》也有讨论,我只是记得部分积的方案一,后来在面试官的引导下才想起了方案二,注意各种情况考虑周全,面试官会让罗列出所有情况。

题六:最长不重复子串,这个本博有讨论,见最长不重复子串

题七:面向对象设计五个原则;快排与归并的区别;继承与组合的区别;

大概第一题耗费了太长时间也没有做出来,面试官就多问了些,其实我还是很感谢那个GG,总是笑着,在我开始答的不好的情况下能多问一些来了解,而不是直接否定。二面过后就让回到HR在的房间等候三面通知。

三面

三面估计是经理面吧,主要是聊我自己做的项目,问我对lucene的理解;问我知道海量数据处理方面哪些开源的东西;问我对缓存的理解,这个我举了索引的缓存和查询器的缓存例子;问我最大的优势是什么;对C++、java的理解;快排的非递归实现等等;由于是聊天形式,记不太清楚了,大概这样子。

总结

一点拙见,轻拍

1)   平时要注重积累

2)  面试时,题目可以不会,但是一定要有积极去思考,去探索思路的行动,不能在那里闷着,然后告诉面试官不会或者想不出来,面试官会把握时间,只要他不提醒你跳过这道题目,就一定要用心去思考,有了稍微眉目的思路就跟面试官交流。

3)  暴力方案虽然挫,但也是一种方案,说出来,增加与面试官的互动。

4)  如果思考时间有些长还是想不出思路,可以寻求跟面试官的交流,可以暂时没有解决方案,但是自己应该知道是朝什么方向去做,例如要减少暴力方案的重复计算;或者要记录一些预处理信息等等这样的,跟面试官做一些讨论。

5)  遇到坎儿,最不能沮丧着脸,你闷面试官也闷,要沟通,要表现出你的乐观和乐意接受挑战并享受解决难题的乐趣吧。

印象

到现在为止,本人只面过三家公司,对各家面试流程与面试官的印象也各不同,这里说点对百度面试的印象:

面试官一般都很友好,总是笑着,很亲切,不像某司的面试官总是板着脸,一副不屑的样纸,不够包容,不好;面试过程中,百度面试官会用笔记本做非常详细的记录,综合几面对你进行了解打分,而且如果前面你答的不好,他后面会尝试多问一些以加深了解,不像某司的面试官一道题目定死人,也没有记录,很随意;从这些可以看出公司文化、员工对新人的包容以及流程的规范性,当然不是一定怎样做就是好的,还是看公司。

最后说点感受,面试除了实力,很大程度看运气,不同面试官差别真心较大;所以,努力准备,一切随缘,也用这话给自己接下来的应聘打气、加油!

(全文完)

  • Royn

    Royn :线段那个题,http://codepad.org/X74TrSEi 这个解法你看算优么,我不知道有什么特例,稍微DP了下。

    额,原来写的太傻了,这个简单些。http://codepad.org/vZ5ktTH7

    • Yx.Ac

      @Royn 抱歉这么晚才回复,昨天整理评论时才看到;嗯,个人觉得这个代码是最优的,就是两个指针跑的思想,两个指针这种思路的题目见过好多呀,确实很好用; :-) ,多交流

  • Royn

    线段那个题,http://codepad.org/X74TrSEi 这个解法你看算优么,我不知道有什么特例,稍微DP了下。

  • http://www.felix021.com/blog/ felix021

    建议在入职之前(至少是拿到offer之前)不要公布笔经面经,不太好

    • Yx.Ac

      哈,好的,谢谢 felix021。

  • rabbit2duck

    唉,可惜被pending了

    • Yx.Ac

      哈哈,加油呀,楼上定哪里了?我们可以多交流 :-)

  • Mae

    ~~nice ! congratulations!~~inspired !

    • Yx.Ac

      哈,谢啦,不过拒掉了 :-)