百度校园招聘面试成功分享.pdfVIP

百度2012校园招聘面试过程 一面： 给你一棵二叉树，如何判断它是否是完全二叉树？ 最开始我连完全 二叉树的定义都忘了，面试官提醒我之后我才明白是啥。。汗。我当 时回答的是先把它转化成数组的形式存储（就是2*n 存左孩子， 2*n+1存右孩子的存法 ，然后循环判断一下是不是所有的结点都是 在数组的前 m 个位置。 给你一个数组，求它的一个子串，使该子串的和最大。 这是典型的 最大子串和问题，我直接就说这是个经典的动态规划问题：令F 表示以第 m 个数为结尾的所有子串中和最大的子串的子串和。则若 F[m-1] 0,则 F F[m-1]+a ,若 F[m-1] 0，则 F a 。求出所有 F 中最大的一个就行了。 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 次才终于写对。当时 感觉到自