百度面试经验

百度面试经验

　　百度电话面试经验

　　我是周四接到百度的电话面试通知的，因为当时正在移动公司上班，说话不是很方便，直接提出改天进行面试(大家基本都会这样做，例如第二天再进行，自己好可以准备一下)，而我直接提出在周六面试，感觉推得有点时间长了，可能给公司的感觉不是太好，我自己也有些后悔，但事已至此，只能这样了。周五还是上班，根本就没准备，直到周六早上读完英语才大概看了一点东西，真的是花时间太少了，自己忙这也不能算是借口，还是自己没有太重视，毕竟这也是自己心仪的公司，怎么能这样对待它呢，如果失败了，自己可能会后悔一辈子，大家可要注意啦，对任何自己想去的公司可要做最充足的准备呀，我这可是前车之鉴呀!

　　进入正题：

　　周六上午10：30，百度的招聘人员打过来电话，并且提醒可以总座机接电话，这点还是比较人性化的。下面是正式的面试环节，分3大部分：

　　1. 首先问你最大的项目经历是什么，其中涉及到很多的细节，特别具体。他会问你的职责是什么，根据具体的职责回问更详细的问题，例如我说我是一个项目组的小组长，他就问我怎么管理项目组，怎么安排的进度、人员，遇到过什么问题，怎么解决的，你们项目中做的最出色的东西是什么，怎么实现的。还会根据你的回答，往下引伸，比如问了我软件是怎么进行版本号管理的，是用什么软件进行管理的吗，我不太清楚这些，这就很尴尬了，就是尽量多的准备各个方面知识吧，估计详细准备一两个项目也该够了。再就是这其中可以把话题引向你准备好的方向，但要把握住分寸，别搬起石头砸了自己的脚呀!我就顺便提了一下我们现在做的项目，可能是做了一段时间比较熟悉其中的一部分内容，想和招聘人员炫耀一下，但是人家问了我别的方面的问题，自己不会，这可丢大人了，所以以后大家要做类似的事情一定要把握住话题的方向，别顺着招聘人员的思路走，要不我们会死的很惨的。

　　2. 详细讨论笔试的题目。可能题目少的话，他会和你逐题讨论。他会问你：你认为你的算法怎么样?还可以有什么改进?然后他提一个算法方案，让你分析给他听，比较这2个方案优劣，他会提出一些其中可能出现的问题，让你分析，可以怎么解决，然后顺着你的方案，找一些不好地方，再让你找方案分析给他听，反正就是非常重视细节，你从宏观上答给他听，他是不会满意的，会一直问你的，可能知道你哑口无言，所以在面试之前，要对笔试的题目好好的准备一下，这点我认为极其重要。

　　3. 问你以后的人生规划，当时给我提供了2个方向，一个是开发，另一个是统计，因为我不知道这2个方向的职责是什么，所以也不知道选什么，就胡乱选了一个，然后他解释了这两个方向的具体职责，我认为刚才说的不合适，就改了一个，这样好像不太好，变得也太快了，所以在面试之前要清楚各个职位的职责，也要尽早确定自己的目标，别给人一种拿不定主意的感觉。

　　最后，结束，应该对招聘人员表示感谢。

　　这可是我的第一次面试，就用了电话面试，不是很舒服，应该尽量放松吧，只有放松才能做好，才能得到自己心仪的职位，否则只能适得其反。

　　百度面试经验分享

　　一面：

　　给你一棵二叉树，如何判断它是否是完全二叉树? 最开始我连完全二叉树的定义都忘了，面试官提醒我之后我才明白是啥。。汗。我当时回答的是先把它转化成数组的形式存储(就是2*n存左孩子，2*n+1存 右孩子的存法)，然后循环判断一下是不是所有的结点都是在数组的前m个位置。

　　给你一个数组，求它的一个子串，使该子串的和最大。 这是典型的最大子串和问题，我直接就说这是个经典的动态规划问题：令F[m]表示以第m个数为结尾的所有子串中和最大的子串的子串和。则若F[m- 1]>0,则F[m]=F[m-1]+a[m],若F[m-1]<0，则F[m]=a[m]。求出所有F[m]中最大的一个就行了。

　　vector是如何实现的? 这个简单到爆了，我寥寥几句说完了。

　　C++里，虚函数是如何实现的? 我一听就明白想说的是vptr和vtable,直接说：如果一个对象含有一个以上虚函数，则它的对象中有一个vptr，指向该对象所属类型的虚拟函数地址表(vtable)，这样，就能根据一个对象的`实际类型来确定要执行的函数地址了。

　　C++里动态申请一个数组是用的int *p=new int[10]类型的方法，而销毁时，则是用delete [] p ，请问，delete时，没有指明销毁空间有多大，它是如何知道要delete的数组是多大的?如果你来设计C++,你会如何来实现? 这个我之前确实没思考过，我想了会儿，说可能是new时在前面多申请出几个字节，用来存该申请出区域的大小。这样，返回的p可能不是申请出的首地 址，delete时，用p往前几个字节，就能知道数组有多大了。后来网上查了查，似乎确实是用差不多的方法实现的。

　　给你一个随机数发生器，它有p的概率生成0，1-p的概率生成1，现在让你设计一个随机数发生器，有1/2的概率生成0，1/2的概率生成1. 这个想了好一会儿没想出来好方法。后来面试结束后，让大二大三的想，他们找到了个方法：用给出的随机发生器，随机生成两次数字，由于先1后0和先0后1的 概论是相同的，都是p(1-p)的概率，所以，如果先1后0，就输出1，如果先0后1，就输出0.如果同1或者同0，就重复试验，直接两次生成的数不相同 为止。

　　给你一棵树，并给你两个结点，如何求它们的最近公共祖先? 我一听最近公共祖先(LCA问题)，直接说能用tarjan算法来算，然后他又让我说明具体怎么算，我想了好一会儿才想清楚具体的过程。说完才意识到他现 在只是问求一次最近公共祖先如何求，我又说，如果只求一次的话只需要简单的一次搜索就可以了。。而求多次的话，每次都搜索太慢，可以用上面说的 tarjan算法或者用一次搜索先转化成+-1RMQ问题来求解。

　　请详细说明如何使用socket。 这个我以前我用C语言和C#都写过socket程序，所以对这个很是熟悉，又是直接说了一通。

　　TCP和UDP的区别是什么? 我说TCP是面向连接的，UDP是无连接的。

　　请详述TCP的三次握手的过程 这个我当时确实不会，就直接

　　关于虚拟内存管理，说说你的看法。 这个，我当时不太了解，不过猜测和cache管理比较类似，然后就按cache管理答了些东西，后来看看，大致还算比较靠谱。

　　你有什么问题想要问的没有? 这个说是问题也可以算是个问题吧，我就随便扯一点点，然后帮同学问问一个同学为什么还没接到电面通知，他说他会帮我问问的。

　　然后，面试完和面试官闲谈了谈，谈到我在大连理工参加的大连赛区的ACM比赛，面试官似乎之前在大连理工上过学，他说似乎大连赛区这个比赛的申办和他还有些关系…

　　二面： 先是在去往面试地点的路上，电梯里，聊了聊ACM相关的东西，他问我现在中国有几个赛区，我说五个，他说“现在这么多赛区啊”，看样子他以前也参加过 ACM。面试开始后，他最开始先是让我自己讲一下我写的OJ系统的工作原理，我扯了一堆linux系统调用之类的东西，然后，他似乎感觉不错，开始一直问 我算法方面的题目。 第一道题是让我在纸上写一个什么函数，现在忘记到底是啥函数了，反正不太难，不过在纸上写代码确实有些郁闷。 第二个题是给了一个链表结构，让我写个代码使这个链表中的相邻的元素两两进行交换，比如1 2 3 4 5 交换成2 1 4 3 5，最后剩余的元素不再交换。就这么个简单的程序，我竟然写了好一会儿，写错了n次才终于写对。当时感觉到自己真是弱爆了。 第三道题说的是有m个数，其中部分数能分到集合一里，部分数能分到集合二里，部分数可以分到集合一也可以分到集合二，现在给你集合一的容量和集合二的容 量，如何划分这些数(可以分到一个集合中或者不放入任何一个集合)，让两个集合中数的和最大。我刚开始把容量理解成是放进这个集合中的数的和不能超过这个 定值，当时想了一会儿没想好具体怎么去搞。后来他准备去引导我把这题搞出来，在他引导我的时候，我才明白原来他说的容量是指放入的数的个数，我立刻说这题 能用贪心算法来做，就是从大数到小数排序，用三个变量a,b,c分别表示集合一剩余容量，集合二剩余容量，和总剩余容量，然后从大到小对这些数一个一个进 行处理，如果待处理的数只能放到集合一中，则让集合一剩余容量减少，总剩余容量减少，如果只能放到集合二中，则让集合二剩余容量减少，总剩余容量减少，如 果既可放到一也可放到二，则只让总剩余容量减少。如果某个数只能放到集合一(或二)中，而集合一(或二)的剩余容量已为0，则该数不放入任一集合，当总剩 余容量为0时算法停止。 第四道题说的是连连看游戏，说是给你一个连连看的初始状态，现在让你判断某两个位置的物品是否能够消除。 我想了一会儿，说可以先横着枚举，从两个物品都往横方向发一条直线，枚举这两条直线上由该物品可直接到达的点，看看这两条直线上这些点有没有横坐标相同并 且中间没有阻挡直接到达的情况，如果有，则证明可以消去，如果没有则不可消去。但是我也知道这个方法似乎很慢。主要就慢在判断两个点是否没有阻挡直接可达 上。然后，我又说要不行的话先预处理存下所有的点之间的连通状态。他让我算一下空间复杂度，我一算，似乎需要的额外空间很大，然后我又想到可以利用存前n 项和的方法，也就是说，先把有物品的地方标记为1，没有物品的地方标记为0，利用部分和的方法求出每一列的前n项和存到一个对应的数组里，(同样也求出每 一行的前n项和存到另一数组里)，然后利用f[m-1]-f[n]就可以得到第n+1项到第m-1项的和，如果它们为0，则表明中间没有阻挡，如果不为 0，则表明有阻挡，则这里每次判断的复杂度从O(n)转化成了O(1)，然后面试官又说，你这样是可以很快了，但是，你消除元素之后，如何去更新你的数 组?我一想这样的话消除元素之后，更新数组又成O(n)的复杂度了。不过瞬间我就想起了这样求和并需要更新，明显插点问线型的树状数组可以搞，于是，我立 马说可以用树状数组进行插线问点。面试官愣了下，问我什么是树状数组。。我汗了一下，然后，意识到他搞竞赛时可能树状数组还不流行。。于是解释了一下原 理，然后说可以实现插点问线。然后面试官才说“哦，知道了，也就是说和线段树类似嘛”，我说“嗯，不过比线段树写起来简单多了”，然后面试官说好了，面试 结束了，问我有什么问题要问没有，我开始变聪明了，问了问面试结果什么时候出来，面试官直接说，“你二面已经通过了，不过今天有点晚了，不能直接三面了， 可能明天或者下周会安排你进行三面”，我又帮另一同学问了问内推的事，他说他也不清楚，于是二面就结束了。

　　三面： 面试官先让自我介绍，这个我还算有点准备，不过感觉面试官听得很不仔细，边看电脑边听的样子，于是，心里有些慌，感觉自己想说的面试官没听进去。。 不过，我还是把想说的都说了说，说了自己许多优点。然后面试官和我聊了会儿之后，开始问我题目，只问了一道题： 现在给你N个点，给你一个函数能算出任意两个点之间的距离，现在要把这N个点中距离最近的两个点合并成一个点(合并之后点的坐标也给你一个现成的函数能算 出来)，然后，继续这样操作，让你找一个方法，能尽可能高效的把这N个点合并成一个点。如果给你M台计算机，你该如何利用多台计算机加快这个过程。

　　这题不多说了，我当时答得沾了个边，但是答得不是很好，反正我说的是用极小堆和标记数组搞来搞，后来下来一想当时答得有些扯淡。现在想好了一个方法，不过 说起来比较难描述，不多说了。 他又问我能过去实习不，我想了想说应该可以吧。 他又问我有什么想问的或者想说的没有，我本来想给他说说OJ，后来发现他对OJ也很熟悉(估计又是一搞过ACM的)，然后我就没啥可说的了，然后我还和二 面时一样问什么时候能出结果，面试官又爽快地说我三面已经过了。

　　于是，就这样拿到了offer。