【转】baidu 面试题偏向算法（1）

人研究生二年级，申请百度实习，虽没到实习高峰，就算早做准备吧。

本人电路与系统专业，不是正牌的程序猿，虽说学过c系列编程以及数据结构，但大都基础不牢固，而且根本就没学过操作系统。

经师兄（大牛，百度正牌成员）推荐，本人简历成功到达某位hr手中。hr接到简历大概三天后给我打电话，主要说了下实习时间问题，说最好半年，我说再商量下，因为不可能出去半年时间，三个月最多了，然后说明天下午五点给你安排电面~~~来的太突然了，都没怎么准备呢。

第二天下午，在实验等待，叫了另外一个大牛师兄陪我，面前有电脑，可以救急。5点整，果断接到010开头的电话，百度果真准时，是一位gg，声音很有磁性，但是有点小，我提出让他加大声音，可是还是很小，这也多少影响发挥了吧。上来首先是自我介绍，大概说了下基本情况，不到两分钟吧。然后说了下现在做的项目，因为当时还是很紧张的，所以没怎么说好，这项目应该是我的强项，项目是关于成像然后后处理，中间说道openCV，gg问openCV如何进行矩阵操作，当时没怎么听明白，因为是第一个问题，也没敢叫他详细解释，就说了句用数组，不过后来感觉应该用openCV自带的类来进行操作。我把项目陈述完之后，gg听完来了句反正我也不懂，咱们直接来考题吧 。


第一题，介绍熟悉的排序算法。
由于对这个不是特别了解，之前看百度百科介绍过，记下来了几种，说了三种吧，然后gg狂问时间复杂度。感觉百度很关注这个，真实狂问时间复杂度啊


第二题：已经排序两个正整数数组，等长，如何找到两个数组里面全部数的中位数。

想了一会，想到直接查找每个数组的中间数，然后比较，如果不等的话，向相应的方向移动数组，每次移动一位。gg问了下时间复杂度，然后让我找到复杂度更低的算法。后来想到了二分查找！其实这道题的关键就是二分查找！第一反映没到位，不过想到二分查找时，却没搞明白查找终止的条件。这个应该给自己减了不少分。

第三题  两个文件各存50亿个url，求两个文件里同时出现的url。

说了句最简单的方法，逐个查找，逐个匹配，就像字符串匹配那样。后来gg说如果考虑内存应该怎么办，其实这道题我之前见过，但是gg也没描述清楚吧，应该还有内存是多少，每个url多少字节之类的信息，不过我也没细问，想了一会，说用hash表，之前看面经的时候说用hash表，就表达了我的意思，但是具体如何操作，我就云里雾里的说了一通，因为我着实对hash表不是很熟悉，从来没用过，最多算是了解吧。

第四题  gg说是经典的字符串反转问题

我说简单的方法，开辟一个新字符b，b=a[last],a[1]=b,a[last]=b，然后依次类推。

后来说，句子里面的单词反转，这个我答的很糟糕，因为之前看过一个类似的题，就按照之前的思路想了下去，后来发现是不节约空间的，复杂度很高。

第五题  字典查找问题，给定一个英文字典，给出12个不重复的字母，如果字典里的单词由这12个字母或12字母里面的某几个字母组成，则把此单词跳出来。

给出的第一个思路是用不同的质数代替不同单词，然后算每个单词的成绩，和12字母所有可能组合单词所对应的质数乘积，最后用质数成绩匹配。  

后来我又提出可以用排序组成。gg果断说还是用排序吧。

我说每个字母按照一定顺序排列，12个字母按照相同的顺序排序，然后逐个匹配，期间gg说了不考虑字母重复问题，使得问题简单不少。


问题就到这里，gg问我有没有什么问题，我说了一句，不管结果如何，一定要通知我一下，然后他说他不方便现在说。

总结：

1）基础知识薄弱，毕竟不是软件方向。而且现在头脑已经不灵活了，研究生把知识学死了！

2）紧张，这是第一次电面。想问题的时候，电话两边都不说话了，我就感觉很紧张。。。如果是好基友，应该不会有这种感觉吧。

3）不知道该说什么，对gg所说的题目没有深入研究，也没有完全听清楚。应该要求gg描述的更详细些，甚至给出答案，下次一定注意。

4）百度果然看重url游戏，要弄清楚url的各种运算，交，并，求余……尤其是大量url的。。。。。而且喜欢各种排序…………

5）对自己项目描述的较少，只说了一个项目。


师兄刚才说，那个gg是他的指导人，师兄看见gg在打电话，Hi了句“在面试吗”，gg回了句“这个人被我问懵了”…………后来师兄也没再跟他说什么了！！！


还是要扩充知识面啊，多看面经还是管用的。


希望以上的东西对大家有用，如我描述的不清楚 可以讨论。。。


顺便攒人品，希望进入下一轮。。。北京面试！！！！求人品爆发！！！！！！！！！！！


转自：http://bbs.yingjiesheng.com/thread-1611550-1-1.html#11526-tsina-1-93838-3c21f3533a41d5cddf31831b88a99f81 ;