百度校园招聘面试成功分享.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 次才终于写对。当时 感觉到自