百度校园招聘历年笔试题.pdf

该【百度校园招聘历年笔试题 】是由【惜春文档】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【百度校园招聘历年笔试题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
百度笔试题
一、编程题(30分)
输入:N(整数)
输入:,不超过6条记录,字符串长度不超过15个字节
文件格式如下:
字符串\t数字\n
说明:
每行为1条记录;字符串中不含有\t。
数字描述的是该字符串的出现概率,小于等于100的整数。
多条记录的出现概率之和为100,,程序则退出;
如果文件格式错误,程序也退出。
要求:
编写一个程序,输入为N(正整数),,按照字符串出现概率随机
地输出字符串,输出N条记录
例如:

abc\t20
a\t30
de\t50
输入为:10
即abc有20%的概率输出,a有30%的概率输出,de有50%的概率输出,输出10条记
录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de
二、算法题(35分)
题目描述:
设有n个正整数,将它们联接成一排,组成一个最小的多位整数。
程序输入:n个数
程序输出:联接成的多位数
例如:
n=2时,2个整数32,321连接成的最小整数为:32132,
n=4时,4个整数55,31,312,33联接成的最小整数为:312313355:.
[题目要求]
,请给出对应的文字说明,并使用上面给出的例子试验你的算
法。
。
。(非常重要)
三、系统设计题(35分)
在一个有1000万用户的系统中,设计一个推送(feed)系统。以下是一些预定义概念:
1、用户:在这个系统中,每个用户用一个递增的unsignedint来表示userid(简写为uid);则uid的范围是从1到
1000万的正整数。
2、好友:用户之间可以形成好友关系,好友是双向的;比如说uid为3和uid为4的两个用户可以互为好友。每个用
户好友的上限是500个;用户之间的好友关系可以被解除
3、活动:每个用户只能发文章;文章可以被作者删除,其他人不能删除非自己发表的文章;每篇文章通过一个blogid
表示。
4、feed:我们希望,每个用户可以看到他所有好友的活动列表,在这个简化的系统中就是所有好友的文章更新列表。
5、访问量要求:所有feed访问量每天在1亿量级;所有的blogid增加量每天在百万量级。
题目:请在以上限制条件下,设计一个高效的feed访问系统。
要求:
1、能够尽快的返回每个用户的好友feed列表,每个用户可以最多保留1000条feed;feed的展现按照时间倒排序,
最新的在最前面
2、用户删除某篇文章后,被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的
3、尽可能高效
2010百度校园招聘笔试题
一、简答题
;
:
#include<>
#include<>
structRecord{
inta;
intb;
};
intcreate(structRecord*p,intnum)
{
p=newstructRecord[num];
if(!p)
return-1;
else
return0;
}
intTest()
{
structRecord*p=NULL;
inti;
intnum;:.
printf("0x%08x\n",p);
scanf("Inputrecordnum:%d",&num);
if(create(p,num)<0)
return-1;
printf("0x%08x\n",p);
for(i=0;i<num;i++){
p[i].a=0;
p[i].b=0;
}
return0;
}
intmain(void)
{
Test();
getchar();
return0;
}
#include<>
#include<>
structRecord
{
inta;
intb;
};
intcreate(structRecord*&p,intnum)
{
p=NULL;
p=newstructRecord[num];
if(!p)
return-1;
else
return0;
}
intTest()
{
structRecord*p=NULL;
inti;
intnum;
printf("0x%08x\n",p);
printf("Inputrecordnum:");scanf("%d",&num);
if(create(p,num)<0)
return-1;
printf("0x%08x\n",p);
for(i=0;i<num;i++){:.
p[i].a=0;
p[i].b=0;
}
delete[]p;
return0;
}
intmain(void)
{
Test();
getchar();
return0;
}
,内存大小为1K,CPU主频为1M(CPU状态每秒改变10的6次方次),问在这台计算机上可运
行并且确定可以终止的程序的最长运行时间是多少?
给出思路及推理过程(可以做任何假设)。
二、算法设计
,N2……Nn构成,每个组件都可以独立编译,但是某些组件的编译依赖于其它组件(即
某些组件只能在其它组件编译完成后才能编译),设计算法给出统计过程。
#include<iostream>
#defineMAXN505
#defineMAXMMAXN*MAXN
structedge
{
intv;
edge*mNext;
};
intin[MAXN];
intn,m;
edgeE[MAXM];
inten;
edge*first[MAXN];
intcnt[MAXN][MAXN];
voidinsert(intu,intv)
{
E[en].v=v;
E[en].mNext=first[u];
first[u]=&E[en++];
}
voidtopo()
{
for(inti=1;i<=n;i++)
for(intu=1;u<=n;u++)
{:.
if(in[u]==0)
{
in[u]=-1;
printf("%d",u);
for(edge*e=first[u];e;e=e->mNext)
in[e->v]--;
break;
}
}
}
intmain()
{
freopen("c:/","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(first,NULL,sizeof(first));
memset(cnt,0,sizeof(cnt));
memset(in,0,sizeof(in));
intu,v;
en=0;
for(inti=0;i<m;i++)
{
scanf("%d%d",&u,&v);
if(cnt[u][v]==0)
{
cnt[u][v]=1;
insert(u,v);
in[v]++;
}
}
topo();
printf("\n");
}
return0;
}
:
intmaxnumstr(char*inputstr,char*outputstr)
函数功能:找出inputstr中的最长连续数字串存储到outputstr里并返回长度,如调用maxnumstr("123abc1234a",
outputstr)后返回4且outputstr中为"1234"。
#include<iostream>
#defineMAXN1000
intmaxnumstr(char*inputstr,char*outputstr)
{
if(inputstr==NULL||outputstr==NULL)
throw"ErrorNULLparams";
if(*inputstr=='\0')
{:.
*outputstr='\0';
return0;
}
char*begin=inputstr;
intres=1;
intcur=1;
charpre=*inputstr++;
while(*inputstr)
{
if('0'<=*inputstr&&*inputstr<='9'&&pre==*inputstr-1)
cur++;
else
cur=1;
if(res<cur)
{
res=cur;
begin=inputstr-(cur-1);
}
pre=*inputstr++;
}
for(inti=0;i<res;i++)
outputstr[i]=begin[i];
outputstr[res]='\0';
returnres;
}
intmain()
{
freopen("c:/","r",stdin);
charsrc[MAXN],tar[MAXN];
while(scanf("%s",src)!=EOF)
{
printf("%d",maxnumstr(src,NULL));
printf("%s\n",tar);
}
return0;
}
三、系统设计
URL(统一资源定位符)由site、path组成,并且有其它属性信息如访问时间等。
如:://,path为/img/abc。
;
、删除及修改;
;
百度2011校园招聘笔试题
:.
一、简答
、B(0<A,B<100000),求A^B中最后三位数是多少。请简要描述你的思路。(这题我用方法比较笨,应
该是做错了,唉)
答:定义A,B为unsignedint,共4个字节,(A&1)^(B&1)剩下两位分别与2和4
,然后有四个小问题,代码和题都很简单基础。
a)C程序中的存储区分哪几个部分?
常量存储区(如常量)、全局存储区(静态变量、全局变量)、代码区、堆、栈
b)指出程序中几个变量所在的存储区。
c)使用new分配的内存如果分配失败会如何?
分配失败以后将会返回一个空指针
d)关于new/delete和malloc/free的区别。
要点:调用new时有三步:分配空间、调构造函数、返回指针,而malloc不调用构造函数;delete与free类似
,如果括号有多种,怎么做?如(([]))正确,[[(()错误。
首先需要确定的一点是这个括号字符串中不能包含除括号以外的其它字符。
思路:用一个map<char,char>来存放各种可能的括号对,如<],[>,<),(>,<},{>,然后用一个栈来模拟整个字符
串匹配过程:顺序读取字符串各字符ch,执行以下判断:若ch不在map中,则将其压入栈;否则则将map中ch对应
的值与栈顶元素进行比较,若不相同,则退出(匹配错误),若相同,则将栈顶弹出。
二、算法
,要求一个最佳抓取方案。请详细描述你
的算法思路(可以用伪代码),并分析时间复杂度和空间复杂度。
(1)的空间,将整数数组按奇偶数分成2部分,数组左边是奇数、右边是偶数。(要求:给出完整代码,尽量高
效,简洁)
答:参考快排的partition思想,时间O(n),空间O(1)。
三、系统设计题
微博上,每个用户可以发送一条消息,可以follow另一个用户,当用户发送消息时,所有follow他的用户都能
看见这条消息。如AfollowB,则B的消息,A都能看见。
实现一个微博客消息存储系统,可以使用多台机器来满足性能要求,可以再海量的用户和消息下,快速的实现以
下两种查询:
a)给定一个用户,查询他发送的消息,按消息发送时间排序,新的消息在前。
b)给定一个用户,查询他follow的所有人的消息,按消息发送时间排序,新的消息在前.
2011年百度校园招聘技术类笔试真题新鲜出炉
第一大题
,添加一个min函数,找到栈的最小元素。要求函数min、push、pop的时间复杂度为O(1),请
简要描述思路。
,并判断函数功能。同时要指出程序的隐患程序太长了,记不住了。
、二叉平衡树和哈希表存储数据时各自的优劣。
第二大题
,共m颗。每个珠子有自己的颜色,全部颜色共有n种(n小于等于10),从中截取一段,要求:.
包含所有不同的颜色,长度越短越好,如何截取。详述算法思路,并分析时间和空间复杂度。
,比较字符串的大小。,
字符串有数字的情况,仍然沿用strcmp方式。
第三大题
处理一个词搭配的词典,条件为
1)字典中存在的项是两个词的搭配,例如:字典中有“今天”和“晚上”两个词,那它们组成的搭配为“今天晚上”
和“晚上今天”
2)词的集合很大,约为10万量级
3)一个词并不会和其它所有词搭配,通常只会和不超过1万个词搭配
4)对字典的使用读操作很多,通常为上千次请求,几乎没有写入操作。
请设计一个字典服务系统,当请求为两个词的搭配时,能快速返回搭配的相关信息,使用尽可能少的资源,并计算出
需要使用的机器资源。

一、算法设计
1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度
分析。
思路:这个使用数学中的极坐标来解决,先调用[s1,t1]随机产生一个数r,归一化后乘以半径,得到R*(r-s1)/(t1-s1),
然后在调用[s2,t2]随机产生一个数a,归一化后得到角度:360*(a-s2)/(t2-s2)
2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,
现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分
析之,注意:不到最后一刻,并不知用户的总请求量。
思路:如果用户查询的数量小于m,那么直接就存起来。如果用户查询的数量大于m,假设为m+i,那么在1-----m+i
之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i),如果选择的是后面i条记录中的
查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i),当查询记录量很大的时
候,m/(m+i)==(m-1)/(m+i),所以每个query被抽中的概率是相等的。
3、C++STL中vector的相关问题:
(1)、调用push_back时,其内部的内存分配是如何进行的?
(2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作?
vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的时候,这块空间会让某种
方式扩展,但是你删除数据的时候,它却不会缩小。
vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据了,未清内存,因为vector
的capacity容量未变化,系统维护一个的默认值。
有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下
template<classT>
voidClearVector(vector<T>&vt)
{:.
vector<T>vtTemp;
(vt);
}
事实上,vector根本就不管内存,它只是负责向内存管理框架acquire/release内存,内存管理框架如果发现内存
不够了,就malloc,但是当vector释放资源的时候(比如destruct),stl根本就不调用free以减少内存,因为内存
分配在stl的底层:stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list,hashmap也是用
这些内存),所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off
一般的STL内存管理器allocator都是用内存池来管理内存的,所以某个容器申请内存或释放内存都只是影响到内
存池的剩余内存量,而不是真的把内存归还给系统。这样做一是为了避免内存碎片,二是提高了内存申请和释放的效
率——不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端,服务端需做一个异常客户端行为的过滤系统,设服务器在某一刻收到客
户端A的一个请求,则1分钟内的客户端任何其它请求都需要被过滤,现知每一客户端都有一个IPv6地址可作为其ID,
客户端个数太多,以至于无法全部放到单台服务器的内存hash表中,现需简单设计一个系统,使用支持高效的过滤,
可使用多台机器,但要求使用的机器越少越好,请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数:
如p([1,2,3])输出:
[123]、[132]、[213]、[231]、[321]、[312]
求一个组合函数。
方法1:依次从字符串中取出一个字符作为最终排列的第一个字符,对剩余字符组成的字符串生成全排列,最终结果为
取出的字符和剩余子串全排列的组合。
[cpp]viewplaincopy
1.#include<iostream>
2.#include<string>
;
4.
(stringprefix,stringstr)
6.{
(()==0)
<<prefix<<endl;

10.{
(inti=0;i<();i++)
(prefix+str[i],(0,i)+(i+1,()));
13.}
14.}
15.
(strings)
17.{
("",s);:.
19.}
20.
(void)
22.{
23.//method1,unabletoremoveduplicatepermutations.
("abc");
;
26.}
优点:该方法易于理解,但无法移除重复的排列,如:s="ABA",会生成两个“AAB”。
方法2:利用交换的思想,具体见实例,但该方法不如方法1容易理解。
我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a,求后面两个字符bc的排列。
当两个字符bc的排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后
面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了
交换,为了保证这次c仍然是和原先处在第一位置的a交换,我们在拿c和第一个字符交换之前,先要把b和a交换
回来。在交换b和a之后,再拿c和处在第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个
字符b、a的排列。
既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了。
基于前面的分析,我们可以得到如下的参考代码:
(char*pStr,char*pBegin)
2.{
(pStr&&pBegin);
4.//if(!pStr||!pBegin)
5.//return;
(*pBegin=='\0')
("%s\n",pStr);
:.
9.{
;
(char*pCh=pBegin;*pCh!='\0';pCh++)
12.{
(pCh!=pBegin&&*pCh==*pBegin)//为避免生成重复排列,当不同位置的字符相同时
不再交换
;
=*pCh;
16.*pCh=*pBegin;
17.*pBegin=temp;
18.
(pStr,pBegin+1);
20.
=*pCh;
22.*pCh=*pBegin;
23.*pBegin=temp;
24.}
25.}
26.}
27.
(void)
29.{
[]="aba";
(str,str);
;
33.}
如p([1,2,3])输出:
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
这两问可以用伪代码。
百度2012校园招聘笔试题

。任务是互相依赖的。比如B任务依赖A任务,则A完成B才能执行。不
考虑并发限制,假设所有的任务都能一次执行成功,所有的任务执行时间都相等。任务数据结构原型
为:typedefstruct{intid;//该任务的ID
int*child;//该任务依赖的任务的IDintchild_num;//该任务依赖的任务的个数}task;函数原型:
booldoschedule(task*pask,inttask_num);以下函数可以直接调用:
voiddotask(intid);//执行一个进程
intwaittask(inttimeout);//等待timeout时间,并返回一个执行成功的任务的id,如果没有任务在时间片内
完成,则返回-1boolkilltask(intid);//,应该怎么改进?二。简答题
、速度、内存性能等方面的不同点。假如现在有一个缓冲区域绝大多数只需要1KB空间,
极少数极端情况下需要100MB,怎么样合理分配内存?

义a).double*ptr=&value;b).constdouble*ptr=&value;c).double*constptr=&value;d).constdou
ble*constptr=&value;
?比如:
constdoublevalue=;double*ptr;
ptr怎么样获取value的值?解:Ptr=(int*)&value;
,用最简单的算法找出重合长度最长得两条线段。比如线段A(1,5)、B(2,8)、:.
C(3,9),则B和C的重合长度最长,为5.
,例子给出了一个包含5个节点的有向图,标有权值,求始点到终点的距离,图就不
画了。这两道题都需要详细写明算法与函数设计-_-
百度的某某服务机制类似于CS(customer-server),有时候大量用户访问服务器S,导致S运行效率缓慢。为了
提升效率,拟在C上利用一些空余的结果空间作为缓存。已知在C的一台客户机上,每天接收1000wquery,其中
500wuniqquery,每个query5KB,客户机内存3GB,硬盘500GB。做出一个方案,说明系统结构、存储结构、性能优
化等方面的设计。
百度2013校园招聘笔试题
一:简答题(30)
1:数据库以及线程发生死锁的原理及必要条件,如何避免死锁
答:
产生死锁的原因主要是:
(1)因为系统资源不足。
(2)进程运行推进的顺序不合适。
(3)资源分配不当等。
产生死锁的四个必要条件:
(1)互斥条件:一个资源每次只能被一个进程使用。
(2)请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3)不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。
(4)循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
避免死锁:
死锁的预防是通过破坏产生条件来阻止死锁的产生,但这种方法破坏了系统的并行性和并发性。
死锁产生的前三个条件是死锁产生的必要条件,也就是说要产生死锁必须具备的条件,而不是存在这3个条件就一定
产生死锁,那么只要在逻辑上回避了第四个条件就可以避免死锁。
避免死锁采用的是允许前三个条件存在,但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链,从
而避免死锁。该方法支持多个进程的并行执行,为了避免死锁,系统动态的确定是否分配一个资源给请求的进程。
预防死锁:具体的做法是破坏产生死锁的四个必要条件之一
2:面向对象的三个基本元素,五个基本原则
答:
三个基本元素:
封装
继承
多态
五个基本原则:
单一职责原则(Single-ResposibilityPrinciple):一个类,最好只做一件事,只有一个引起它的变化。单一职责原
则可以看做是低耦合、高内聚在面向对象原则上的引申,将职责定义为引起变化的原因,以提高内聚性来减少引起变
化的原因。
开放封闭原则(Open-Closedprinciple):软件实体应该是可扩展的,而不可修改的。也就是,对扩展开放,对修改
封闭的。
Liskov替换原则(Liskov-SubstituionPrinciple):子类必须能够替换其基类。这一思想体现为对继承机制的约束规
范,只有子类能够替换基类时,才能保证系统在运行期内识别子类,这是保证继承复用的基础。
依赖倒置原则(Dependecy-InversionPrinciple):依赖于抽象。具体而言就是高层模块不依赖于底层模块,二者都
同依赖于抽象;抽象不依赖于具体,具体依赖于抽象。
接口隔离原则(