一、百度实习笔试题：

2011/5/7百度实习笔试题目（研发方向与测试的试卷相同）

*******************************************************************************

第一题，简答题：

1、 extern “c”{}是什么含义？用来解决什么问题？

2、 至少说出两种经典的设计模式，并举例说明使用场景，有伪代码更佳。

3、 Tcp连接的time-wait是什么状态，描述其发生的场景，说明它存在的好处/坏处 。

第二题 算法与程序设计题

1、 有一个任务执行器，每天定时执行N个任务(N<1000),每次只能执行一个任务，而各任务之间存在着依赖关系，如任务A需要依赖任务B任务完成后才能进行。虽然各个任务着依赖关系复杂，但任务之间没有循环依赖问题，请给出适当的任务执行顺序。

请详细描述你的算法思路，并给出时间和空间复杂度。

2、 编写函数：统计在某段英文文本完整句子的数目，文本只包括大小写英文字母，空格，点号，逗号，完整句子必须包含至少一个字母并以点号结束。

要求：完成代码，要尽量高效、简洁。

第三题 系统设计

某流量监控系统每天完成大量的数据记录，每条数据记录包括url，访问ip、时间，这些数据记录需要进行存储和维护，并提供查询。

请设计一个系统能够存储和维护1000亿条记录，实现实时监控，并能支持一下两种查询：

（1） 指定任意时间段（精确到分）和某个url，查出这个时间段内中对该url的总访问量。

（2） 指定任意时间段（精确到分）和某个ip，查出这个时间段内中对该ip的总访问量。

百度实习电面题：

百度一面（质量部，测试开发的）

首先是自我介绍，然后问得第一个问题是扑克牌A-K排序，用什么算法最快?（先说一个算法，俺说快速排序）

演示一下排序过程，时间复杂度是多少？如果里面有重复元素，稳不稳定？

如果希望在O(n)的时间内排序完，可不可以做到，用什么方法？

二个有序的文件如何合并成一个大的有序的文件？

内存分配有几种方法，它们之间有什么区别？

如果要用C语言打开一个3G的文件进行操作，可以直接打开吗？（俺答不能）

那最大能直接打开的文件的大小是多少？你用什么方法可以做到打开它？

用linux命令如何查看一个线程的状态？

如何测试你的实习项目（我以前做过的一个项目，是java写得一个航空订票系统）？

假设服务器上有一个web应用，如何保证它的安全性？

你性格有哪些方面适合做测试工作？

在项目当中，遇到问题的时候，比如出现了bug，你通常如何做？

PS:面试的时候，考细心，周全

百度二面：

首先就是对我的简历重点进行追问

然后是哈希表与二叉树的区别

然后问了一下搜索引擎的结构

最后问了1000万个文档里面，如何快速找出10个相似的文档。。

就几个问题，花了半个小时。

PS:俺发现，面试的时候考算法考得最多了，尤其是排序

百度喜欢问大数据量处理方面的问题

搜索引擎，俺在腾讯和百度都问到了，不知道是不是人品的原因。。

1000万个网页里面，如何快速找出10个相似的网页？1.从网页集合中抓取一些网页文档，手工建立一个训练文档集，里面是已经分类好的文档。具有相似内容的网页归为一类。从训练文档中提取对类别敏感的关键字n个，用这n个关键字衡量每一个文档，使之转化为向量。在剩下的文档中随机选择一个文档，计算其向量和每一个训练文档向量的距离，然后采用KNN分类算法进行相似文档归类。2.先建立两个倒排索引表，第一个是关键字（关键字是有较好的区分度的）对网页文档，第二个是网页文档对关键字。从网页集合中任选一个网页文档，先从第一个倒排索引表中取得它的关键字集合，然后用每一个关键字在第一个倒排表中检索文档，再针对每一个关键字检索出来的文档进行一个交，交之后剩下的文档即为该文档的相似文档。如果求交集之后的文档数量太少或者觉得太苛刻，可以放宽到只包含一部分关键字，而不需要包含所有的关键字。3.任选一个文档，再从网页集合中选择9个文档建立一个堆，堆中每个元素的权值为该文档与选定的文档的相似度（相似度的计算参考第一种方法或用其它的方法），依次遍历1000万个文档，计算它们与选定文档的相似度，如果小于堆中某一元素的相似度，则从堆中删除最大的元素，将该文档加入堆中，并重新调整一下堆。当遍历完网页集合中的所有文档之后，最终会剩下9个文档，然后这9个文档即为选定文档的最相似的9个文档。

*******************************************************************************

*******************************************************************************

*******************************************************************************

二、腾讯实习笔试题：(研发方向与测试的试卷相同)

1、 选择题：纯数学题（计算并行电路不出故障的概率）、MD5有多少位（128）、最小生成树、三个进程在cpu与I/O上执行时间

2、 最后一道程序题目：关于四则运算的一道C语言题，其中缺了几空。

3、 附加题：手机内存分配算法

现在有一个32位手机，能使用的最大内存空间是8M。地址是连续的，而程序的内存分配的请求要求的空间大小以及要求的频度如下：

设计一内存分配器，尽最大可能满足程序的内存要求，因为一旦内存分配失败，程序就必须退出。请设计一数据结构、设计数据、申请数据以及释放内存算法。同时估算设计的内存分配器的空间利用率以及说明为什么你的内存分配器能够保证更多的请求得到响应。

腾讯实习面试题()：

写一个二分查找的程序

然后自我介绍，之后针对简历上的项目重点问了一下

linux命令（创建目录、列出一个文件夹下的所有文件、获取一个文件的最近更新时间）

再然后问我有使用过哪些互联网产品（回答qq、百度、google）

百度的搜索原理是什么、如果是你设计百度，你觉得应该怎么设计？

后来我说我学过信息检索这门课，然后他又问你觉得信息检索与搜索有什么区别？

我说信息检索一般指得是规范化的内容，比如图书馆，一些人写得文章 面试官就问，如果一个作者写一本书，他怎么又会考虑不否会满足你的规定呢，又怎么样进行信息检索呢？

最后一个问题是10w进行比赛，两两淘汰制，总共要进行多少场比赛？

ps:说话太有漏洞了，结果被面试官抓住狂问一通

其它同学的面试：

（1）同学1

面试官看简历，问很多项目里面的问题

像数据库的索引怎么优化之类的

还有一些网络协议

问了下linux下的核心编程的问题

最后问了几个数据结构里面的排序和查找算法（没让写，说思路）

（2）同学2

数据库怎么查询优化？

网上搜索到的答案：

1数据库设计方面：a建立索引 b分区（MySQL，按时间分区） c尽量使用固定长度字段 d限制字段长度

2数据库I/O方面：a增加缓冲区 b如果涉及表的级联，不同的表存储在不同的磁盘上，以增加I/O速度

3在SQL语句方面：a优化SQL语句，减少比较次数 b限制返回的条目数（MySQL中用limit）

写一个关于服务端与客户端的通信程序

好像也是个二叉树查找算法，记不太清了

（3）同学3

文本文件和二进制文件的区别

怎么打开这两种文件

以及堆和栈的区别

如何创建线程，有几种方法？

C++中的模板，用一句话描述

怎么求两个数组的交集（散列，面试官给的答案）

（4）群里其它同学的、

问了stl，堆栈溢出，内存处理。

字符串集合，根据字符的首尾字符，判断该字符串集合是否能形成一个环

C++各种不知名关键字 explicit mutabale volatile…… STL中vector除非作用域结束否则不释放内存咋整 多态、虚函数表的内存结构及具体实现机制 仿函数 被无视之后各种开发性智力问题接着被无视了

董老师的人狼羊白菜问题

STL中vector除非作用域结束否则不释放内存咋整

（

群里如是说：

譬如vector a很大很大了 …………｛ 建一个空的vector b 采用swap函数交换 a.swap(b)｝括号内的就变大了 到出大括号 系统就析构了。

百度腾讯实习笔试面试题