![中国人才网](http://static.cnrencai.com/img/cn_logo2.jpg"){kind=logo}
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a) url有可能带http头也有可能不带
b)动态url(即含有"?"的url)的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。
3)此题40分
如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。
4)此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案
百度试题
一、 选择题：15分 共10题
1.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。
A.e B.2e C.n2-e D.n2-2e
2.____是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。
A.继承(Inhertance) B.模板(Template)
C.对象的自身引用(Self-Reference) D.动态绑定(Dynamic Binding)
3.应用层DNS协议主要用于实现 网络服务功能.
A. IP地址到网络设备名字的映射 B. IP地址到网络硬件地址的映射
C. 网络设备名字到IP地址的映射 D. 网络硬件地址到IP地址的映射
4.linux默认情况下，一个进程最多能打开多少文件
A.64 B. 128 C. 512 D. 1024
5.下面结构体
struct s1 {
char ch, *ptr;
union {
short a, b;
unsigned int c:2, d:1;
}
struct s1 *next;
};
的大小是_____：
A. 12字节 B.16字节 C.20字节 D. 24字节
6.任何一个基于"比较"的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。
A.10 B.11 C.21 D.36
7.以下不是进程间通讯的是___
A 共享内存 B 信号量 C线程局部存储 D 消息队列
8.下面程序，求count的值
int func(x)
{
int count= 0;
x=9999;
while(x)
{
Count ++;
x = x&(x-1);
}
return count;
}
A 8; B 10; C 5; D 11
A
9.使用malloc系统调用分配的内存是在__D__ 上分配的
A 栈; B bss; C 物理内存; D 堆
10.最坏情况下，合并两个大小为n的已排序数组所需要的比较次数_____
A.2n B.2n-1 C.2n+1 D.2n-2
二、简答题：20分，共3题
1.(5分)下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。
for (char *piterator = szWord; *piterator != 0; piterator++)
{
if (*piterator & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
piterator += 32;
}
2.(5分)对给定的上亿条无序的url，请按照domain、site以及path分别排序，并请指出排序过程中可能会遇到的哪些问题 如何提高效率
例如：https://www.baidu.com/path/about.html，domain、site以及path的定义分别如下：
Domain:baidu.com
Site:www.baidu.com
Path: www.baidu.com/path
3.(10分)某型CPU的一级数据缓存大小为16K字节，cache块大小为64字节;二级缓存大小为256K字节，cache块大小为4K字节，采用二路组相联。经测试，下面两段代码运行时效率差别很大，请分析哪段代码更好，以及可能的原因。
为了进一步提高效率，你还可以采取什么办法
A段代码
int matrix[1023][15];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < 1023; i++) {
for(j = 0; j < 15; j++) {
sum += matrix[j] + tmp;
}
}
B段代码
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j] + strlen(str);
}
}
三、编程题：30分 共1题
注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
1.内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复(或者重复的概率可以忽略)，并且签名分布足够均匀。
请描述你的数据结构 内存如何申请 增、删、查、改的功能如何实现 如果操作很频繁，该如何优化
取自"https://wiki.xyzp.net/index.php/2006%E7%99%BE%E5%BA%A6%E7%AC%94%E8%AF%95%E9%A2%98
一、选择题：15 分 共 10 题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是：
A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;
3. 代码
void func()
{
static int val;
…
}
中，变量 val 的内存地址位于：
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
4. 同一进程下的线程可以共享以下：
A. stack B. data section C. register set D. thread ID
5. TCP 和 IP 分别对应了 OSI 中的哪几层
A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer
6. short a[100]，sizeof(a) 返回
A. 2 B. 4 C. 100 D. 200 E. 400
7. 以下哪种不是基于组件的开发技术_____。
A. XPCOM B. XP C. COM D. CORBA
8. 以下代码打印的结果是(假设运行在 i386 系列计算机上)：
struct st_t
{
int status;
short *pdata;
char errstr[32];
};
st_t st[16];
char *p = (char *)( st[2].errstr + 32 );
printf( "%d", ( p - (char *)(st) ) );
A. 32 B. 114 C. 120 D. 1112
9. STL 中的哪种结构是连续形式的存储：
A. map B. set C. list D. vector
10. 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是：
A. EDCBA B. DECBA C. DCEAB D. ABCDE
二、简答题：20 分，共 2 题
1. (5 分)重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
2. (15 分)下面一段代码，想在调用 f2(1) 时打印 err1，调用 f2(2) 时打印 err4，但是代码中有一些问题，请做尽可能少的修改使之正确。
1 static int f1( const char *errstr, unsigned int flag ) {
2 int copy, index, len;
3 const static char **__err = { "err1", "err2", "err3", "err4" };
4
5 if( flag & 0x10000 )
6 copy = 1;
7 index = ( flag & 0x300000 ) >> 20;
8
9 if( copy ) {
10 len = flag & 0xF;
11 errstr = malloc( len );
12 if( errstr = NULL )
13 return -1;
14 strncpy( errstr, __err[index], sizeof( errstr ) );
15 } else
16 errstr = __err + index;
17 }
18
19 void f2( int c ) {
20 char *err;
21
22 swtch( c ) {
23 case 1:
24 if( f1( err, 0x110004 ) != -1 )
25 printf( err );
26 case 2:
27 if( f2( err, 0x30000D ) != -1 )
28 printf( err );
29 }
30 }
三、编程题：30 分 共 1 题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 求符合指定规则的数。
给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。
定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。
输出：
1
3
…
四、设计题：35 分 共 1 题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲，并记录了可收听这些歌曲的 2^30 条 URL，但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL，如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如下需求：
1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表
2) 给定一个 SONG_ID，为其添加一个新的 URL_ID
3) 添加一个新的 SONG_ID
4) 给定一个 URL_ID，将其置为不可用
限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理
百度第二套
一、选择题：15 分 共 10 题
1. 已知一个线性表(38,25,74,63,52,48)，采用的散列函数为 Hash($Key)=$Key mod 7，将元素散列到表长为7的哈希表中存储。请选择后面两种冲突解决方法分别应用在该散列表上进行等概率成功查找的平均查找长度，拉链法 ，线性探测法 .
A. 1.0 B. 1.5 C. 1.7 D. 2.0 E. 2.3
F. 7/6 G. 4/3 H. 3/2
2. 需要将OS缓冲区的数据刷新到硬盘，可以调用的函数有(多选)：
A.fflush() B. fsync() C. sync() D.writev()
3. 下面哪个shell语句不能打印出用户主目录的路径
A. echo "$HOME" B. echo ~
C. echo `$HOME` D. echo $HOME
4. 最坏情况下，合并两个大小为n的已排序数组所需要的比较次数
A.2n B.2n-1 C.2n+1 D.2n-2
5. 一个B类网的子网掩码是255.255.240.0，这个子网能拥有的最大主机数是：
A. 240 B. 255 C.4094 D. 65534
6. 以下代码执行后，val的值是___:
unsigned long val = 0;
char a = 0x48;
char b = 0x52;
val = b << 8 | a;
A 20992 B 21064 C 72 D 0
7. 内存的速度远远高于磁盘速度，所以为了解决这个矛盾，可以采用：
A 并行技术 B 虚存技术 C 缓冲技术 D 通道技术
8. 以下代码打印的结果是(假设运行在i386系列计算机上)：
struct st_t
{
int status;
short* pdata;
char errstr[32];
};
st_t st[16];
char* p = (char*)(st[2].errstr + 32);
printf("%d", (p - (char*)(st)));
A 32 B 114
C 120 D 1112
9. 同一进程下的线程可以共享以下
A. stack B. data section
C. register set D. thread ID
10. 以下哪种操作最适合先进行排序处理
A 找最大、最小值 B 计算算术平均值
C 找中间值 D 找出现次数最多的值
二、简答题：20分，共2题
1. (6分)下面是一个http请求：
GET /baidu/blog/item/6605d1b4eb6433738ad4b26d.html HTTP/1.1
Host: hi.baidu.com
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; zh-CN; rv:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6
Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5
Accept-Language: zh-cn,zh;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: gb2312,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive
Referer: https://hi.baidu.com/baidu
Cookie: BAIDUID=AFB70E986AC48B336ABAB7505CDD1C76;
请解释以下各字段基本含义： Host、User-Agent、Accept-Charset、Connection、Referer、Cookie
2. (14分)函数A将字符串str1转成小写，并打印出转化前后的字符串。另外，改错时不能改变函数的接口和主要思路。改错时，请指出行号。
1 #include
2 #include
3
4
5 char* str1 = "ABDFLjlero我们都是saf";
6
7 char* ToLower(char s[])
8 {
9 static size_t i=sizeof(s);
10
11 for (i; i>=0; i--) {
12 if (s>"A" && s<"Z") {
13 s += 26;
14 }
15 }
16 return s;
17 }
18
19 int A()
20 {
21 printf("old str[%s] after lower[%s]n", str1, ToLower(str1));
22 }
三、编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 两个已排序的整型数组，求交集，最快算法
输入：两个已排序的整型数组(int a[m], b[n])
输出：两个数组的交集
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 考虑一个字符串替换的过程，在一个文本文件中含有一些文本内容和一些需要替换的变量，变量的格式为“$Var$”，原来的“$”使用“$$”进行转义，原来的“$$”表示为“$$$”。我们将含有变量的文件称为模板(文件名为t)，文本文件的平均长度为100K。另外，还有一系列的变量文件，里面为变量名和变量值的对应关系(文件名为1.v , 2.v… n.v)，每个变量文件包含的变量数在百万数量级，且变量排列次序不定。现要求将，模板里的变量分别用变量文件里的变量替换，并将生成的文件写成 (1.r, 2.r… n.r)。
要求：从算法和实现上和实现技术上的细节对程序进行优化，尽量使程序高效。程序运行环境为2G内存，4CPU。阐明主要思路，给出伪码和说明，可以着重指出你使用的优化技术。
例子：模板文件为
This is an $FF$ $$. I like $FF$ and $FA$。
变量文件为
1.v
FF : banana
FA : apple
2.v
FA: 苹果
FF : 香蕉
则生成文件为
1.r
This is an banana $$. I like banana and apple。
2.r
This is an香蕉 $$. I like 香蕉and苹果。 1)此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18!=6402373705728000，尾部连续0的个数是3。
(不用考虑数值超出计算机整数界限的问题)
2)此题10分
编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a) url有可能带http头也有可能不带
b)动态url(即含有" "的url)的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。
3)此题40分
如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。
4)此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案
百度面经：我是9月份跟百度联系的，当时连简历都没写，只是写了一下自己做过的一些东西，然后就通知我9月21日面试，第一次面试经过了3个小时，见了4位面试官，一个系统构建师，一个team leader，一个技术部经理，还有一个hrJJ，主要问的问题就是我曾经做过的信息检索项目，基本上照着简历(如果有的话)仔细地问，还会出点题目考你，建议大家多去看看《数据结构》，尤其是算法分析、查找、排序方面的东西。还有一些就看你的反应能力了，这里就不说了。
然后她会让你问一些问题，记得去之前到网上搜集点百度的资料看看，对百度有些认识，然后再问写关于公司发展和个人发展的问题，薪水的问题就别问题。
大约3个星期后，通知我去二面，又见了一个team leader和技术副总裁，这回还是围绕着简历提问，但自由交流的成份很多，就看你的亲和力和素质了，总之让他认为你这个人有创意，有想法，跟你一起合作会很愉快就是了。
当时那个副总裁邀请我到公司去做兼职，因为最近比较忙，就说下学期才能开始，可以说是整个面试中最大的败笔。
一个星期后打电话到HR那里问结果，被告知应届生招聘计划暂时推迟，感觉很faint，只好去找别的工作了。
百度的待遇一直不知道，工作时间大约是每天10小时以上，周六经常加班。
有股票期权，看你是不是喜欢了。
主要注意的是他让你问他问题的时候，一定问点有水平的问题，给他们点表现的机会，它表现的很爽，一高兴，对你也有好处。
百度网络笔试题目
1.假设Apache产生的日志文件名为access_log,在apache正在运行时,执行命令mv
access_log access_log.bak,执行完后,请问新的apache的日志会打印到哪里,为什么
2.在Shell环境下,如何查看远程Linux系统运行了多少时间
3.处理以下文件内容,将域名取出并进行计数排序,如处理:
https://www.baidu.com/index.html
https://www.baidu.com/1.html
https://post.baidu.com/index.html
https://mp3.baidu.com/index.html
https://www.baidu.com/3.html
https://post.baidu.com/2.html
得到如下结果:
域名的出现的次数 域名
3 www.baidu.com
2 post.baidu.com
1 mp3.baidu.com
可以使用bash/perl/php/c任意一种
4.如果得到随机的字串,长度和字串中出现的字符表可定义,并将字串倒序显示,如
把0123456789作为基准的字串字符表,产生一个6位的字串642031,打印出的字串为
130246,可使用bash/perl/php/c任意一种.
5.如何查看当前Linux系统的状态,如CPU使用,内存使用,负载情况等.
6.你在大学中做的最成功的一件事是什么(不必一定与计算机相关) 百度面试过程：
我的求职路程好像很是艰辛……到目前为止面试了很多家，简历更是投了几十份，只有Neusofe给了我一个offer。这个offer并不是对我能力的肯定，只是觉得我可能会留在东软。可惜东软我已经给拒了，基本上没有退路了。
说一下我的百度求职过程吧。
经过在线笔试、两轮电话面试，今天上午收到了百度的拒信，我的百度求职算是告一段落了……
从百度校园招聘开始，我就投了一份简历。在别人都有在线笔试机会的时候，我却没有任何消息。
听说师兄可以给推荐，我就又通过内部推荐的方式投递了一次，这次很快就有消息了——拒信。
那时基本上就放弃了百度。可是大概20多天以后，我投递的第一份简历有消息了——通知我在线笔试。经过精心准备，笔试题答得还凑合。过了几天给我来了封邮件告知我笔试通过，会找时间安排电话面试。又过了好几天，我正在剃头的时候接到百度电话，约了第二天下午三点电话面试。心情异常兴奋，回到寝室拼命复习数据结构并收集百度面试题型……临阵磨枪 呵呵。
百度的面试氛围很是轻松，让你很快就觉得是在聊天而不是面试。第一轮主要是在针对我的在线笔试的题目进行提问和分析，主要讲的是做题的思路和改进的方法。面试时间大概有半个小时，觉得应该有下一轮。
果然上个星期五晚上接到了百度技术经理的电话，自称姓刘。在前一天我同学也是这个时候接到百度第二面电话，看来是同一个人，后来的面试内容证实了是同一个人。面试过程大概如下：
1、介绍一下项目。
2、提了一个问题：上千万条记录，统计出重复记录最多的前N条。
3、一个概率题：54张扑克牌，除去两张大小王剩下52张扑克牌。问红桃A和黑桃A同时被一个人拿到的概率是多少
4、多个线程访问共享内存时因该怎么办
5、在写程序遇到问题的时候，通常采用什么调试方法
6、一个client/server的协议问题
7、剩下就是随便聊聊，比如有缺点、期望工作的性质、职业规划等
总结一下教训：
1、介绍项目的时候不能一味的按照事前想好的模板说，应该根据所申请的工作的性质，多说一些和自己申请的工作内内容相近的东西说。我在介绍我的项目的时候，说了很多硬件的东西，而相关的Linux下的C编程却没有提到多少，一大失败之处。
2、对于他提的第二个问题，当时因为紧张没有想出来，挂了电话以后才有了思路。
3、这个概率题以前碰到过，而且和同学们讨论过，答案很早就知道了。但是遇到面试的时候，不能马上就说出答案，因为这样摆明了高诉人家你以前就见过这道题，这样就失去了作为考题的意义。所以，如果事前知道答案也不要马上说出来，装作考虑中，然后慢慢说出答案。我就是很快就说出了答案，失败!
4、在问项目的时候，他问我代码行大概有多少 我说大概有5.6K行左右。在回答第四个问题的时候，我几乎是将书上所讲过的东西背了一遍给他，虽然答案是正确的，但是我估计他一听就听出来是在背书了，所以这也会减分不少。，而且百度强调创新，其实就算你不知道答案也可以按照自己的思路说一下的，只要逻辑清晰、合理都会比我背书强……
5、我的回答是有时候用gdb，有时候用输出日志的形式。以我之前给他讲的项目经验是不大可能会涉及这么多的知识的，所以估计他又听出我是在背书了……继续减分
6、后来我发现这个问题其实他不是在考我问题的答案，是考我解决问题的能力和考虑问题的思路。这点是我比较差的地方，没办法……减分
我前面表现那么失败，基本上已经没有什么希望了，后面的谈话已经没有意义了，只不过是礼貌性的结束这次面试了。
上面的总结是我收到拒信以后才总结出来的，可悲的是电话面试结束以后，还以为能被录取呢……
面试官太和蔼了，而且气氛及其融洽，根本没有任何不好的征兆，面试官好厉害!
至此，我的百度求职过程到此告一段落……生活还在继续，工作还得继续努力去找，加油! 百度电话面试题目： 1.谈谈你对数据库中索引的理解2.现在普通关系数据库用得数据结构是什么类型的数据结构3.索引的优点和缺点4.session和cache的区别是什么5.如果有几千个session，怎么提高效率6.session是存储在什么地方，以什么形式存储的。
百度技术研发笔试题目
/*百度面试题
* 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，
* 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
*
*
* 分析:题目中的蚂蚁只可能相遇在整数点,不可以相遇在其它点,比如3.5cm处之类的,也就是可以让每只蚂蚁走 1秒,然后
* 查看是否有相遇的即可.
*
* 这样我的程序实现思路就是,初始化5只蚂蚁,让每只蚂蚁走1秒,然后看是否有相遇的,如果有则做相应处理.当每只蚂蚁都
* 走出木杆时,我就记录当前时间.这样就可以得到当前状态情况下,需要多久可以走出木杆,然后遍历所有状态则可以得到所胡
* 可能.
*/
package baidu;
public class Ant {
/*
* step 表示蚂蚁每一个单位时间所走的长度
*/
private final static int step = 1;
/*
* position表示蚂蚁所处的初始位置
*/
private int position;
/*
* direction表示蚂蚁的前进方向，如果为1表示向27厘米的方向走， 如果为-1，则表示往0的方向走。
*/
private int direction = 1;
/*
* 此函数运行一次，表示蚂蚁前进一个单位时间，如果已经走下木杆则会抛出异常
*/
public void walk() {
if (isOut()) {
throw new RuntimeException("the ant is out");
}
position = position + this.direction * step;
};
/**
* 检查蚂蚁是否已经走出木杆，如果走出返回true
*
*/
public boolean isOut() {
return position <= 0 || position >= 27;
}
/**
* 检查此蚂蚁是否已经遇到另外一只蚂蚁
* @param ant
* @return 如果遇到返回true
*/
public boolean isEncounter(Ant ant) {
return ant.position == this.position;
}
/**
* 改变蚂蚁的前进方向
*/
public void changeDistation() {
direction = -1 * direction;
}
/**
* 构造函数,设置蚂蚁的初始前进方向,和初始位置
* @param position
* @param direction
*/
public Ant(int position, int direction) {
this.position = position;
if (direction != 1) {
this.direction = -1;//方向设置初始位置,比如为0时,也将其设置为1.这样可以方便后面的处理
} else {
this.direction = 1;
}
}
}
/////////////////////////////////////////////////////////
package baidu;
public class Controller {
public static void main(String[] args) {
int time = 0;
for (int i = 0; i < 32; i++) {
Ant[] antArray = getAntList(getPoistions(), getDirections(i));
while (!isAllOut(antArray)) {
for (Ant ant : antArray) {
if (!ant.isOut()) {
ant.walk();
}
}
time++;
// 查看是否有已经相遇的Ant,如果有则更改其前进方向
dealEncounter(antArray);
}
System.out.println(time);
// 将时间归0,这样可以重新设置条件,再次得到全部走完所需要的时间.
time = 0;
}
}
/**
* 这个函数的算法很乱，但暂时能解决问题
*
* @param list
*/
public static void dealEncounter(Ant[] antArray) {
int num_ant = antArray.length;
for (int j = 0; j < num_ant; j++) {
for (int k = j + 1; k < num_ant; k++) {
if (antArray[j].isEncounter(antArray[k])) {
antArray[j].changeDistation();
antArray[k].changeDistation();
}
}
}
}
/**
* 因为有5只Ant，所以组合之后有32种组合.刚好用5位二进制来表示,如果为0则表示Ant往0的方向走 如果为1,则表示往27的方向走
*
* 注:在通过Ant的构造函数设置初始值时,通过过滤把0修改成了-1.
*/
public static int[] getDirections(int seed) {
int result[] = new int[5];
result[0] = seed % 2;
result[1] = seed / 2 % 2;
result[2] = seed / 4 % 2;
result[3] = seed / 8 % 2;
result[4] = seed / 16 % 2;
System.out.println("directions is " + result[0] + "|" + result[1] + "|"
+ result[2] + "|" + result[3] + "|" + result[4]);
return result;
}
/**
* 批量设置Ant的初始位置,这样设置不是十分必要,可以直接在代码中设置
*
* @return
*/
public static int[] getPoistions() {
return new int[] { 3, 7, 11, 17, 23 };
}
/**
* 取得设置好初始值的5只Ant
*
* @param positions
* @param directions
* @return
*/
public static Ant[] getAntList(int[] positions, int[] directions) {
Ant ant3 = new Ant(positions[0], directions[0]);
Ant ant7 = new Ant(positions[1], directions[1]);
Ant ant11 = new Ant(positions[2], directions[2]);
Ant ant17 = new Ant(positions[3], directions[3]);
Ant ant23 = new Ant(positions[4], directions[4]);
return new Ant[] { ant3, ant7, ant11, ant17, ant23 };
}
/**
* 判断是否所有的Ant都已经走出了木杆,也就是设置退出条件
*
* @param antArray
* @return
*/
public static boolean isAllOut(Ant[] antArray) {
for (Ant ant : antArray) {
if (ant.isOut() == false) {
return false;
}
}
return true;
}
}
编程：
用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
2 编程：
用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove
函数的功能是拷贝src所指的内存内容前n个字节
到dest所指的地址上。
3 英文拼写纠错：
在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包
含了正确英文单词的词典，请你设计一个拼写纠错
的程序。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度;
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
4 寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串
的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个
。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度。
5 集合合并：
给定一个字符串的集合，格式如：
{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应
输出
{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
////////////////////////////////1
1 题
char *revert(char * str)
{
int n=strlen(str);
int i=0;
char c;
for(i=0;i
{
c=str;
str=str[n-i];
str[n-i]=c;
}
return str;
}
///////////////////////////////////
2 题
void * memmove(void *dest,const void *src,size_t n)
{
assert((dest!=0)&&(src!=0));
char * temp=(char * )dest;
char * ss=(char * )src;
int i=0;
for(;i
{
*temp++=*ss++;
}
return temp;
}
/////////////////////////////////////////////////
3 题
(1)思路 :
字典以字母键树组织，在用户输入同时匹配
(2)
流程:
每输入一个字母：
沿字典树向下一层，
a)若可以顺利下行，则继续至结束，给出结果;
b)若该处不能匹配，纠错处理，给出拼写建议,继续至a);
算法:
1.在字典中查找单词
字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母
一个字母匹配.算法时间就是单词的长度k.
2.纠错算法
情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示
可能 处理方法:
(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;
(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可
以有更多的)
根据分析字典特征和用户单词已输入部分选择(a),(b)处理
复杂性分析：影响算法的效率主要是字典的实现与纠错处理
(a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈;
(b)纠错策略要简单有效 ,如前述情况，是线性复杂度;
(3)改进
策略选择最是重要，可以采用统计学习的方法改进。
//////////////////////////////////////////////
4 题
(1)思路：
用哈希做
(2)
首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度
(注意值与日志项对应关系)
选出前十的频度，取出对应的日志串，简单不过了。
哈希的设计是关键。
//////////////////////////////////////////////////
5 题
(1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有
就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比
较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，
就终止。
(2)处理流程：
1.将集合按照大小排序，组成集合合并待处理列表
2.选择最小的集合，找出与之有交集的集合，
如果有，合并之;
如果无，则与其它集合是独立集合，从待处理列表 中删除。
3.重复直到待处理列表为空
算法：
1。将集合按照大小从小到大排序,组成待处理的集合列表。
2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索
是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3
。
2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素
都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集
合列表。转3。
3。如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m
排序的时间复杂度可以达到n*log(n)
然后对于元素在其他集合中查找，最坏情况下为(n-1)*m
查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)
合并的时间复杂度不会超过查找集合有交集的最坏情况。
所以最终最坏时间复杂度为O(m*m*n*n)
需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处
于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先
与最大的集合进行比较，这些都最大的回避了最坏情况。
(3)可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及
合并的效率增高。
另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
2006百度笔试题
一、选择题：15分 共10题
1.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。
A.e B.2e C.n2-e D.n2-2e
2.____是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。
A.继承(Inhertance) B.模板(Template)
C.对象的自身引用(Self-Reference) D.动态绑定(Dynamic Binding)
3.应用层DNS协议主要用于实现 网络服务功能.
A. IP地址到网络设备名字的映射 B. IP地址到网络硬件地址的映射
C. 网络设备名字到IP地址的映射 D. 网络硬件地址到IP地址的映射
4.linux默认情况下，一个进程最多能打开多少文件?
A.64 B. 128 C. 512 D. 1024
5.下面结构体
struct s1 {
char ch, *ptr;
union {
short a, b;
unsigned int c:2, d:1;
}
struct s1 *next;
};
的大小是_____：
A. 12字节 B.16字节 C.20字节 D. 24字节
6.任何一个基于"比较"的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。
A.10 B.11 C.21 D.36
7.以下不是进程间通讯的是___
A 共享内存 B 信号量 C线程局部存储 D 消息队列
8.下面程序，求count的值
int func(x)
{
int count= 0;
x=9999;
while(x)
{
Count ++;
x = x&(x-1);
}
return count;
}
A 8; B 10; C 5; D 11
9.使用malloc系统调用分配的内存是在____ 上分配的?
A 栈; B bss; C 物理内存; D 堆
10.最坏情况下，合并两个大小为n的已排序数组所需要的比较次数_____
A.2n B.2n-1 C.2n+1 D.2n-2
二、简答题：20分，共3题
1.(5分)下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。
for (char *piterator = szWord; *piterator != 0; piterator++)
{
if (*piterator & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
*piterator += 32;
}
2.(5分)对给定的上亿条无序的url，请按照domain、site以及path分别排序，并请指出排序过程中可能会遇到的哪些问题?如何提高效率?
例如：https://www.baidu.com/path/about.html，domain、site以及path的定义分别如下：
Domain:baidu.com
Site:www.baidu.com
Path: www.baidu.com/path
3.(10分)某型CPU的一级数据缓存大小为16K字节，cache块大小为64字节;二级缓存大小为256K字节，cache块大小为4K字节，采用二路组相联。经测试，下面两段代码运行时效率差别很大，请分析哪段代码更好，以及可能的原因。
为了进一步提高效率，你还可以采取什么办法?
A段代码
int matrix[1023][15];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < 1023; i++) {
for(j = 0; j < 15; j++) {
sum += matrix[i][j] + tmp;
}
}
B段代码
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j][i] + strlen(str);
}
}
三、编程题：30分 共1题
注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
1.内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复(或者重复的概率可以忽略)，并且签名分布足够均匀。
请描述你的数据结构?内存如何申请?增、删、查、改的功能如何实现?如果操作很频繁，该如何优化?
2007百度笔试题
一、选择题：15分 共10题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是 .
A. Shell排序 B. 归并排序 C. 直接插入排序 D. 选择排序
2. 以下多线程对int型变量x的操作，哪几个需要进行同步：
A. x=y; B. x C. x; D. x=1;
3. 代码
void func() {
static int val;
…
}
中，变量val的内存地址位于：
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
4. 同一进程下的线程可以共享以下
A. stack B. data section
C. register set D. thread ID
5. TCP和IP分别对应了 OSI中的哪几层?
A. Application layer
B. Data link layer
C. Presentation layer
D. Physical layer
E. Transport layer
F. Session layer
G. Network layer
6. short a[100]，sizeof(a)返回?
A 2 B 4 C 100 D 200 E 400
7. 以下哪种不是基于组件的开发技术_____。
A XPCOM B XP C COM D CORBA
8. 以下代码打印的结果是(假设运行在i386系列计算机上)：
struct st_t
{
int status;
short* pdata;
char errstr[32];
};
st_t st[16];
char* p = (char*)(st[2].errstr 32);
printf("%d", (p - (char*)(st)));
A 32 B 114
C 120 D 1112
9. STL中的哪种结构是连续形式的存储
A map B set C list D vector
10. 一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是( )
A、EDCBA; B、DECBA; C、DCEAB; D、ABCDE
二、简答题：20分，共2题
1. (5分)重复多次fclose一个打开过一次的FILE *fp指针会有什么结果，并请解释。
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异
常。
2. (15分)下面一段代码，想在调用f2(1)时打印err1，调用f2(2)时打印err4，但是代码
中有一些问题，请做尽可能少的修改使之正确。
1 static int f1(const char *errstr, unsigned int flag) {
2 int copy, index, len;
3 const static char **__err = {“err1”, “err2”, “err3”, “err4”};
4
5 if(flag & 0x10000)
6 copy = 1;
7 index = (flag & 0x300000) >> 20;
8
9 if(copy) {
10 len = flag & 0xF;
11 errstr = malloc(len);
12 if(errstr = NULL)
13 return -1;
14 strncpy(errstr, __err[index], sizeof(errstr));
15 } else
16 errstr = __err index;
17 }
18
19 void f2(int c) {
20 char *err;
21
22 swtch(c) {
23 case 1:
24 if(f1(err, 0x110004) != -1)
25 printf(err);
26 case 2:
27 if(f2(err, 0x30000D) != -1)
28 printf(err);
29 }
30 }
三、编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 求符合指定规则的数。
给定函数d(n) = n n的各位之和，n为正整数，如 d(78) = 78 7 8=93。 这样这个函数
可以看成一个生成器，如93可以看成由78生成。
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出
1至10000里的所有符合数A定义的数。
输出：
1
3
…
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或
者流程说明。
1. 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每
首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结
果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求
：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个
。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩
大，该如何多机分布处理?
腾讯笔试题：
1 计算 a^b << 2 (运算符优先级问题)
2 根据先序中序求后序
3 a[3][4]哪个不能表示 a[1][1]: *(&a[0][0]) *(*(a+1)+1) *(&a[1]+1) *(&a[0][0]+4)
4 for(int i...)
for(int j...)
printf(i,j);
printf(j)
会出现什么问题
5 for(i=0;i<10;++i,sum+=i);的运行结果
6 10个数顺序插入查找二叉树，元素62的比较次数
7 10个数放入模10hash链表，最大长度是多少
8 fun((exp1,exp2),(exp3,exp4,exp5))有几个实参
9 希尔 冒泡 快速 插入 哪个平均速度最快
10 二分查找是 顺序存储 链存储 按value有序中的哪些
11 顺序查找的平均时间
12 *p=NULL *p=new char[100] sizeof(p)各为多少
13 频繁的插入删除操作使用什么结构比较合适，链表还是数组
14 enum的声明方式
其他1个选择暂时想不起来了
大题：
1 把字符串转换为小写，不成功返回NULL,成功返回新串
char* toLower(char* sSrcStr)
{
char* sDest= NULL;
if( __1___)
{
int j;
sLen = strlen(sSrcStr);
sDest = new [_______2_____];
if(*sDest == NULL)
return NULL;
sDest[sLen] = '\0';
while(_____3____)
sDest[sLen] = toLowerChar(sSrcStr[sLen]);
}
return sDest;
}
2 把字符串转换为整数 例如："-123" -> -123
main()
{
.....
if( *string == '-' )
n = ____1______;
else
n = num(string);
.....
}
int num(char* string)
{
for(;!(*string==0);string++)
{
int k;
k = __2_____;
j = --sLen;
while( __3__)
k = k * 10;
num = num + k;
}
return num;
}
附加题：
1 linux下调试core的命令，察看堆栈状态命令
2 写出socks套接字 服务端 客户端 通讯程序
3 填空补全程序，按照我的理解是添入：win32调入dll的函数名 查找函数入口的函数名 找到函数的调用形式 把formView加到singledoc的声明 将singledoc加到app的声明
4 有关系 s(sno,sname) c(cno,cname) sc(sno,cno,grade)
1 问上课程 "db"的学生no
2 成绩最高的学生号
3 每科大于90分的人数
其他
1)此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18!=6402373705728000，尾部连续0的个数是3。
(不用考虑数值超出计算机整数界限的问题)
2)此题10分
编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a) url有可能带http头也有可能不带
b)动态url(即含有"?"的url)的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。
3)此题40分
如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。
4)此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案
百度2008年校园招聘笔试题(研发技术)
不定项选择题
线程与进程比较而言，下面论述成立的有()
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系统中，对命令“In file 1 file2”描述正确的是?()
A.建立软链接file1,并指向file2
B. 建立硬链接file1,并指向file2
C. 建立软链接file2,并指向file1
D. 建立硬链接file2,并指向file1
9.在Shell编程中，下面哪个表示上一步所运行程序的返回值?()
A. $#
B. $(后一字符打不出来可以描述一下‘S下面在加一点’)
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站点上的有价值网页。
1) 请设计基本模型，并做出简要说明。
请考虑如何获取网页、如何存储网页、如何判断网页的价值。。。。。。。。
2) 实际应用中，需要考虑哪些因素。
(四) 简述：某广告投放系统采用B/S结构，其主要用户为广告主，广告主可通过该广告投放系统在各个网站上投放广告并查看投放效果。该广告系统需要实现如下功能：
1) 用户可向自己账户中加款。
2) 用户可提交广告，广告包括四种形式：文字广告，图片广告，flash广告和对媒体广告。
3) 用户可制定哪些广告在哪些网站上展现，用户可分别广告在制定网站上的点击单价
4) 广告被点击时，直接从用户账户中扣除相应的钱款
5) 用户账户余额不足时，所有广告失效，用户加款后，恢复生效。
6) 用户可查询广告的每日消费情况(点击次数、消费额)、广告在各个网站的消费情况。
要求：1)设计该系统的数据表结构，要求满足上述功能，结构清晰，并尽可能灵活。
2)写出功能6所涉及的SQL语句
3)请分析随着广告主的增加、广告点击次数的增长，系统可能会在哪些方面出项性能瓶颈?你在设计时是如何考虑解决这些瓶颈的?潜在的性能瓶颈还有哪些?
1)此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18!=6402373705728000，尾部连续0的个数是3。
(不用考虑数值超出计算机整数界限的问题)
2)此题10分
编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a) url有可能带http头也有可能不带
b)动态url(即含有"?"的url)的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。
3)此题40分
如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。
4)此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案
1 编程：
用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
2 编程：
用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
3 英文拼写纠错：
在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度;
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
4 寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度。
5 集合合并：
给定一个字符串的集合，格式如： {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh} 要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出 {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程，算法，以及算法的复杂度
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
////////////////////////////////
1 题
char *revert(char * str)
{
int n=strlen(str);
int i=0;
char c;
for(i=0;i {
c=str;
str=str[n-i];
str[n-i]=c;
}
return str;
}
///////////////////////////////////
2 题
void * memmove(void *dest,const void *src,size_t n)
{
assert((dest!=0)&&(src!=0));
char * temp=(char * )dest;
char * ss=(char * )src;
int i=0;
for(;i {
*temp =*ss ;
}
return temp;
}
/////////////////////////////////////////////////
3 题
(1)思路: 字典以字母键树组织，在用户输入同时匹配
(2) 流程:
每输入一个字母：
沿字典树向下一层，
a)若可以顺利下行，则继续至结束，给出结果;
b)若该处不能匹配，纠错处理，给出拼写建议,继续至a);
算法:
1.在字典中查找单词
字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母
一个字母匹配.算法时间就是单词的长度k.
2.纠错算法
情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能 处理方法:
(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;
(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可 以有更多的)
根据分析字典特征和用户单词已输入部分选择(a),(b)处理
复杂性分析：影响算法的效率主要是字典的实现与纠错处理
(a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈;
(b)纠错策略要简单有效 ,如前述情况，是线性复杂度;
(3)改进
策略选择最是重要，可以采用统计学习的方法改进。
//////////////////////////////////////////////
4 题
(1)思路：用哈希做
(2) 首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度(注意值与日志项对应关系) my.chinahrlab.com 选出前十的频度，取出对应的日志串，简单不过了。哈希的设计是关键。
//////////////////////////////////////////////////
5 题
(1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。
(2)处理流程：
1.将集合按照大小排序，组成集合合并待处理列表
2.选择最小的集合，找出与之有交集的集合，如果有，合并之;如果无，则与其它集合是独立集合，从待处理列表 中删除。
3.重复直到待处理列表为空
算法： 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在：
1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。
2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。
3。如果待处理集合列表不为空，转2。
如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。
算法复杂度分析：
假设集合的个数为n，最大的集合元素为m 排序的时间复杂度可以达到n*log(n) 然后对于元素在其他集合中查找，最坏情况下为(n-1)*m 查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(m*m*n*n)
需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。
(3)可能的改进：
首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。
取自"https://wiki.xyzp.net/%E7%99%BE%E5%BA%A611%E6%9C%884%E6%97%A5%E7%BD%91%E4%B8%8A%E7%AC%94%E8%AF%95%E9%A2%98%E5%8F%8A%E7%AD%94%E6%A1%88%EF%BC%88%E4%BB%85%E4%BE%9B%E5%8F%82%E8%80%83%EF%BC%89.htm"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
1)此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18!=6402373705728000，尾部连续0的个数是3。 (不用考虑数值超出计算机整数界限的问题)
2)此题10分 编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目录页：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
请注意：
a) url有可能带http头也有可能不带
b)动态url(即含有"?"的url)的一律不算目录页，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能(附加5分)。
3)此题40分
如果必须从网页中区分出一部分"重要网页"(例如在10亿中选8亿)，比其他网页更值得展现给用户，请提出一种方案。
4)此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文(即网页的源码)、全文长度、网页正文(即网页中提取的主体文字)、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。
取自"https://wiki.xyzp.net/%E7%99%BE%E5%BA%A6%E7%AC%94%E8%AF%95%E9%A2%98%282005%29.htm"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
好久没来了。
发生了一些事情，其间的心情已不是几行文字所能表述的了。
终于明白有些事情，并不是自己努力就一定能圆满的;有些事情，是我控制不了的。
唉，不提也罢!
说说今天去百度笔试的经历吧
部门：百度搜索应用技术部。
地点：海淀南路银科大厦(海淀图书城西临)18层。
时间：2005/6/15 10：00-11：20 am
九点从实验室出发，725到知春路，转735，到海淀桥下车，9：50到达百度。在725的车上碰到一男士索要手机号，说自己认识信息产业部的部长杨泽民先生，以居高临下的姿态把手机号给了他-__-!
在百度前台见到了一直帮我安排笔试的杨韫敏jj，不是想象中的HR形象，而是一副干练的女IT的样子跳跃的灵魂很快，给我找了一间小会议室，只有一张桌子，两把椅子，还帮我开了灯，关门，走人，我开始看题。冷汗也开始流。翻了一下三页纸的笔试题，只有很少的传说中的Linux题目，其他的全是C、数据结构、算法编程的题。第一反应：走人!但又觉得对不起陈jj，关键的是我已经在笔试题上写了姓名和学校了，sign，总的为自己的名字和学校负责吧，他们是无辜的。如此斗争良久，决定坚持下来。
题目大致是这样的：
第一部分选择题：有几道网络相关的题目，巨简单，比如第一题是TCP、RIP、IP、FTP中哪个协议是传输层的......。有一道linux的chown使用题目。其他的全是数据结构的题目!什么链，表，码的，不知所云跳跃的灵魂唉，我可以没有学过数据结构的人呐!真残忍!这一部分迅速猜完!
第二部分简答题：
1、在linux中如何编译C程序，使之成为可执行文件?如何调试?
答案：
1)检查程序中.h文件所在的目录，将其加入系统PATH中;
2)执行C编译：#gcc [源文件名] -o [目标文件名]
执行C++编译：#g++ [源文件名] -o [目标文件名]
3)改变目标文件为可执行文件：#chmod +x [目标文件名]
4)如需将多个可执行文件连续执行，可生成批处理文件：
#vi [批处理文件名]
可执行文件1
可执行文件2
.........
最后将该批处理文件属性该位可执行。
调试：在编译时使用-g参数，就可以使用gdb进行调试。
2、写出内存分配和释放的函数，并指出区别。
答案：
C语言的标准内存分配函数：malloc，calloc，realloc，free等。
malloc与calloc的区别为1块与n块的区别：
malloc调用形式为(类型*)malloc(size)：在内存的动态存储区中分配一块长度为“size”字节的连续区域，返回该区域的首地址。
calloc调用形式为(类型*)calloc(n，size)：在内存的动态存储区中分配n块长度为“size”字节的连续区域，返回首地址。
realloc调用形式为(类型*)realloc(*ptr，size)：将ptr内存大小增大到size。
free的调用形式为free(void*ptr)：释放ptr所指向的一块内存空间。
C++中为new/delete函数。
3、写出socket函数，并指出其功能。
socket():建立socket通信描述符;
bind()：将套接字和机器上的一定的端口关联;
connect()：连接到远程主机;
listen()：使套接字做好连接的准备，规定等待服务请求队列的长度;
accept()：接受连接，一旦有客户端发出连接，accept返回客户地址信息和一个新的sock;
有了这个新的sock，双方就可以开始收发数据：
send()和recv()：用于流式套接字或者数据套接字的通讯;
sendto()和recvfrom()：用于无连接的数据报套接字;
close()：关闭套接字;
shutdown()：选择性的关闭套接字，可以只允许某一方向的通讯关闭;
getpeername()：返回流式套接字时对端peer信息;
gethostname()：返回程序所运行的机器的主机名字;
gethostbyname()：返回本机IP;
第三部分编程题：
1、从文件中读取字符串数据，反序显示并大小写转换。
2、给定26字母表以及对应的密码表，编程实现加密及解密功能。
第四部分思考题(正是传说中的字典纠错题)：
用户在输入英文单词时经常出错，现对其进行就错。给定一个正确的英文词典，考虑纠错实现。1)指出思路。2)流程、算法难易程度及可能的改进策略。
不过陈jj没有给我答题纸，只好拿试题的背面做了答题纸兼草稿纸-___-!说实话有些题目是很基础的，就是没背过。不知怎么搞得，巨潦草。实验室参加过笔试的通同学都是憋着劲做了两个多小时才答完，而我只一个小时就完了，唉，正好说明肚子里只有别人一半的东西~~看着潦草而不着边际的答题，决定在最后给陈jj写段话，大意就是感谢她帮我挽回了一次笔试的机会，但我的表现很遗憾等等......然后交卷走人~~
没想到交了试卷没让我走，等了大约30分钟的样子，有个很深沉的gg来看我的卷子跳跃的灵魂-___-!我颤颤的跟他说我很长时间没有接触C了，当时脖子都红了，真觉得丢人。gg看了一下，没有很鄙视的样子，问我有没有带简历。当然木有啦~~答应回来给他发个电子版的，然后赶紧跑人了!
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
题目大致是这样的：
第一部分选择题：
有几道网络相关的题目，巨简单，比如第一题是TCP、RIP、IP、FTP中哪个协议是传输层的......。有一道linux的chown使用题目。其他的全是数据结构的题目!什么链，表，码的，不知所云.唉，我可以没有学过数据结构的人呐!真残忍!这一部分迅速猜完!
第二部分简答题：
1、在linux中如何编译C程序，使之成为可执行文件?如何调试?
答案： 1)检查程序中.h文件所在的目录，将其加入系统PATH中;
2)执行C编译：#gcc [源文件名] -o [目标文件名]
执行C++编译：#g++ [源文件名] -o [目标文件名]
3)改变目标文件为可执行文件：#chmod +x [目标文件名]
4)如需将多个可执行文件连续执行，可生成批处理文件：
#vi [批处理文件名]
可执行文件1
可执行文件2
.........
最后将该批处理文件属性该位可执行。
调试：在编译时使用-g参数，就可以使用gdb进行调试。
2、写出内存分配和释放的函数，并指出区别。
答案：
C语言的标准内存分配函数：malloc，calloc，realloc，free等。
malloc与calloc的区别为1块与n块的区别：
malloc调用形式为(类型*)malloc(size)：在内存的动态存储区中分配一块长度为“size”字节的连续区域，返回该区域的首地址。
calloc调用形式为(类型*)calloc(n，size)：在内存的动态存储区中分配n块长度为“size”字节的连续区域，返回首地址。
realloc调用形式为(类型*)realloc(*ptr，size)：将ptr内存大小增大到size。
free的调用形式为free(void*ptr)：释放ptr所指向的一块内存空间。
C++中为new/delete函数。
3、写出socket函数，并指出其功能。
socket():建立socket通信描述符;
bind()：将套接字和机器上的一定的端口关联;
connect()：连接到远程主机;
listen()：使套接字做好连接的准备，规定等待服务请求队列的长度;
accept()：接受连接，一旦有客户端发出连接，accept返回客户地址信息和一个新的sock;
有了这个新的sock，双方就可以开始收发数据：
send()和recv()：用于流式套接字或者数据套接字的通讯;
sendto()和recvfrom()：用于无连接的数据报套接字;
close()：关闭套接字;
shutdown()：选择性的关闭套接字，可以只允许某一方向的通讯关闭;
getpeername()：返回流式套接字时对端peer信息;
gethostname()：返回程序所运行的机器的主机名字;
gethostbyname()：返回本机IP;
第三部分编程题：
1、从文件中读取字符串数据，反序显示并大小写转换。
2、给定26字母表以及对应的密码表，编程实现加密及解密功能。
第四部分思考题(正是传说中的字典纠错题)：
用户在输入英文单词时经常出错，现对其进行就错。给定一个正确的英文词典，考虑纠错实现。1)指出思路。2)流程、算法难易程度及可能的改进策略。
一道算法题目答案
int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数
{
for(n=0,i=1;i〈=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串
{ //分别把T的前面和后面部分保存为head和tail
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));
StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串
i+=Strlen(V); //当前指针跳到插入串以后
n++;
}//if
return n;
}//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果? (无限递归face)
百度2005年的笔试题
1.实现 void delete_char(char * str, char ch);
把str中所有的ch删掉
2.把字符串S中所有A子串换成B,这个没给函数原型
3.搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
(1) 主要解决思路 //具体用词和原题不大一样
(2) 算法及其复杂度分析
4.有字典,设计一个英文拼写纠正算法 (1) 思想 (2) 算法及复杂度 (3) 改进
5. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合
要求把交集不为空的集合并起来,如上例会得到 { aaa, bb, ccc, dd, ff }, {gg}
(1) 思想 (2) 算法及复杂度 (3) 改进
取自"https://wiki.xyzp.net/%E7%99%BE%E5%BA%A6%E7%AC%94%E8%AF%95%E9%A2%982005.htm"
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
一、选择题：15分 共10题
1.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有____个零元素。
A.e B.2e C.n2-e D.n2-2e
2.____是面向对象程序设计语言中的一种机制。这种机制实现了方法的定义与具体的对象无关，而对方法的调用则可以关联于具体的对象。
A.继承(Inhertance) B.模板(Template)
C.对象的自身引用(Self-Reference) D.动态绑定(Dynamic Binding)
3.应用层DNS协议主要用于实现 网络服务功能.
A. IP地址到网络设备名字的映射 B. IP地址到网络硬件地址的映射
C. 网络设备名字到IP地址的映射 D. 网络硬件地址到IP地址的映射
4.linux默认情况下，一个进程最多能打开多少文件?
A.64 B. 128 C. 512 D. 1024
5.下面结构体
struct s1 {
char ch, *ptr;
union {
short a, b;
unsigned int c:2, d:1;
}
struct s1 *next;
};
的大小是_____：
A. 12字节 B.16字节 C.20字节 D. 24字节
6.任何一个基于"比较"的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。
A.10 B.11 C.21 D.36
7.以下不是进程间通讯的是___
A 共享内存 B 信号量 C线程局部存储 D 消息队列
8.下面程序，求count的值
int func(x)
{
int count= 0;
x=9999;
while(x)
{
Count ++;
x = x&(x-1);
}
return count;
}
A 8; B 10; C 5; D 11
9.使用malloc系统调用分配的内存是在____ 上分配的?
A 栈; B bss; C 物理内存; D 堆
10.最坏情况下，合并两个大小为n的已排序数组所需要的比较次数_____
A.2n B.2n-1 C.2n+1 D.2n-2
二、简答题：20分，共3题
1.(5分)下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。
for (char *piterator = szWord; *piterator != 0; piterator++)
{
if (*piterator & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
piterator += 32;
}
2.(5分)对给定的上亿条无序的url，请按照domain、site以及path分别排序，并请指出排序过程中可能会遇到的哪些问题?如何提高效率?
例如：https://www.baidu.com/path/about.html，domain、site以及path的定义分别如下：
Domain:baidu.com
Site:www.baidu.com
Path: www.baidu.com/path
3.(10分)某型CPU的一级数据缓存大小为16K字节，cache块大小为64字节;二级缓存大小为256K字节，cache块大小为4K字节，采用二路组相联。经测试，下面两段代码运行时效率差别很大，请分析哪段代码更好，以及可能的原因。
为了进一步提高效率，你还可以采取什么办法?
A段代码
int matrix[1023][15];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < 1023; i++) {
for(j = 0; j < 15; j++) {
sum += matrix[i][j] + tmp;
}
}
B段代码
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j][i] + strlen(str);
}
}
三、编程题：30分 共1题
注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
1.内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复(或者重复的概率可以忽略)，并且签名分布足够均匀。
请描述你的数据结构?内存如何申请?增、删、查、改的功能如何实现?如果操作很频繁，该如何优化?
总结一下教训：
1、介绍项目的时候不能一味的按照事前想好的模板说，应该根据所申请的工作的性质，多说一些和自己申请的工作内内容相近的东西说。我在介绍我的项目的时候，说了很多硬件的东西，而相关的Linux下的C编程却没有提到多少，一大失败之处。
2、对于他提的第二个问题，当时因为紧张没有想出来，挂了电话以后才有了思路。
3、这个概率题以前碰到过，而且和同学们讨论过，答案很早就知道了。但是遇到面试的时候，不能马上就说出答案，因为这样摆明了高诉人家你以前就见过这道题，这样就失去了作为考题的意义。所以，如果事前知道答案也不要马上说出来，装作考虑中，然后慢慢说出答案。我就是很快就说出了答案，失败!
4、在问项目的时候，他问我代码行大概有多少?我说大概有5.6K行左右。在回答第四个问题的时候，我几乎是将书上所讲过的东西背了一遍给他，虽然答案是正确的，但是我估计他一听就听出来是在背书了，所以这也会减分不少。，而且百度强调创新，其实就算你不知道答案也可以按照自己的思路说一下的，只要逻辑清晰、合理都会比我背书强……
5、我的回答是有时候用gdb，有时候用输出日志的形式。以我之前给他讲的项目经验是不大可能会涉及这么多的知识的，所以估计他又听出我是在背书了……继续减分
6、后来我发现这个问题其实他不是在考我问题的答案，是考我解决问题的能力和考虑问题的思路。这点是我比较差的地方，没办法……减分
我前面表现那么失败，基本上已经没有什么希望了，后面的谈话已经没有意义了，只不过是礼貌性的结束这次面试了。
上面的总结是我收到拒信以后才总结出来的，还以为能被录取呢……
面试官太和蔼了，而且气氛及其融洽，根本没有任何不好的征兆，面试官好厉害!
至此，我的百度求职过程到此告一段落……生活还在继续，工作还得继续努力去找，加油!
百度电话面试题目：
1.谈谈你对数据库中索引的理解
2.现在普通关系数据库用得数据结构是什么类型的数据结构
3.索引的优点和缺点
4.session和cache的区别是什么
5.如果有几千个session，怎么提高效率
6.session是存储在什么地方，以什么形式存储的。
百度川大站笔试题
技术类试卷一
1、编程题
判断字符串 b 的所有字符是否都再字符串 a 中出现过，a,b都是可能包含汉字的字符串。b中重复出现的汉字，那么a中也要至少出现相同的次数。
汉字使用gbk编码(简单的所，用两个字节表示一个汉字，高字节最高位为1的代表汉字，低字节最高位可以不为1)。
int is_include(char *a , char *b)
返回0 表示没有都出现过，返回1表示都出现过。
2、 算法题
序列 seq=[a,b,…,z,aa,ab,…,az,ba,bb,…,bz,…,za,zb,…,zz,aaa,…]类似于excel的字母序排列，任意给一字符串 s=[a-z]+(由a-z字符串组成的任意长度字符串)，请问s是序列seq的第几个字符串。
3、 系统设计
需求：需要引入用户对搜索结果相关性的评分，100分制。希望用户的打分能帮助搜索引擎排序，但又避免恶意投票、作弊等。请设计一个比较公平的评分系统。
以为大家对百度不是很敢兴趣呢，我上个月去那里面试了，来发一篇吧
我是上个月在chinahr上直接给他们投的简历，那个时候可能人比较少吧，他们很快就发了笔试通知，然后偶就过去了，地点在盈科18层(海淀图书城很近)，到了，以后，先给偶作了一套题，一共四道大题，时间是两个小时，题都是非常典型的算法题，对算法的效率和健壮性要求比较高，比如说，在百万数量级的文件中查找某个可匹配的关键字，千万个节点的链表的逆序(具体的题目由于百度要求不让外泄，所以只能说这么多拉)偶憋了半天写了三道题，可以说都没写完。还有一题只是把想法写了写，没有编代码，就交了，然后在一个屋子里面等，过了一会进来一个看起来像很有编程经验的gg，自我介绍是高级软件工程师，
他主要问的是关于笔试这四道题，我的思路什么，偶的数据结构早就还给老师拉，憋了半天，就瞎说了一通，他显然不是很满意，说给5分钟，再好好想想，偶又憋了半天，还是没想出好的办法，基本上没题都要问一遍，偶实在答不出来了，他说时间不够了，算了，终于长舒了一口气，然后就问了些做过的项目，终于轻松一些了，偶就老老实实做了什么就说什么了，二面是技术经理，就是网上鼎鼎有名的齐玉杰，见到真人后，看起来非常亲切，不知道
为什么心情就放松起来了，接下来就聊了聊项目，还有对搜索的看法，还重点文了搜索算法的思路9是没答上来?( 不过齐gg还是非常nice的，也没有刁难我，三面是技术总监,他们叫dan,就是非常有名的郭耽，偶是第二天去的，偶想象技术总监怎么也应该有些年纪了，结果也是出乎意料的年轻，感觉像个学生，最令偶吃惊的是，他居然穿着拖鞋....呵呵，他主要问一些概要的东东，比如说最大的困难是什么啊，能为百度贡献什么啊，诸如此类
整个过程就是这样，补充一下，我申请的是搜索应用部(就是做mp搜索的部门)，对了，他们还多次问到有没有用过百度地业务，偶只知道mp3，其实还有好多，寒...感觉百度的氛围还是挺宽松，经理也没什么架子，大家放松心情去就好了
百度2010暑期实习笔试面试全面备战
百度2010暑期实习网申将于2010年5月29日截止。
笔试阶段
5月30日前，对于通过了简历筛选的申请人百度将会通过系统发送笔试通知。注册时请务必填写正确有效的邮箱地址。
面试阶段
6月7日起，百度将陆续安排现场面试。
大街网为大家准备了百度往年的实习和校园招聘笔试及面试经验，供大家参考。
以下为百度2010校园招聘各岗位笔试真题，全部是大街网网友整理，不代表今年笔试内容，请大家参考。
【百度2010校园招聘技术类笔经】
第一题：简要说明树的深度优先、广度优先遍历算法挤特点
第二题：一个复数相加的编码挑错题
第三题：告诉内存大小和cpu速度，计算可能的程序运行最长时间
第四题：复杂项目的组件编译依赖，设计一个快速算法并计算复杂度
第五题：写个c程序，返回字符串中最长数字字符串的长度和地址，不能用标准库函数
第六题：设计个系统，存储100亿个url和属性信息，并可以更改属性信息和查找url，快速搜索站点的所有url及信息
【百度2010校园招聘非技术类笔试题】
1、09年的第一道图形推理题，不过我不知道正确答案，知道的童鞋请帮忙告诉一声，我选的C
2、还是往年论坛上有的非技术题，只是换了下字，分析2010年的网络购物，宠物用品和化妆品
3、说出10种易拉罐为什么做成圆柱形的理由
4、一个八边形，各角觉有一小虫，爬呀爬，计算终点之类的，题目太长，没记住，抱歉。。。
5、3个男人、2个女人一起渡河，只有一条船，每次只能渡两个人
女人要求：不能让一男一女同时一起过河
男人要求，每人只能划一次浆
如果只有一个划桨的，阿特第一，本第二，**第三。。
问：用最短的过河次数推测，谁最后一个划桨渡河?
6、有两张标准版的世界地图，一张的比例尺是1：3600万，另一张的比例尺是1：2000万，将较大的一张完全的覆盖较小的一张(两张都是平整铺开的情况)。请问：取出一枚图钉，是否可以选择到一个点，按下去，刺穿的两张地图的点对应的是同一个真实地球上的点?不论是或否，请给出你的思考和论证过程。
7、说明一些你对互联网和百度产品的理解、分析之类的
8、你认为这次测试是否能够基本反映出自己的水平?你对自己今天的答案满意么?如果不是，你还有哪些补充?
【2010校园招聘百度用户体验部笔试题】
第一部分:答一题，多答不限
1.方差分析的统计原理和运用条件
2.什么是社会网络研究?它的主要观点是什么?有哪些应用?
3.市场调研过程分为几个阶段?各个阶段的核心任务和目标是什么?
第二部分：三题必须都答
1.用户体验研究领域有哪些专家?用一句话描述他们的主要观点?
2.用户体验研究和产品运营之间的关系
3.交互设计是什么?一个好的交互设计具备哪些特征?举例说明。
第三部分：答两题，多答不限
1.简述用户体验研究方面的企业实践项目?(没有可以不写)
2.有用户提出反馈“搜索结果页面，需要将页面拖放到最底才可点击下一页，可否实现翻页置顶或自动反应功能”，如何处理这个问题
3.百事可乐攻击可口可乐时，曾经在马路上随机做双盲实验，多数人认为百事可乐比可口可乐好喝，百事可乐公司以此为据进行推广。可口可乐也在马路上做双盲实验，惊奇地发现，多数人认为百事可乐比可口可乐好喝，因此，可口可乐公司下定决心改进产品，推出新产品“new coke”，没想到“NEWCOKE”推出后消费者抵制，并且要求推出原来的口味。请分析“new coke”失败的原因。
4.统计关键词的搜索量时(有一个图，统计2007 2008 2009关键词搜索量)，有人说“......，因此，当台风来时，人们就更关注变形金刚”，设计一个研究说明结论正确与否。
第四部分：附加题
有四道逻辑推理题
估算你所在城市的出租车数量?简述估算理由。
【百度2010校园招聘运维web开发两道笔试题】
1.推理：24个人，每人至少养一种宠物，养鸟、狗、鱼、猫的分别为13、5、10、9人，同时养鸟和狗的2人，同时养鸟和鱼、鸟和猫、鱼和猫的各为4人，养狗的既不养猫也不养鱼。问只养一种宠物的总共几人?同时养鸟鱼猫的几人?
2.找程序的错和不足：
int test(char *value,int value_len,int flag)
{
char temp_buf[BUF_SIZE];
sprintf(temp_buf,value);
char temp_new_buf=new char[value_len];
if(flag)
{
strcat(temp_buf,"flag is true");
printf(temp_buf);
return 1;
}
delete[] temp_new_buf;
return 0;
}
【百度2010网页搜索产品市场部笔试题】
1.微软搜索引擎Bing的相关搜索是放在搜索结果左侧的，而百度的相关搜索是放在搜索结果下方，请分析一下，这样做各有什么优缺点，你觉得怎样设计更好?
2. 分别列出以下检索query的网页前十理想结果，需要给出每条结果的排名并阐明理由。(我觉得这几个关键词是比较实事性或随机的，所以每个时期笔试给出的检索词可能不一样。)
【百度2010非技术类笔试】
一、选择题
30道，共60分
主要是逻辑(verbal类、推理类，无数字题)和互联网商业常识(比如市场份额最大的搜索引擎)。
二、论述题
1道，40分
对推广“百度知道”产品的思路和方法。
难度不大，时间充裕。很多人提前交卷的。
【2010年百度运维部笔试及相关说明】
这次应聘的是运维部的数据库DBA，实际上运维部的所有岗位试题是一张卷子，五个简答，一个算法完善程序，一个系统设计题。
这次百度是分部门考试的，每个部门一张卷，不是像以往的好几张卷子。
由于公司的保密性以及对其他同学的公平性考虑，这里不透漏具体题目，但是可以告诉大家方向。
之前一直以为会考很多算法，后来证明是错误的
运维部的备考还是以运维岗位的需求为主题，重点不是算法，而是系统，数据库，以及简单的算法知识。
整张卷子只有一道题目要写程序，而且是比较基础的。
其他简答题里，有一道算法题，只是简答，EASY;另外有关于linux的文件系统的题，性能优化，数据库基本概念，以及硬件处理能力相关知识之类
最后的设计题，也是和运维紧密相关的，当然是数据库和系统架构知识的结合，不是很细。
希望对大家有帮助。祝考完的同学好运!
【百度2010运维部笔试题】
总共三部分7道题
第一部分·简答
1·简述树的深度优先算法、广度优先算法，及非递归实现的特点。
2·在文件系统中，元数据(比如ext2中的inode)的基本作用是什么?ext2跟ext3的根本区别是什么?
3·在web服务中，负载均衡的基本作用是什么?请举例你熟悉的一款负载均衡软件或者实现方案，简述它们的实现原理。(这题后半部分为开放性，我也没记多深，大概就这样)
4·数据库事务的四大特性是什么?请你简单举例对一个完全不懂数据库的人解释这四个特性。投数据库管理员(DBA)必答。
5·一个微型处理器，1KB内存和1MHz(每MHz运算次数为10^6)，在这样的计算机上面运行程序(程序到该终止时会自动终止，不会出现死循环)最长能运行多长时间?你可以进行任何需要的假定。
第二部分·算法和程序设计
1·int maxContinuNum(const char *inputstr,char * outputstr)
编写一段程序实现该函数，实现返回一个以“\0”结束的字符串中最长的数字串的长度，并把该数字子串的首地址赋给outputstr。不能使用任何库函数或已经存在的函数，如strlen。
例如：在字符串“abc123abcdef12345abcdefgh123456789”中，把该字符串的首地址赋给inputstr，返回9，outputstr指向字符串“123456789”的首地址。
第三部分·备份系统设计
(这题太长了，记住的不多，下面是大概的)
设计一个备份系统，要求符合三个备份场景，写出你的设计思路，框架模块设计，实现原理。
要求：1·该系统要能实现对多服务器备份工作(大概这样，还是。。)
2·该系统要具备很好容错性，不能因为多服务器中的一台出现故障儿导致整个备份工作不能进行。
3·。。。
4·。。。(这两点记不清了，不好意思)
5·具有较强的扩展性，例如当服务器内存不够时，能灵活的添加内存。
扩展性是附加，在实现前面的要求后再考虑扩展性
备份场景服务器备份网络速度 备份开始时间
场景1 a1~a1010M/S每天上午10点10分
场景2a1,b1,c1,d130M/S(忘了- -!)
四台服务器
场景3a1~a100 5M/S(也不大记得了。。)
【分享百度13日笔经】
1.简述深度优先及广度优先遍历算法，并说明非递归实现的特点
2. 程序找错，一大段。
3. 假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定性终止(非死循环)，问如何求得这台计算机上程序运行的最长时间，可以做出任何大胆的假设。
4. 大型软件有很多组件，编译时存在复杂的依赖关系，比如N1和N2存在依赖关系，要编译N1必须先编译N2,假设存在N<1000个组件，之间存在复杂的依赖关系，但不存在依赖环，问采用怎样的算法来构建编译规则，说明算法的复杂度。
5.写一个函数 int MaxContinuNum(const char *inputstr,char *outputstr)
找出一个字符串中最长的连续数字串，返回最长数字串的长度，并将最长字符串存入Outputstr指定的地址，
如， abcd1234abd123abcd123456789, 最长连续字符串为123456789，长度为9
6.有100亿个url，要求设计一个系统，能实现url的添加、删除、更新，并能查看url的内容
【百度2010商务搜索部笔试】
1，深度优先广度优先定义。它们非递归实现的特点
2，一个复数实部 虚部分别相乘求和的程序改错
3，一个有内存1KB， 处理器速度 10^6/S
最长计算时间
4， N个文件相互有倚赖(编译的时候) 设计一个算法，编译之
5，一个字符串中最长的数字子串
6，100忆个URL的存储，查找，删除，更新，添加
【百度2010笔试归来】
第一题：树的深度遍历，广度遍历，和非递归实现算法的特点。
第二题：一堆代码，找错误和潜在的危险。
第三题：一个有1kb内存和1mhz处理器的计算机在上面运行的程序的最长时间是多少
算法题目
1.包编译依赖问题，设计算法，能够最快的完成包的编译
2.对输入的字符串能够从中找到最大连续数字的字符串
系统设计题目
百度最常出的题目，如何在100万url处理path、属性等等。
2010年实习生招聘笔试题RD-混合
试卷说明：
<!--[if !supportLists]-->1. <!--[endif]-->本试卷共两套题目，请先用几分钟的时间浏览一遍，选择一套适合你的试卷进行笔试。
<!--[if !supportLists]-->2. <!--[endif]-->请在您答案的第一行标注您选择的是A卷还是B卷。
<!--[if !supportLists]-->3. <!--[endif]-->两套试卷的成绩不会合并计算，仅计算其中一套的分数。请安排好答题时间，不要两套都做而耽误时间。
A卷(共三道大题)
【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】
第一题、简答题
<!--[if !supportLists]-->1. <!--[endif]-->简要说明树的深度优先、广度优先遍历算法，及非递归实现的特点。
<!--[if !supportLists]-->2. <!--[endif]-->在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。
第二题、算法与程序设计
1.百度全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友;接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。
例如：
<小明，小王>，<小军，小王>，<小丽，小李>是队友，那么小军和小明是队友，小军和小丽不是队友。
2.给定以下二叉树:
struct node_t
{
node_t *left, *right;
int value;
};
要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);
输出以 node 为根的二叉树第 m 层的第 k 个节点值.
(level, k 均从 0 开始计数)
注意：
<!--[if !supportLists]-->1) <!--[endif]-->此树不是完全二叉树;
<!--[if !supportLists]-->2) <!--[endif]-->所谓的第K个节点，是本层中从左到右的第K个节点
第三题、系统设计题
百度打算开发一个投票系统，它提供创建、查看、参与和管理投票功能。用户创建一个投票时，有如下信息可知：创建者、标题、各选项内容、截止时间、可投票数。另外，该投票是否对所有用户可见继承于创建者的个性设置。查看一个投票时，除了显示上述信息外，还需要显示每个选项的投票数。在截止时间之前，用户可以参与投票。管理投票功能为创建者提供删除一个投票和调整进行中投票截止时间的功能。
预计该投票系统会很受用户欢迎，每天可望创建超过1万个投票。每天浏览次数达数百万，并且有约一百万人次参与投票。经验还表明，用户更喜欢新近的内容。
实习生小A针对上述需求，打算用数据库来实现这个投票系统，他给出了数据库的表设计如下：
user_info：
| uid | name | … | visible |
| 1 | “Alex Wang” | … | 1 (all) |
| 2 | “Jeff Li” | … | 0 (self) |
| vid | uid | title | options | counts | close_time | max | visible |
| 1 | 1 | “Do you like Lady Gaga?” | “Yes; No; Who?” | “4; 2; 1” | 1339071276 | 1 | 1 |
| 2 | 1 | “Who’s the best forward?” | “Messi; Ronaldo; Droba; Millito” | “912; 654; 400; 301” | 1339076234 | 1 | 1 |
问题：
1、小A的设计存在什么问题，如何改善?
2、如果想增加一个功能，即每个用户对每个投票只能投一次。如何设计?
3、系统运行了较长一段时间之后，用户反馈使用中速度变慢。请分析可能的原因，并提出解决办法。
4、请完整给出新系统下各功能的实现流程。涉及数据库查询的，请给出SQL语句。
B卷(共三道大题)
【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】
第一题、算法和程序设计题
1、请编写函数foo(int x, int y, int n) 计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少?语言仅限于PHP、C/C++、Java中的一种。
2、设计函数，输入为一个字符串，里边包含中文、英文、数字等字符，编码为GBK。中文字符的编码规则假定为：双字节组成，高字节大于0x80，低字节任意。
a) 用常用语言(c/c++/php/java)编写函数，实现功能为：按顺序提取输入文本中的中文字符，形成新的文本串返回调用者。
b) 如果调用者有时希望得到输入串的全中文内容，有时希望得到英文内容，那么该函数应如何设计。
c) 如果调用者希望获取输入串中包含中文、英文、数字这三种字符中的一种或多种的需求不定时，函数应如何设计。
3、有一个图书馆系统，含有Book和BookMaster两个类。Book可以用来设置书的属性(如title)，BookMaster每天做的事情就是根据上级的要求重设设定某些书的title，以增加借阅
者的注意力，让更多的人对书有新的兴趣。
有一天，上级需要BookMaster在setTitle的操作之前都要在日志中记录一条log。但不幸的是由于一些很特别的原因，没有办法去修改Book类，无法在Book类的setTitle()方法
中增加记录log的操作。更不幸的是上级不信任BookMaster自己的统计结果，使BookMaster不能在做setTitle()之前自己做log记录。
请问如何做才能达到目标，请写出必要的实现代码。
相关类定义如下：
public interface Book {
public void setTitle(String title);
public String getTitle();
}
public class BookException extends Exception {
public BookException() {
}
}
public class BookImpl implements Book {
private String title;
public void setTitle(String title) {
this.title = title;
}
public String getTitle() {
return this.title;
}
}
public class BookMaster {
public static void main(String[] args) {
Book book = new BookImpl();
out.println("set a book’s title today"); // 不能添加这行语句，因为上级不信任BookMaster自己的统计结果
book.setTitle("I feel good.");
out.println(book.getTitle());
}
}
注：题目中所提供类的定义为Java实现，但您可以根据您的喜好自由选择其它语言完成题目要求。
第二题、简答题
1、网站如何维护用户的登录状态?百度知道、百度贴吧、百度百科三个网站域名不同，但同在.baidu.com主域下，它们之间如何共享用户登录状态?如果两个网站域名也不在一个主域下，例如www.baidu.com和www.qiyi.com，那么要如何共享用户登录状态?
要求：请尽量提供多种方案并分析各种方案的优劣。
2、在炎炎夏日，你十分口渴，想要买一瓶冰汽水，商店中有三瓶汽水供你选择(如ABC)，其中只有一瓶是冰过的。当你选定了其中的某一瓶后(设为A)，店员摸了下剩余两瓶中的一瓶(设为B)，并告诉你B不是冰的，此时你会将你的选择变更为剩余的那瓶嘛(C)?请详述你的理由?
3、TCP服务器在启动时，需要经过socket、bind、listen和accept四个步骤。
一个单进程的服务器的伪代码如下：
01. listen_fd = socket(TCP);
02. bind(listen_fd, my_addr);
03. listen(listen_fd, backlog);
04.
05. while(true)
06. {
07. client_fd = accept(listen_fd);
08. read(client_fd, request);
09. response = process(request);
10. write(client_fd, response);
11. close(client_fd);
12. }
某客户端的伪代码如下：
13. fd = connect(server_addr);
14. write(fd, request);
15. read(fd, response);
16. display(response);
17. close(fd);
假设服务器在04行执行了sleep(1000000)：
问题1：请简介服务器四个步骤的意义或作用是什么?
问题2：当1个客户端访问该服务器时，客户端执行到哪行会失败?会发生阻塞吗?为什么?
问题3：当50个客户端从50台机器几乎同时访问该服务器时，各个客户端的反应有差别吗?为什么?(注：忽略防火墙因素)
第三题、系统设计题
1、假设系统里有很多模板文件，每个模板文件都有一个唯一的文件名，其内容是一个长字符串，其中包含很多通过$...$方式标记起来的模板变量，如：
my name is $spname$, i’m $spage$ years old ...
其中spname, spage就是我们所谓的模板变量，请设计一个简单高效的模板解析系统，要求上游模块向该系统提供一个模板文件名和一个模板变量值字典时，
系统能够返回经过模板变量解析后的文本内容，例如：
假设模板文件A.tpl的内容为：
my name is $spname$, i’m $spage$ years old ...
提供的模板变量值字典dict为：
array(’spname’ => ’robin928’, ’spage’ => ’29’)，
则解析后的文本内容应该为：
my name is robin928, i’m 29 years old ...
(访问字典时可以通过dict[’spname’]访问到模板变量spname的参数值)
2、目前最流行的, 被称为微革命的互联网应用Twitter中, 人民可以在Twitter中互相关注, 被关注的人发出的每一条微型博客(一般都在140字以内), 都会被关注他的人看到. 而一个人可能被几万,几十万, 甚至上百万的人关注; 当然, 理论上, 一个人也可以关注几万,几十万,甚至上百万的人.
1) 请设计出这样的一个系统, 并详细说明你的设计.
2) 请指出你设计中的缺点, 并给出改进后的设计.
3) 请评述你的最终设计的优点和缺点.
• 您可先离线完成所有答案，再把整份答案内容剪贴到这里;所有内容都将以.txt文件格式保存。
• 如果您长时间未进行任何操作，答题页面可能会超时失效;若失效请重新登录，以防止提交失败。
• 请务必在笔试时间结束前提交您的答案，以保证我们能及时处理。
• 答案一旦提交成功，则您的笔试结束，您将不能继续提交答案。
答题区(请在下边文本区域填写答案)
答案附件: (500K以内，可以为doc,zip,pdf,jpg文件)
©2009 Baidu 使用百度前必读
B卷
第一题、算法和程序设计题
2(a)读取中文
public static String getChinese(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
return desc;
}
2(b)读取中文或英文
public class GetPart {
public static final int CHINESE=1;
public static final int ENGLISH=2;
/**
* @param src
* @param type 当type为CHINESE,得到中文,当type为ENGLISH时,得到英文
* @return
* @throws UnsupportedEncodingException
*/
public static String getPart(String src,int type)throws UnsupportedEncodingException{
if(type==CHINESE){
return doGetChinese(src);
}else if(type==ENGLISH){
return doGetEnglish(src);
}else {
throw new IllegalArgumentException("参数type应该为1,2,3");
}
}
private static String doGetEnglish(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length==1 && Character.isLetter(ch)){
desc+=ch;
}
}
return desc;
}
private static String doGetChinese(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
return desc;
}
public static void main(String[] args) throws UnsupportedEncodingException {
System.out.println(getPart("123你好ok",ENGLISH));
}
}
2(c)可以同时读取任意的文本
public class GetPart {
public static final int CHINESE=0x1;
public static final int ENGLISH=0x2;
public static final int DIGIT=0x4;
/**
* @param src
* @param type 当type为CHINESE,得到中文,当type为ENGLISH时,得到英文
* @return
* @throws UnsupportedEncodingException
*/
public static Result getPart(String src,int type)throws UnsupportedEncodingException{
Result result=new Result();
if((type & CHINESE) == CHINESE){
result.setChinese(doGetChinese(src));
}
if((type & ENGLISH) == ENGLISH){
result.setEnglish(doGetEnglish(src));
}
if((type & DIGIT) == DIGIT){
result.setDigit(doGetDigit(src));
}
return result;
}
private static String doGetDigit(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length==1 && Character.isDigit(ch)){
desc+=ch;
}
}
return desc;
}
private static String doGetEnglish(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length==1 && Character.isLetter(ch)){
desc+=ch;
}
}
return desc;
}
private static String doGetChinese(String src) throws UnsupportedEncodingException {
String desc="";
for (int i = 0; i < src.length(); i++) {
char ch=src.charAt(i);
byte[] buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
return desc;
}
public static void main(String[] args) throws UnsupportedEncodingException {
Result result=getPart("123你好ok",CHINESE|ENGLISH|DIGIT);
System.out.println(result.getChinese());
System.out.println(result.getEnglish());
System.out.println(result.getDigit());
}
}
public class Result {
private String chinese;
private String english;
private String digit;
public Result() {
}
public String getChinese() {
return chinese;
}
public void setChinese(String chinese) {
this.chinese = chinese;
}
public String getEnglish() {
return english;
}
public void setEnglish(String english) {
this.english = english;
}
public String getDigit() {
return digit;
}
public void setDigit(String digit) {
this.digit = digit;
}
}
3.
答:很多方法能解决这个问题.第一:用动态代理为Book生成个代理.
第二:用设计模式的代理设计模式完成.
第三:用spring的aop.
这里我们选用设计模式的方式:
class BookProxy implements Book{
private Book target;
public BookProxy(Book target) {
this.target = target;
}
public String getTitle() {
return target.getTitle();
}
public void setTitle(String title) {
System.out.println("set a book’s title today");//增加的日志信息
target.setTitle(title);
}
}
class BookMaster {
public static void main(String[] args) {
Book book = new BookImpl();
book=new BookProxy(book);
book.setTitle("I feel good.");
}
}
第三题、系统设计题
1。模板解析
答:因为模板文件的内容比较长,不能用正则表达式,这样的效率很低.
因为模板变量有明确的标志${}.那么一遍全文查找就可以了.遇到${,就开始记录便利,遇到}就读取了变量var,那么查字典dict['var'],就能得到其值,然后填充在里面.
特别需要说明:字典用散列表建立,这样效率很高.
伪代码:
public class TemplateUtil {
/**字典*/
private final static Map
static{
//初始化字典
}
/**
* 替换模板变量
* @param source
* @return
*/
public static String replace(String source){
StringBuffer sb=new StringBuffer();
for (int i = 0; i < source.length(); i++) {
char ch=source.charAt(i);
if(ch=='$'&& (i+1)
i+=2;
String var="";
while(i
var+=source.charAt(i);
i++;
}
sb.append(dict.get(var));
}else{
sb.append(ch);
}
}
return sb.toString();
}
}
相关文章：
2.
4.华为近年的笔试题