2010百度校园招聘笔试题

2010百度校园招聘笔试题

一、简答题

1. 简述树的深度优先遍历及广度优先遍历及其非递归实现的特点； 2. 找出以下程序中的bug： #include #include struct Record{ int a; int b; };

int create(struct Record *p, int num) {

p = new struct Record[num];

if (!p) return -1; else

return 0; }

int Test() {

struct Record *p = NULL; int i; int num;

printf(\

scanf(\ if (create(p, num) < 0) return -1;

printf(\

for (i = 0; i < num; i++) { p[i].a = 0; p[i].b = 0; }

return 0; }

int main(void) {

Test();

getchar(); return 0; }

#include #include struct Record { };

int create(struct Record *&p, int num) { } int Test() {

struct Record *p = NULL; int i; int num;

printf(\, p);

printf(\); scanf(\,&num); if (create(p, num) < 0)

return -1; printf(\, p); for (i = 0; i < num; i++) { }

return 0;

p[i].a = 0; p[i].b = 0; p=NULL;

p = new struct Record[num]; if (!p) else

return 0; return -1; int a; int b;

delete []p;

} int main(void) { } Test(); getchar(); return 0;

3. 有一台Mini计算机，内存大小为1K，CPU主频为1M（CPU状态每秒改变10的6次方次），问在这台计算机上可运行并且确定可以终止的程序的最长运行时间是多少？

给出思路及推理过程（可以做任何假设）。 二、算法设计

1. 某大型项目由n个组件N1, N2……Nn构成，每个组件都可以独立编译，但是某些组件的编译依赖于其它组件（即某些组件只能在其它组件编译完成后才能编译），设计算法给出统计过程。

#include #define MAXN 505

#define MAXM MAXN*MAXN

struct edge { };

int in[MAXN]; int n,m; edge E[MAXM]; int en;

edge *first[MAXN]; int cnt[MAXN][MAXN];

void insert(int u,int v) { }

void topo()

E[en].v=v;

E[en].mNext=first[u]; first[u]=&E[en++]; int v; edge *mNext;

{ }

int main() { }

freopen(\,\,stdin); while(scanf(\,&n,&m)!=EOF) { } return 0;

memset(first,NULL,sizeof(first)); memset(cnt,0,sizeof(cnt)); memset(in,0,sizeof(in)); int u,v; en=0;

for(int i=0;i

scanf(\,&u,&v); if(cnt[u][v]==0) { }

cnt[u][v]=1; insert(u,v); in[v]++;

for(int i=1;i<=n;i++)

for(int u=1;u<=n;u++) { }

if(in[u]==0) { }

in[u]=-1; printf(\,u);

for(edge *e=first[u];e;e=e->mNext)

in[e->v]--; break;

2. 完成函数：

int maxnumstr(char *inputstr, char *outputstr)

函数功能：找出inputstr中的最长连续数字串存储到outputstr里并返回长度，如调用maxnumstr(\outputstr)后返回4且outputstr中为\。

#include #define MAXN 1000

int maxnumstr(char *inputstr, char *outputstr) { }

int main() {

freopen(\,\,stdin);

if(inputstr==NULL || outputstr==NULL) {

return 0; }

char* begin=inputstr; int res=1; int cur=1;

char pre=*inputstr++; while(*inputstr) { }

for(int i=0;i

outputstr[i]=begin[i]; outputstr[res]='\\0'; return res;

if('0'<=*inputstr&&*inputstr<='9'&&pre==*inputstr-1) else { }

pre=*inputstr++;

res=cur;

begin=inputstr-(cur-1); cur=1; if(res

cur++;

throw \; if(*inputstr=='\\0')

*outputstr='\\0';

} char src[MAXN],tar[MAXN]; while(scanf(\,src)!=EOF) { } return 0;

printf(\,maxnumstr(src,NULL)); printf(\,tar);

三、系统设计

URL(统一资源定位符)由site、path组成，并且有其它属性信息如访问时间等。 如：http://www.http://m.njliaohua.com//img/abc中site为http://www.http://m.njliaohua.com/，path为/img/abc。

1. 设计系统存储100亿条URL信息；

2. 说明如何完成URL信息的添加、删除及修改； 3. 如何添加URL的属性信息；

http://en.wikipedia.org/wiki/URI_scheme

2010搜狐校园招聘笔试题 一、选择题（20题，40分) 二、名词解释（10题，20分）

诸如SQL、TCP、HTTP、QoS、STL、XML等。 SQL(Structured Query Language)结构化查询语言，是一种数据库查询和程序设计语言，用于存取数据以及查询、更新和管理关系数据库系统。同时也是数据库脚本文件的扩展名。

TCP：Transmission Control Protocol 传输控制协议TCP是一种面向连接（连接导向）的、可靠的、基于字节流的运输层（Transport layer）通信协议.

超文本传输协议(HTTP，HyperText Transfer Protocol)是互联网上应用最为广泛的一种网络协议。所有的WWW文件都必须遵守这个标准。设计HTTP最初的目的是为了提供一种发布和接收HTML页面的方法。

QoS（Quality of Service）服务质量，是网络的一种安全机制, 是用来解决网络延迟和阻塞等问题的一种技术。 在正常情况下，如果网络只用于特定的无时间限制的应用系统，并不需要QoS，比如Web应用，或E-mail设置等。但是对关键应用和多媒体应用就十分必要。当网络过载或拥塞时，QoS 能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。

STL = Standard Template Library，标准模板库

XML（Extensible Markup Language）即可扩展标记语言，它与HTML一样，都是SGML(Standard Generalized Markup Language,标准通用标记语言)。Xml是Internet环境中跨平台的，依赖于内容的技术，是当前处理结构化文档信息的有力工具。扩展标记语言XML是一种简单的数据存储语言，使用一系列简单的标记描述数据，而这些标记可以用方便的方式建立，虽然XML占用的空间比二进制数据要占用更多的空间，但XML极其简单易于掌握和使用。

三、程序设计（可用任何编程语言实现）

1. 排序数字字符串的数字（升序），遇到0时从数字字符串中删除，如\”排序后应该为“1234”，”9002“排序后应该为”29“；

2. 前后颠倒输入的英文中的单词位置，标点符号（只可以出现在句尾）位置不变，如输入\输出应该为“you are how Hello!\。

2011年百度

一、 简答

1、系统有很多任务，任务之间有依赖，比如B依赖于A，则A执行完后B才能执行

（1）不考虑系统并行性，设计一个函数（Task *Ptask,int Task_num）不考虑并行度，最快的方法完成所有任务。

（2）考虑并行度，怎么设计 typedef struct{ int ID;

int * child; int child_num; }Task; 提供的函数:

bool doTask(int taskID);无阻塞的运行一个任务；

int waitTask(int timeout);返回运行完成的任务id，如果没有则返回-1； bool killTask(int taskID);杀死进程

2、堆和栈的生命周期，内存分配性能，不同处，如果一般情况下要求1KB，偶尔需要100MB的缓存空间怎么设计？

二、必答题（各种const）

1、解释下面ptr含义和不同（好像是。。。。题干了大概意思是这样。下面应该没错） double* prt = &value const double* ptr = &value double* const ptr=&value const double* const ptr=&value 2、去掉const属性，例： const double value = 0.0f; double* ptr = NULL; 怎么才能让ptr指向value？ 三、算法设计

1、一个一维数轴上有不同的线段，求重复最长的两个线段。 例：a：1~3 b: 2~7 c：2~8

最长重复是b和c 2、有向带权图最短路径 四、系统设计

大概意思是：百度内部有一个类似cs系统的计算系统，由于大并发计算很耗资源，所有要设计一个缓存系统。c做缓存，配置2.66MHZ,3G内存，大概有1000w个查询，唯一的查询大概有500w。要缓存24小时。设计这个缓存系统的运行机制，算法等等东西。。。。。记不太清了。。。

2011年百度校园招聘技术类笔试真题 新鲜出炉 第一大题

1.定义栈的数据结构，添加一个min函数，找到栈的最小元素。要求函数min、push、pop的时间复杂度为O（1），请简要描述思路。 2.是一个读程序写结果，并判断函数功能。同时要指出程序的隐患 程序太长了，记不住了。

3.分析线性表、二叉平衡树和哈希表存储数据时各自的优劣。 第二大题

1.一串首尾相连的珠子，共m颗。每个珠子有自己的颜色，全部颜色共有n种 (n小于等于10)，从中截取一段，要求包含所有不同的颜色，长度越短越好，如何截取。详述算法思路，并分析时间和空间复杂度。

2.设计strnumcmp函数，比较字符串的大小。功能为 a.当字符串中有数字时，以数字大小为准 b.对于只有其中一个字符串有数字的情况，仍然沿用strcmp方式。 第三大题

处理一个词搭配的词典，条件为

1) 字典中存在的项是两个词的搭配，例如：字典中有“今天”和“晚上”两个词，那它们组成的搭配为“今天 晚上”和“晚上 今天” 2）词的集合很大，约为10万量级

3）一个词并不会和其它所有词搭配，通常只会和不超过1万个词搭配 4）对字典的使用读操作很多，通常为上千次请求，几乎没有写入操作。 请设计一个字典服务系统，当请求为两个词的搭配时，能快速返回搭配的相关信息，使用尽可能少的资源，并计算出需要使用的机器资源。

2009百度实习笔试题Zz

一、编程题（30分） 输入：N（整数）

输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节 文件格式如下： 字符串\\\\t数字\\\\n 说明：

每行为1条记录；字符串中不含有\\\\t。

数字描述的是该字符串的出现概率，小于等于100的整数。

多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出； 如果文件格式错误，程序也退出。 要求：

编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机

地输出字符串，输出N条记录 例如： 输入文件A.txt 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

[题目要求]

1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算 法。

2. 给出算法的时间空间复杂度。 3. 证明你的算法。（非常重要）

三、系统设计题（35分）

在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概 念

1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简

写为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、尽可能高效

表的文章；每篇文章通过一个blogid表示。

4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系

统中就是所有好友的文章更新列表。

5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百

万量级。

题目：请在以上限制条件下，设计一个高效的feed访问系统。 要求：

1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed

；feed的展现按照时间倒排序，最新的在最前面

2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友

feed都是未被删除的 3、尽可能高效