百度公司2012校园招聘研发测试笔试题总结：
1. 用ssh登陆远程linux/unix系统，当网络中断时，终端程序也会随之而中端，请问这是什么原理？有什么解决方案可以避免这种缺陷？
2. 一个最小堆是一棵完全二叉树，最小堆存在一个数组中
（1）任意一个a[n]，写出其左、右子节点的访问方式
（2）完成函数void add_element(int *a, int size,int val)，功能是将一个元素val插入到最小堆a的数组中，并且保持最小堆的性质
（3）输出最小堆中的最小值，并重新调整堆使其保持最小堆的性质
3. 给定某个hash函数，其可以将某个空间均匀分布到另一个空间,空间的大小为100%，最小分布粒度为0.1%，现有两个空间A和B，请问如何将A的任意子空间均匀分布到B的空间,（例，将A的10%的子空间均匀分布到B，使得每个B的10%空间都均匀的拥有A的10%的子空间的1%）？当有超过10层空间时，每层空间都存在这种关系，请问如何解决？
4. 给定一个编码，通过一个算法将其转为另一个编码,使得转换后的编码和以前的编码长度一样并且转换后的编码是比原来编码的大的数中的最小值，例如编码134 转换后的编码是143,020转换后的编码是102，设F(N)=M ,N代表要转换的编码，N的数字位数最多为1000，大小最多为10^500,M表示转换后的编码(编码可以是0),可能给定某个N时，不存在M，使得F(N)=M,此时，返回-1，定义序列S(N)={S(0)=N,S(1)=F(N),S(2)=F(S(1)),…,},请实现求序列S(N)的函数
5. 请设计下面的算法（可以用伪代码）
（1）请设计算法，求某个数组元素的全排列
A=[1,2,3]
Permutation(A)={[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]};
（2）请设计算法，求某个数组元素的所有组合
A=[1,2]
Combination(A)={空,[1],[2],[1,2]};
6. 请设计一个磁盘数据查询系统,其中数据格式定义如下：
其中，每条查询记录都以TermID,urlCount,urlNO[urlCount]，其中urlNO的大小不定，但是平均长度为10万条，查询操作有如下三种：
| TermID1[uint_64] | urlCount[uint_32] | urlNO1 | … | urlNON |
| TermID1[uint_64] | urlCount[uint_32] | urlNO1 | … | urlNON |
| | | | | |
| | | | | |
TermID1 AND TermID2,返回TermID1以及TermID2中urlNO的交集
TermID1 OR TermID2, 返回TermID1以及TermID2中urlNO的并集
TermID1 SUB TermID2，返回TermID1减去TermID2的urlNO集合
(1) 请设计数据存储格式, 尽可能的考虑查询效率，可以适当资源利用
(2) 设计多线程的查询模型
(3.1)设计一个支持括号操作的查询算法, TermID1 OR (TermID2 AND TermID3) SUB TermID4
(3.2)设计截断优化，当返回前100个urlNO时，设计策略，停止查询。
一、简答
1、C++STL中Vector相关问题
（1）调用成员函数push_back，其内部内存分配如何进行。
（2）调用成员函数clear时，内部如何具体实现，若想将其内存释放，该如何操作。
2、指出C语言foo函数的问题，此函数想统计字符串中的字母a~z分别出现的个数。void foo(char a[100],int cnt[256]){ memset(cnt,0,izeof(cnt)); while(*a !='\0'){ ++cnt[*a]; ++a; } for(char c='a';c<='z';++c){ printf("%c:%d\n",c,cnt[c]); } }int main(){ char a[100]="百度abc" int cnt[256]; foo(a,cnt); return 0;}二、算法与程序设计1、设有rand(s,t)函数，可返回(s,t)间的随机小数，如何利用该函数在一个半径为R的圆内随机找n个点，并给出相应的时间复杂度的分析。2、为了分析用户行为，系统往往需存储用户的一些query。但是因为query非常多，所以系统不能存下每一条。设系统每天只能存储m个query，现需设计一个算法，对用户时时请求的query进行随机选择n个，给出一个方案使得每一个query被抽中的概率尽量相等，也请附加相应分析，请注意，不到最后一刻，你并不知道用户的总请求量是多少。三、系统设计题 现有一个“服务器—客户端”的实际系统，正常客户端每一分钟最多发送一条请求到服务器，服务器需要做一个异常客户端行为的过滤系统。设服务器在某一时刻收到A的一条请求，那么一分钟内的客户端的任何其他请求都要被过滤，现知每一个客户端都有一个IPV6地址可以作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需要设计一套系统，使得支持高效过滤，可以使用多台机器，但要求使用机器越少越好，请把关键设计和思想用图表和代码方式表现出来。参加了今天的百度笔试，测试滴，我回忆了一下试题，下面有的表达的欠准确（只能记得这么多了），参加过的可以补充一下，大家探讨探讨呗，攒RP~嘿嘿
第一大题：1.extern "C"{}含义，应用在什么场景下?
2.经典设计模式写出至少两个，解释一下，最好写出伪代码
3.TCP连接中的wait_time含义，应用场景，好处和坏处
第二大题
1.一个任务处理器吧，N个任务，任务之间会有依赖关系。比如A依赖B，A需要B完成之后才能开始，写出算法，找到合适的任务顺序。说明算法的时间复杂度和空间复杂度。
2.一个英文文本，含有字母，“." 和","和空格。写出函数，这个函数用于找出英文文本中含有的完整句子的个数。含有至少一个字母并且以句号"."结尾的视为一个完整的句子。写出完整的代码。
第三大题：系统设计题
1.实时监控系统。有很多记录，记录中含有url,时间段，ip
该系统可以同时实现如下两个查询
查询一：已知时间段（精确到分钟）和某个url，求满足条件的总流量
查询二：已知时间段（精确到分钟）和某个ip,求满足条件的总流量
1、 简答题。 请说出树的深度优先、广度优先遍历算法，及非递归实现的特点。
2、 找错
struct complex_t
{
int real;
int imag;
}
int create(complex_t*p,unsigned int n)
{
p=new complex_t[n];
if(p==NULL){
return -1;
}
return 0;
}
int compute()
{
//implement
complex_t*comps;
unsigned int num=0;
cin>>num;
if(create(comps,num)=0){
cerr<<”create comps failes!”<
return n-1;
}
long long int sum=0;
unsigned int pos=0;
cin>>pos;
while(pos<
cin>>comps[pos].real>>comps[pos].imag;
sum+=comps[pos].real*comps[pos+1].real+comps[pos].imag*comps[pos+1].imag;
pos+=2;
}
cout<<”sum is”<
return 0;
}
第二部分 程序与算法
1、 一个典型的大型项目，通常由众多组件构成，这些组件之间复杂的编译依赖于在构建整个系统时，是最让人头疼的地方之一。现在就有这样的一个大型项目，由N（N>1000）个组件构成，每个组件都是可以编译的，但组件之间存在着编译依赖，如组件N1依赖N2，即编译N1时N2必须已经先编译完成，否则N1不能完成编译，但组件之间没有循环依赖的问题。请设计一种快速算法，能完成整个项目的编译构建过程，并给出算法的时间复杂度。
2、 实现一个函数的完整代码。
int maxContinuNum(const char*inputstr.char*outputstr)
功能：
在以'\0’结尾的字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。不能用strlen之类的库函数。
第一大题，简答题
1.extern “c”{}什么时候用，有什么作用
2.说出两种经典的设计模式，举例说明使用场景，最好写出伪代码
3.TCP 下time_wait 描述其发生的场景，说明它存在的好处/坏处
第二题 算法与程序设计题
1、 有一个任务执行器，每天定时执行N个任务(N<1000),每次只能执行一个任务，而各任务之间存在着依赖关系，如任务A需要依赖任务B任务完成后才能进行。虽然各个任务着依赖关系复杂，但任务之间没有循环依赖问题，请给出适当的任务执行顺序。
请详细描述你的算法思路，并给出时间和空间复杂度。
2、 编写函数：统计在某段英文文本完整句子的数目，文本只包括大小写英文字母，空格，点号，逗号，完整句子必须包含至少一个字母并以点号结束。
要求：完成代码，要尽量高效、简洁。
第三大题系统设计
1． 设计一个系统，存放URL,IP,访问时间。数据量达到1000亿条记录。要求：
1）指定访问时间段，对于给定的URL，统计该URL访问量。
2）指定访问时间段，对于给定的IP，统计该IP的访问量。
请牛人给出自己的答案，看看你能做多少，我貌似会的不多，是从一个师兄那里搞过来的题！
周一，川大场：
1.编程题：
两个字符串a和b，a和b中都含有汉字，判断两字符串是否匹配。匹配的条件是：b中的汉字出现的次数不少于在a中出现的次数，b中的字符在a中都有出现。并分析时间和空间的复杂度。（这个题和百度06年的一道题目有些相似）
2.算法题：
已知一个序列seq=[a,b,....,z,aa,ab,...,zz,aaa,aab,....],求任意一个字符串s=[a-z]+在seq中出现的位置。
3.系统设计题：
现在要设计一个评分系统，用户在搜索完毕后对这次搜索结果进行评分，然后搜索结果将按照评分高低进行排序，为避免用户恶意的评分、点击请问如何设计这个评分系统。
周三，科大场：
1.编程题:
有一组N个固定的集合（N为万量级），在每个集合中有0-ID个编号为id的集合，每个集合中有1-M个temp数组（M为1-100）。现在输入temp输出集合的id，条件是这一组temp包含集合id中所有的temp数组，如果没有输出-1.
例如输入：
temp1空格temp2
temp1空格temp3
temp2空格temp3 temp4
注：a.temp中有汉字出现
b.可以用代码或者伪代码实现
c.分析该算法的时间和空间复杂度
2.算法题：
已知一个文件中有N条无序的条目，T1,T2,...,TN，现在可以找到一个整数M使得T1<T2<...<TM和TM+1<TM+2<....<TN.
（1）写出一个算法，使得T1'<T2'<...<TN'，其中读写文件的时间复杂度为O(n),内存不限。
（2）写出一个算法，使得T1'<T2'<...<TN'，其中读写文件的时间复杂度为O(n),空间复杂度为O(1)。
3.系统设计题：
完成一个搜索需要三个文件：from_url（读取url信息），to_url（连接url信息），anchor（存放页面信息）。
现在要设计一个系统使(from_url/to_url/anchor)存放的N个巨型的数据库中（N<100），满足一下条件：
a.存放相同to_url的页面存放在同一个数据库中
b.相同的to_url存放在同一个数据库中
c.每个数据库存放的信息均匀
d.检索每条信息用的时间差不多
e...不记得了
虽然大部分不会做但还是把题大概抄了下来，不是很完整，仅供借鉴。
一。简答
1.extern“c”{是什么含义，有什么作用
2.写出至少两种经典设计模式，最好写伪代码
3.TCP中time_wait什么含义，在什么情境下发生，以及它的好处和坏处
二。编程
1.一个服务器每天定时执行一定任务（N<1000），各任务间有一定依赖，如执行任务A需要先执行任务B，但无死循环。请设计适当的任务执行顺序。写出算法过程，分析时间空间复杂度。
2.统计一个英文文本中的句子数，文本中含有大小写字母、空格、点号（.）、逗号（，），一个句子的结尾必须是一个字母加点好。给出详细代码。
三。设计题
服务器记录url、访问ip、访问时间，服务器有100亿条记录，设计一个系统：
1.当知道访问时间（精确到分钟）和ip，可以统计url的总访问量
2.当知道访问时间（精确到分钟）和url，可以统计ip的总访问量
第一题;简答题
1.extern "C"{}的含义是什么，能解决什么问题?
2.写出至少两种经典的设计模式，阐明其使用场景，有伪代码更好。
3.TCP连接中time_wait状态是什么意思?说明其使用的场景，并指出它的好处和坏处分别是什么?
第二题：算法分析和设计题
1.有个任务定时器，每天要定时执行N个任务(N < 1000)，其中有些任务的执行依赖于其他任务的执行，如A任务执行之后B任务才能执行，但这些任务之间不存在循环依赖。请用算法来说明任务的执行顺序，有伪代码更好。
2.编程求某一个英文文本中完整句子的数目，文本中只包含大小写字母、空格、“，”和“.”，完整的句子是指以“.”结束，且“.”号前必须出现至少一个字母。
第三题：系统设计题
设计一个系统，该系统记录用户的访问记录。每条记录包含访问的url、访问ip以及访问时间，系统每天至少要记录1000亿条记录，系统要对这些数据进行存储和维护，并提供实时的查询，至少满足下面两个查询：
1.给定任意一个时间段(精确到分)和URL，计算该时间段内访问这个url的访问量;
2.给定任意一个时间段(精确到分)和IP，计算该时间段内访问这个IP的访问量。
下面的试卷一和二分别是两次参加笔试的题目
试卷一：
一、 选择排序：
数比较少
数比较密集
数基本有序时
关注最差时
体现平均性能时
二、 分析程序功能以及指出逻辑错误
三、 一个入口，一个出口。插入节点使路径相同。
四、 大于6的偶数都可以分为两个素数之和
输出6~100000只间能表示两个素数之和的
只输出一种情况就ok
五、key value 每条记录为1024字节， 内存10G ，磁盘不限。设计查询存储结构。
试卷二：
1.写出你知道的5种排序算法的平均时间复杂度
2.有一个链表类似于78912345，是从第四个位置1开始递增有序，问怎么实现查找。
3.求出只包含质因数2,3,5的数据，例如2 3 5 8 9 12 15等，输出前N项（N>10000）
4.有一个key值和value值对应，请编写一个检索系统，实现单线程修改，多线程查询。
下面的试卷一和二分别是两次参加笔试的题目
试卷一：
一、 选择排序：
数比较少
数比较密集
数基本有序时
关注最差时
体现平均性能时
二、 分析程序功能以及指出逻辑错误
三、 一个入口，一个出口。插入节点使路径相同。
四、 大于6的偶数都可以分为两个素数之和
输出6~100000只间能表示两个素数之和的
只输出一种情况就ok
五、key value 每条记录为1024字节， 内存10G ，磁盘不限。设计查询存储结构。
试卷二：
1.写出你知道的5种排序算法的平均时间复杂度
2.有一个链表类似于78912345，是从第四个位置1开始递增有序，问怎么实现查找。
3.求出只包含质因数2,3,5的数据，例如2 3 5 8 9 12 15等，输出前N项（N>10000）
4.有一个key值和value值对应，请编写一个检索系统，实现单线程修改，多线程查询。
百度公司2012校园招聘研发测试笔试题总结：
1. 用ssh登陆远程linux/unix系统，当网络中断时，终端程序也会随之而中端，请问这是什么原理？有什么解决方案可以避免这种缺陷？
2. 一个最小堆是一棵完全二叉树，最小堆存在一个数组中
（1）任意一个a[n]，写出其左、右子节点的访问方式
（2）完成函数void add_element(int *a, int size,int val)，功能是将一个元素val插入到最小堆a的数组中，并且保持最小堆的性质
（3）输出最小堆中的最小值，并重新调整堆使其保持最小堆的性质
3. 给定某个hash函数，其可以将某个空间均匀分布到另一个空间,空间的大小为100%，最小分布粒度为0.1%，现有两个空间A和B，请问如何将A的任意子空间均匀分布到B的空间,（例，将A的10%的子空间均匀分布到B，使得每个B的10%空间都均匀的拥有A的10%的子空间的1%）？当有超过10层空间时，每层空间都存在这种关系，请问如何解决？
4. 给定一个编码，通过一个算法将其转为另一个编码,使得转换后的编码和以前的编码长度一样并且转换后的编码是比原来编码的大的数中的最小值，例如编码134 转换后的编码是143,020转换后的编码是102，设F(N)=M ,N代表要转换的编码，N的数字位数最多为1000，大小最多为10^500,M表示转换后的编码(编码可以是0),可能给定某个N时，不存在M，使得F(N)=M,此时，返回-1，定义序列S(N)={S(0)=N,S(1)=F(N),S(2)=F(S(1)),…,},请实现求序列S(N)的函数
5. 请设计下面的算法（可以用伪代码）
（1）请设计算法，求某个数组元素的全排列
A=[1,2,3]
Permutation(A)={[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]};
（2）请设计算法，求某个数组元素的所有组合
A=[1,2]
Combination(A)={空,[1],[2],[1,2]};
6. 请设计一个磁盘数据查询系统,其中数据格式定义如下：
其中，每条查询记录都以TermID,urlCount,urlNO[urlCount]，其中urlNO的大小不定，但是平均长度为10万条，查询操作有如下三种：
| TermID1[uint_64] | urlCount[uint_32] | urlNO1 | … | urlNON |
| TermID1[uint_64] | urlCount[uint_32] | urlNO1 | … | urlNON |
|
|
|
|
|
|
|
|
|
|
TermID1 AND TermID2,返回TermID1以及TermID2中urlNO的交集
TermID1 OR TermID2, 返回TermID1以及TermID2中urlNO的并集
TermID1 SUB TermID2，返回TermID1减去TermID2的urlNO集合
(1) 请设计数据存储格式, 尽可能的考虑查询效率，可以适当资源利用
(2) 设计多线程的查询模型
(3.1)设计一个支持括号操作的查询算法, TermID1 OR (TermID2 AND TermID3) SUB TermID4
(3.2)设计截断优化，当返回前100个urlNO时，设计策略，停止查询。
以上就是
不定项选择题
1、线程与进程比较而言，下面论述成立的有（）
A 一个线程可以有多个进程组成
B 一个进程可以有多个线程组成
C 相对而言，线程运行需要更多的资源
D 线程比进程运行需要更少的系统资源
2、13*16=244在使用_______进制时成立（）
A 6
B 11
C 9
D 7
E 8
3、以下的C程序代码片段运行后c和d的值分别是多少（）
int a=1,b=2;
int c,d;
c=(a&b)&&a;
d=(a&&b)&a;
A 0，0
B 0，1
C 1，0
D 1，1
4、假设局域网中子网掩码是255.255.0.0，那么在这个局域网中哪些IP地址是可用的？（）A 192.168.0.0
B 192.168.0.1
C 192.168.255.1
D 192.168.255.255
5、给定数列（541，132，982，746，518，181，946，314，205，827）按照从小到大的顺序排列，采用冒泡排序时，第一趟扫描结果是（）；采用直接选择大值开始排序时，第一趟扫描结果是（）；采用快速排序（以中间元素518为基准）的第一趟扫描结果是（）。
A (541，132，827，746，518，181，946，314，205，984)
B (205，132，314，181，518，746，946，984，541，827)
C (132，541，746，984，181，518，314，946，205，827)
6、有若干5g和7g的砝码，任何大于（）克都能够用5g和7g的砝码组合出。
A 35
B 23
C 12
D 53
7、93486781634*22349659874=___________6（30秒）
8、在Linux系统中，对命令“ln file1 file2”描述正确的是？（）
A 建立软链接file1，并指向file2
B 建立硬链接file1，并指向file2
C 建立软链接file2，并指向file1
D 建立硬链接file2，并指向file1
9、在Shell编程中，下面哪个表示上一步所运行程序的返回值？（）
A $#
B $?
C $&
D $!
编程和测试设计题（2道）
题目一
简述：
实现一个函数，对一个正整数n，算得到1需要的最少操作次数：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
例子：
ret=func(7);
ret=4，可以证明最少需要4次运算
n=7
n--6
n/2 3
n/2 2
n++1
要求：
实现函数（实现尽可能高效）int func(unsign int n)；n为输入，返回最小的运算次数。
给出思路（文字描述），完成代码，并分析你算法的时间复杂度。
请列举测试方法和思路。
题目二 IP防火墙
简述：
Security公司的网络管理工程师Mr.leak最近发现有不少来自公司外部IP的请求，试图非法访问公司内部资源，为了不影响数据访问流程。他不得不写一个高效的程序——一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT来配置授权的IP地址，文件格式为每行（'\n'）一个IP地址（或IP段），范围不超过一个B类。
例如：
162.105.91.163
59.66.105.0 59.66.105.255
211.71.0.0 211.71.255.255
限制：
IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：
请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y，否则打印N。如果输入为一个空行，程序结束。
请给出思路（文字描述），完成代码，分析你采用算法的优劣。
请列举测试方法和思路
设计思考题（2道，请选做一道）
题目一
设计一个简单的网页抓取系统，目标是抓取z.baidu.com站点上的有价值网页。
请设计基本模型，并做出简要说明。
请考虑如何获取网页、如何存储网页、如何判断网页的价值……
实际应用中，需要考虑哪些因素。
题目二
简述：
某广告投放系统采用B/S结构，其主要用户为广告主，广告主可通过该广告投放系统在各个网站上投放广告并查看投放效果。该广告系统需要实现如下功能：
用户可向自己账户中加款。
用户可提交广告，广告包括四种形式：文字广告，图片广告，flash广告和对媒体广告。
用户可制定哪些广告在哪些网站上展现，用户可分别广告在制定网站上的点击单价
广告被点击时，直接从用户账户中扣除相应的钱款
用户账户余额不足时，所有广告失效，用户加款后，恢复生效。
用户可查询广告的每日消费情况（点击次数、消费额）、广告在各个网站的消费情况。
要求：
1 设计该系统的数据表结构，要求满足上述功能，结构清晰，并尽可能灵活。
2 写出功能6所涉及的SQL语句。
3 请分析随着广告主的增加、广告点击次数的增长，系统可能会在哪些方面出项性能瓶颈？你在设计时是如何考虑解决这些瓶颈的?潜在的性能瓶颈还有哪些？
实现一个函数，对于正整数n，算出得到1需要的最少操作次数：
如果n是偶数，将其除以2；如果n是奇数，可以加1或减1；一直处理下去，直到得到1。
示例：
ret=func(7);
ret=4，可以证明最少需要4次操作。
n=7;
n-1=6;
n/2=3;
n-1=2;
n/2=1;
要求：
实现函数（实现尽可能高效）int func(unsigned int n)；n是输入，返回最小的操作次数。给出思路（文字描述）并完成代码，然后分析算法的时间复杂度。
分析：
从数的二进制表示来看，偶数的最后一位为0，而奇数为1。如4d＝100b，而3d＝11b。除2操作与二进制的右移一位操作等价，故对偶数来说，右移一位即可；而奇数则需加1（或减1）。
在最好的情况下，数n的最低位为1，其它位均为0,如10000b，这样的数右移log2n位即可变为1，这样消去除最高位外的其它位的平均代价为1。接着考虑最低位为1的情况，由于不清楚是需加1还是减1，我们来看次低位（倒数第2位）。如果次低位为1，如11011b，则若加1一共需3次能消去后两位，平均每位代价为1.5；若减1，则共需四次才能消去后两位，平均每位代价为2，故选择加1。如果次低位为0，则直接减1，消去后两位的代价为3，平均每位代价为1.5。任何二进制数均可分段为若干个2位和0或1个1位组成，因此消去每位的最高代价为1.5，消去所有位的代价为1.5log2n；如果考虑到后两位消去时向前面的进位，则消去所有位的代价最多为1.5log2n+1。综上，算法的时间复杂度为O(log2n)。
对于数3d＝11b，其若加1后需3次才能变为1，而减1可以后需2次。故对3d特殊考虑。
实现：
int func(unsigned int n)
{
int count = 0;
while (n != 1)
{
if ((n & 0x1) == 0)
{
n >>= 1;
}
else if ((n & 0x2) == 0)
{
--n;
}
else if (n != 3)
{
++n;
}
else
{
--n;
}
++count;
}
return count;
}
|
