百度校园招聘PHP实习生笔试题及答案

1.给一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么b是a的兄弟单词，比如单词army和mary互为兄弟单词。现在要给出一种解决方案，对于用户输入的单词，根据给定的字典找出输入单词有哪些兄弟单词。请具体说明数据结构和查询流程，要求时间和空间效率尽可能地高。

解析：仔细研读本题，我们发现，所谓兄弟单词就是有相同的字母组成还是有不同的顺序的单词。因此我们可以对所有的单词做排序（根据字母表中的顺序对其排序），排序后的结果作为单词的唯一“签名”或者“标志”，例如单词army和单词mary的唯一签名就是“amry”.

如果本题目作为c/c++面试题。那么所用的数据结构可以是“hash_map + 单链表”（也可以是hash_map + 二维数组，有些浪费空间，或者是hash_map + list，容器套容器），具体的流程是：对于输入的单词列表，先计算单词的key(排序后的结果)如果key不再hash_map中，那么就将该单词加入hash_map中。hash——map的key就是单词的key,value是链表（或数组）。如果已经存在该key,那么单词加入value对应的单链表中。查询一个单词的所有兄弟单词的时候就可以简单滴查询hash_map，然后扫描相应的单链表即可。

另外，字典树对于求解字符串匹配，前缀，后缀等问题是一个利器。因而本题也可通过字典树求解。具体的解法可以参考：

http://blog.csdn.net/hackbuteer1/article/details/7542774

本题作为php面试。数据结构可以直接用数组（php中数组真是万能的数据结构，除了作为普通的数组，还可以做栈，做队列，做hash_map，实在是太强大了，囧）。

当然思路也是基于单词排序后的结果。给定一个单词列表如army,mary,map,pam.则生成的结果数组是这样的：

$array = array('amry' => array(’army’,’mary’),’amp’=>array(’map’,’pam’));

有了思路，代码就简单了：

<?php $dicts = array(’army’, ’mary’, ’are’, ’so’, ’os’, ’test’, ’how’, ’pam’, ’map’,);function getBrother($sea,$needle){//大海捞针 $brother = array(); foreach($sea as $word){$str_array = str_split($word);rsort($str_array);$res = implode(’’,$str_array);//if(!in_array($brother,$res)){ $brother[$res][] = $word;//} } $key_array = str_split($needle); rsort($key_array); $key = implode(’’,$key_array); if(isset($brother[$key])){return $brother[$key]; } return null;}print_r(getBrother($dicts,'map'));

该题目的c++解法可以参考：http://hi.baidu.com/nicker2010/item/295b0e090ac8ddebfe240d84

2.系统中维护了若干数据项，我们对数据项的分类可以分为三级，首先我们按照一级分类方法将数据项分为A、B、C……若干类别，每个一级分类方法产生的类别又可以按照二级分类方法分为a、b、c……若干子类别，同样，二级分类方法产生的类别又可以按照是三级分类方法分为i、ii、iii……若干子类别，每个三级分类方法产生的子类别中的数据项从1开始编号。我们需要对每个数据项输出日志，日志的形式是key_value对，写入日志的时候，用户提供三级类别名称、数据项编号和日志的key，共五个key值，例如，write_log（A,a,i,1,key1），获取日志的时候，用户提供三级类别名称、数据项编号，共四个key值，返回对应的所有的key_value对，例如get_log（A,a,i,1,key1），请描述一种数据结构来存储这些日志，并计算出写入日志和读出日志的时间复杂度。

解析：多级分类对应多级hash_map。

作为php面试。多维的map即为一个多维的数组。各维的含义依次是：一级，二级，三级分类，编号，key.

数据存储形式为：array('A' =>array('a'=>array('i'=>array(1=>array('key1'=>'value1','key2'=>’value2’))),'b'=>array));

查询的时候根据相应的编号和类别，key直接查询即可。时间复杂度可以达到O(1).(考虑，如果数据是海量的，应该如何存储？查询？)

相应的测试代码：

<?php class Dictory{private $dict = array( ’class_one_A’ => array(’class_two_a’=>array( ’class_three_i’=>array(1=>array( ’id’=>'test_id', ’name’=>’test’, ’date’=>’2012-07-12’,),2=>array( //..),3=>array( //..), ), ’class_three_ii’=>array( ), ), ’class_two_b’=>array( //... ), ), ’class_one_B’ => array(//... ),//...);public function __construct(){ //也可以在这里传入dict列表。}public function getItem($class_one,$class_two,$class_three,$num){ $class_one = ’class_one_’.$class_one; $class_two = ’class_two_’.$class_two; $class_three = ’class_three_’.$class_three; $num = intval($num); if(isset($this->dicts[$class_one][$class_two][$class_three][$num])){return $this->dicts[$class_one][$class_two][$class_three][$num]); } return null;}public function setItem($class_one,$class_two,$class_three,$num,$key,$value){ //设置相应的值} } $dict = new Dictory; echo '<pre>'; print_r($dict->getItem(’A’,’a’,’i’,1)); /* * Array * ( * [id] => test_id * [name] => test * [date] => 2012-07-12 * ) */

3.C和C++中如何动态分配和释放内存？他们的区别是什么？

(不明白为什么php的面试中还有c/c++的基础题。诡异的很，肯定是有人搞错了)

解析：c中的动态分配内存相关的函数是：malloc()和relloc().对应的释放空间的函数是free()

c++中动态分配内存相关的函数是：new().相应的释放空间的函数是delete（删除单个变量空间）和delete[](释放数组空间)

相应的区别有：

相同点：都可用于申请动态内存和释放内存不同点：(1)操作对象有所不同: malloc 与 free 是 C++/C 语言的标准库函数，new/delete 是 C++的运算符。对于非内部数据类的对象而言，光用 maloc/free 无法满足动态对象的要求。对象在创建的同时要自动执行构造函数， 对象消亡之前要自动执行析构函数。由于 malloc/free 是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加 malloc/free。(2)在用法上也有所不同:函数 malloc 的原型如下： void * malloc(size_t size); 用 malloc 申请一块长度为 length 的整数类型的内存，程序如下： int *p = (int *) malloc(sizeof(int) * length);我们应当把注意力集中在两个要素上：“类型转换”和“sizeof”。 malloc 返回值的类型是 void *，所以在调用 malloc 时要显式地进行类型转换，将 void * 转换成 所需要的指针类型。 malloc 函数本身并不识别要申请的内存是什么类型，它只关心内存的总字节数。函数 free 的原型如下： void free( void * memblock ); 为什么 free 函数不象 malloc 函数那样复杂呢？这是因为指针p的类型以及它所指的内存的容量事先都是知道的，语句 free(p)能正确地释放内存。如果 p 是 NULL 指针，那么 free对 p 无论操作多少次都不会出问题。如果p不是NULL 指针，那么 free对p连续操作两次就会导致程序运行错误。new/delete 的使用要点:运算符 new 使用起来要比函数 malloc 简单得多，例如： int *p1 = (int *)malloc(sizeof(int) * length); int *p2 = new int[length]; 这是因为new内置了sizeof、类型转换和类型安全检查功能。对于非内部数据类型的对象而言，new在创建动态对象的同时完成了初始化工作。如果对象有多个构造函数，那么 new 的语句也可以有多种形式。如果用 new 创建对象数组，那么只能使用对象的无参数构造函数。例如 Obj *objects = new Obj[100]; // 创建 100 个动态对象不能写成 Obj *objects = new Obj[100](1);// 创建 100 个动态对象的同时赋初值 1在用 delete 释放对象数组时，留意不要丢了符号‘[]’。例如 delete []objects; // 正确的用法delete objects; // 错误的用法 后者相当于 delete objects[0]，漏掉了另外 99 个对象。

4.数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注：al[i]元素是支持’<’运算符的。

解析：如果只有要求O(1),那么可以简单的插入排序（从mid开始）。

注意归并排序是不行的。归并排序的空间复杂度是O(n)。

题目也可以通过循环移位的方式进行“合并”。

具体的解法也可参考：http://blog.csdn.net/hackbuteer1/article/details/7542774（代码未经测试）

5.线程和进程的区别及联系？如何理解“线程安全”问题？

答案：进程和线程都是由操作系统所体会的程序运行的基本单元，系统利用该基本单元实现系统对应用的并发性。1)、简而言之,一个程序至少有一个进程,一个进程至少有一个线程.2)、进程是资源划分的最小单位，线程是任务划分的最小单位。3)、另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存（资源），从而极大地提高了程序的运行效率。4)、线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。5)、从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

由于多线程之间共享内存和其他资源，因而就有了一个新的概念：多线程安全。试想，如果多个线程共享同一段代码，那么同时运行的时候，如果没有相应的机制（例如锁机制），就会产生不确定的结果，这就是非线程安全的。因而线程安全就是指多线程之间同步运行的时候不会产生莫名其妙或者不确定的结果（由于多线程执行的顺序是不可见和不可预知的），或者，通俗点讲，多线程下的线程安全就是多个线程同步工作的情况下，运行的结果和单线程运行的情况下没有什么区别，大多数情况下，这就是线程安全的。

6.做一个系统来过滤垃圾信息，题目较长，用PHP来编写，要求消耗内存尽可能少。

解析：参考《集体智慧编程》[下载][购买]中文档分类一节。

1.网页爬虫在抓取网页时，从指定的URL站点入口开始爬取这个站点上的所有URL link，抓取到下一级link对应的页面后，同样对页面上的link进行抓取从而完成深度遍历。为简化问题，我们假设每个页面上至多只有一个link，如从www.baidu.com/a.html链接到www.baidu.com/b.html再链到www.baidu.com/x.html，当爬虫抓取到某个页面时，有可能再链回www.baidu.com/b.html，也有可能爬取到一个不带任何link的终极页面。当抓取到相同的URL或不包含任何link的终极页面时即完成爬取。爬虫在抓取到这些页面后建立一个单向链表，用来记录抓取到的页面，如：a.html->b.html->x.html…->NULL。问：对于爬虫分别从www.baidu.com/x1.html和www.baidu.com/x2.html两个入口开始获得两个单向链表，得到这两个单向链表后，如何判断他们是否抓取到了相同的URL？（假设页面URL上百亿，存储资源有限，无法用hash方法判断是否包含相同的URL）请先描述相应的算法，再给出相应的代码实现。（只需给出判断方法代码，无需爬虫代码）

解析：挖掘问题的本质，实质上是：给定两个单链表，判断两个单向链表是否相交的问题。至于如何判断两个单链表相交，网上答案很多。这里不再赘述（如判断两个单链表的最后一个指针是否相等，或转换为单链表是否有环的问题。 ）

2.有一种结构如下图所示，它由层的嵌套组成，一个父层中只能包含垂直方向上或者是水平方向上并列的层，例如，层1可以包含2、3、4三个垂直方向上的层，层2可以包含5和6两个水平方向的层，在空层中可以包含数据节点，所谓的空层是指不包含子层的层，每个空层可以包含若干个数据节点，也可以一个都不包含。

在这种结构上面，我们从垂直方向上划一条线，我们约定每一个子层中我们只能经过一个数据节点，在这种情况下，每条线可以经过多个数据节点，也可以不经过任何数据节点，例如，线1经过了3、5、8三个数据节点，线2只经过了14个数据节点。（1）给出函数，实现判断两个数据节点，是否可能同时被线划中，给出具体的代码。

（2）给出函数，输出所有一条线可以划中的数据节点序列，

思路：

（1）如果两个数据节点位于同一个最外层中，那么不能连接（我们约定每一个子层中我们只能经过一个数据节点），然后判断两个数所属的同一层次的相同矩形框的下一层次矩形框是水平排列的还是垂直排列的，垂直排列在能在一条线上，水平排列则不能。

（2）用回溯算法求出所有在一条直线上的字符串，用两字符串是否在同一直线上进行剪枝操作。（实际上类似于字符串的组合问题）。

1.相信大家都使用过百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何实现？请给出实现思路和主要的数据结构、算法。有什么优化思路可以使得时间和空间效率最高？

解析：常见的Ajax提示框的实现是基于字典树，根据前缀扫出相应的单词（热点词），最后根据top K算法求出前K个热点词。并展示给用户。

参考：http://www.wzsky.net/html/article/php/php2/115202.html

这里是用数据库保存数据，而查询的时候是通过数据库委托的like取相应的前缀查询，因而掩盖了很多数据结构和算法的细节。

实际应用中，每个热词可能还有相应的计数或者权重，根据权重选取相应的热词并取top K进行展示。

2.两个200G大小的文件A和B，AB文件里内容均为无序的一行一个正整数字（不超过2^63），请设计方案，输出两个文件中均出现过的数字，使用一台内存不超过16G、磁盘充足的机器。

又是海量数据的处理，大型互联网公司最爱做的面试无非就是这些个问题：top K，求相同，大文件统计ip，统计在线人数。为什么现在硬件大大发展的情况下我们还要谈海量数据处理，大概是因为：利用有限的资源处理更多的事情，本身就是一个很有挑战性的课题。而这些问题，最重要的是思路。关于海量数据的题目，强烈推荐july的这篇文章：

http://blog.csdn.net/v_july_v/article/details/7382693

相信你读完一定收获颇丰。

对于本题。由于两个文件的大小都大大超过了内存的限制。因而不能直接放入内存。可考虑对文件进行hash分为多个小文件（根据每一行的值）。hash的文件由于相同的key都存在一个文件中，因而只需要比较相同的文件中的数字。最后归并之，得到所有的A文件和B文件中相同的数字。