1：堆和栈的区别，什么时候用堆什么时候用栈？
2：树的深度优先搜索算法
按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠钻迷宫老鼠遇到死胡同）则退
回头另选通路继续搜索，直到找到条件的目标为止。
3：广度优先搜索算法
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多
重要的图的算法的原型。Prim 最小生成树算法采用了和宽度优先搜索类似的思想。其别名
又叫 BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。
4：树的非递归实现
5：数据库事务的四大特性
原子性 atomic、一致性 consistency、分离性 isolation、持久性 durability
◎事务的原子性指的是，事务中包含的程序作为数据库的逻辑工作单位，它所做的对数据修
改操作要么全部执行，要么完全不执行。这种特性称为原子性。
◎事务的一致性指的是在一个事务执行之前和执行之后数据库都必须处于一致性状态。
◎分离性指并发的事务是相互隔离的。即一个事务内部的操作及正在操作的数据必须封锁起
来，不被其它企图进行修改的事务看到。
◎持久性意味着当系统或介质发生故障时，确保已提交事务的更新不能丢失。即一旦一个事
务提交，DBMS 保证它对数据库中数据的改变应该是永久性的，耐得住任何系统故障。
持久性通过数据库备份和恢复来保证。
6：ASCII 码--十进制（对应关系）
0--48 9--57
A--65 Z--90
a--97 z—122
十进制：decimal，简称：DEC
7：算法与程序设计题
#include <iostream>
using namespace std;
//该函数实现返回一个以“\0”结束的字符串中最长的数字串的长度，
//并把该数字子串的首地址赋给outputstr
//不能使用任何库函数或已经存在的函数，如strlen。
//例如：在字符串“abc123abcdef12345abcdefgh123456789”中，
//把该字符串的首地址赋给inputstr，函数返回，
//outputstr指向字符串“”的首地址。
int maxContinuNum(const char
inputstr,const char outputstr)
{
int max=0,count=0;
while(
inputstr!='\0') //如果字符串没有到末尾，继续循环{ if(inputstr>=49 &&
inputstr<=57) //如果在统计范围内{ count++; }else //如果在统计范围外{ if(count>max){ max=count;outputstr=inputstr-count; //返回最大数字子串的首地址对应的数字count=0;}else{ count=0;}}inputstr++;}if(inputstr=='\0') //特殊情况，最长字符串在末尾
{
max=count;
outputstr=inputstr-count; //返回最大数字子串的首地址对应的数字
}
cout<<"返回最大数字子串的首地址对应的数字："<<
outputstr<<endl;return max;}int main(){ int max;char str="abc123abcdef12345abcdefgh123456789";
max=maxContinuNum(str,str);
cout<<"字符串“abc123abcdef12345abcdefgh123456789”中最长的数字串的长度为："<<max<<endl;
}
8：New Coke 的一项失败营销方略
始于可口可乐与百事可乐之争的。这是商业史上的著名案例，很多人曾经从不同角度分析这
个案例。而在 blink 书中，两种可乐在做产品比较时采取了错误的“切片”方法。百事在最初
***可口时，曾经通过在大街上随即抽取人员作双盲测试，并发现大多数人认为百事可乐更
好喝，以此为证据说明百事的优点。可口也作了同样的测试，惊恐的发现事实确实如此。于
是他们断定可口可乐必须在产品上改进，经过大量的投入，一种新的New Coke发布出来了。
New Coke 在做同样的双盲测试时，更多人认为 New Coke 比 Pepsi 好喝。当时的 CEO 郭思
达在发布时说，这是可口可乐有史以来做的最有把握的一件事。可是，事实是，New Coke
迅速被消费者抵制，最后可口可乐不得不重新推出原来的可口可乐并完全摒弃 New Coke。
这种双盲测试是一种错误的切片方法，因为在做这种试验时，用户对每种饮料都只喝一小口，
而不是像正常时一次喝一瓶。而当用户只喝一小口饮料时，大多数人会更喜欢更甜的那一种
——虽然当他们喝一整瓶的时候会有不同的看法。书中又举了更多例子说明，所谓的用户测
试并不是一种能够让你相信的结果，因为用户测试会被很多不同的因素所影响，包括包装、
饮用方法。
9：链表和数组的优缺点？
链表：链表是一块不连续的动态空间，长度可变；链表需要按顺序检索节点，效率低；
链表的优点是可以快速插入和删除节点，大小动态分配，长度不固定。
链表不存在越界问题。
数组：数组是一快连续的空间，声明时长度就需要固定。
数组的优点是速度快，数据操作直接使用偏移地址。
数组有越界问题。
2008-9-24 百度电子科技大学网络工程师笔试题(第五套笔试题)
第一大题，共 6 小题，每题 5 分，共 30 分
1:什么是保留 IP 地址,请列举?为什么规定保留 IP 地址?
保留 IP 地址：1 个 A 类地址 10.
..
；16 个 B 类地址 172.16..
---172.31..
256 个 C 类地址 192.168.0.---192.168.255.
；保留 IP 地址不会在 internet 网上出现，用于企业网络，A 企业可以用,B 企业也可以使用！2:IPv4 和 IPv6 的地址分别是多少？IPv4 的地址是 32 位，IPv6 的地址是 64 位。3:什么是访问控制列表?它的执行流程?访问控制列表（ALC）实际上就是一系列允许和拒绝匹配准则的集合。总的一句话就是数据包与 ALC 中的一旦出现的匹配情况，就执行相应的操作，而此时对此数据包的检测就到此为止了，后面不管出现多少不匹配的情况将不作检测。4:802.1Q 协议实现什么功能?和 ISL 有何区别5:端口镜像,链路汇聚的功能是什么,请用你熟悉的交换机写出它们的命名。6:linux 下解释: ip rule add from 192.168.3.112/32 [tos 0x10] table 2 pref 1500第二大题，30 分你现在有一个文件，文件中顺序存有 N 个记录，R1,R2,...,RN,这些记录不是有序的，但是你知道一个整数 M,这些记录满足 R1<R2<...<RM 以及 RM+1<RM+2<...RN.1,设计一个算法或编写一个程序，将文件中的记录排序为 R1',R2',...,RN',算法或程序读取文件的次数为 O(N),不限内存使用，2,设计一个算法或编写一个程序，将文件中的记录排序为 R1',R2',...,RN',算法或程序读写文件的次数为 O(N)，空间复杂度为 O(1)，亦即，你使用的内存大小和 M,N 均无关。第三大题，每小题 20 分，共 40 分1：在某些情况下，网络中会出现路由环路，请根据你的理解，说明可能出现路由环路的原理，并以你最熟悉的路由协议，说明该路由协议采取了哪些措施避免路由环路。2：如果用户向你申述上百度主页很慢，你会从哪些方面取分析这个问题，如何高效的分析并判断故障根源所在？第四套题的第三大题的第一个现在需要对 2000 台机器升级某个软件？已经有这个软件的最新代码，1：你会选择用什么工具自动升级该软件？请给出具体步骤或方法？2：为了便于后期的运维，如果让你设计一套软件部署方案，你会怎么设计？1、请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。数据结构为：typedef struct_TreeNode{ char c;TreeNode leftchild;
TreeNode
rightchild;}TreeNode;函数接口为：int CompTree(TreeNode tree1,TreeNode
tree2);注：A、B 两棵树相等当且仅当 Root->c==RootB-->c,而且 A 和 B 的左右子树相等或者左右互换相等。2、写一段程序，找出数组中第 k 大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在 4。第二大、第三大的数都是 4，位置在 1、3 随便输出哪一个均可。函数接口为：int find_orderk(const int narry,const int n,const int k)
2'、已知一个字串由 GBK 汉字和 ansi 编码的数字字母混合组成，编写 c 语言函数实现从中去掉所有 ansi
编码的字母和数字(包括大小写),要求在原字串上返回结果。
函数接口为：int filter_ansi(char* gbk
string)注：汉字的 GBK 编码范围是 0x8140-0xFEFE百度笔试题1）此题 10 分对任意输入的正整数 N，编写 C 程序求 N!的尾部连续 0 的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续 0 的个数是 3。（不用考虑数值超出计算机整数界限的问题）2）此题 10 分编写一个 C 语言函数，要求输入一个 url，输出该 url 是首页、目录页或者其他 url 如下形式叫做首页：militia.info/ www.apcnc.com.cn/ www.800cool.net/ 如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/ 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 A9.使用 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 分别排序，并请指出排序过程中可能会遇到的哪些问题 如何提高效率 例如： 以及 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 类
型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以
忽略），并且签名分布足够均匀。
请描述你的数据结构 内存如何申请 增、删、查、改的功能如何实现 如果操作很频繁，该
如何优化
取 自
"
%E9%A2%98
一、选择题：15 分 共 10 题
- 在排序方法中，关键码比较次数与记录地初始排列无关的是：A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
- 以下多线程对 int 型变量 x 的操作，哪几个需要进行同步：A. x=y; B. x++; C. ++x; D. x=1;
- 代码void func(){ static int val;„}中，变量 val 的内存地址位于：A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
- 同一进程下的线程可以共享以下：A. stack B. data section C. register set D. thread ID
- 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
- short a[100]，sizeof(a) 返回A. 2 B. 4 C. 100 D. 200 E. 400
- 以下哪种不是基于组件的开发技术_____。A. XPCOM B. XP C. COM D. CORBA
- 以下代码打印的结果是（假设运行在 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
- STL 中的哪种结构是连续形式的存储：A. map B. set C. list D. vector
- 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是：A. EDCBA B. DECBA C. DCEAB D. ABCDE二、简答题：20 分，共 2 题
- （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
- （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" };45 if( flag & 0x10000 ) 6 copy = 1;7 index = ( flag & 0x300000 ) >> 20;89 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 } else16 errstr = __err + index;17 }1819 void f2( int c ) { 20 char err;2122 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 题注意：要求提供完整代码，如果可以编译运行酌情加分。
- 求符合指定规则的数。给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。 输出：13„四、设计题：35 分 共 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_ID3) 添加一个新的 SONG_ID4) 给定一个 URL_ID，将其置为不可用限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理 百度第二套
一、选择题：15 分 共 10 题
- 已知一个线性表(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.3F. 7/6 G. 4/3 H. 3/2
- 需要将 OS 缓冲区的数据刷新到硬盘，可以调用的函数有(多选)：A.fflush() B. fsync() C. sync() D.writev()
- 下面哪个 shell 语句不能打印出用户主目录的路径A. echo "$HOME" B. echo ~C. echo
$HOME D. echo $HOME - 最坏情况下，合并两个大小为 n 的已排序数组所需要的比较次数A.2n B.2n-1 C.2n+1 D.2n-2
- 一个 B 类网的子网掩码是 255.255.240.0，这个子网能拥有的最大主机数是：A. 240 B. 255 C.4094 D. 65534
- 以下代码执行后，val 的值是___:unsigned long val = 0;char a = 0x48;char b = 0x52;val = b << 8 | a;A 20992 B 21064 C 72 D 0
- 内存的速度远远高于磁盘速度，所以为了解决这个矛盾，可以采用：A 并行技术 B 虚存技术 C 缓冲技术 D 通道技术
- 以下代码打印的结果是（假设运行在 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 114C 120 D 1112
- 同一进程下的线程可以共享以下A. stack B. data sectionC. register set D. thread ID
- 以下哪种操作最适合先进行排序处理A 找最大、最小值 B 计算算术平均值C 找中间值 D 找出现次数最多的值二、简答题：20 分，共 2 题
- （6 分）下面是一个 http 请求：GET /baidu/blog/item/6605d1b4eb6433738ad4b26d.html HTTP/1.1Host: hi.baidu.comUser-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; zh-CN; rv:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,/;q=0.5Accept-Language: zh-cn,zh;q=0.5 Accept-Encoding: gzip,deflateAccept-Charset: gb2312,utf-8;q=0.7,*;q=0.7Keep-Alive: 300Connection: keep-aliveReferer: Cookie: BAIDUID=AFB70E986AC48B336ABAB7505CDD1C76;请解释以下各字段基本含义：Host、User-Agent、Accept-Charset、Connection、Referer、Cookie
- （14 分）函数 A 将字符串 str1 转成小写，并打印出转化前后的字符串。另外，改错时不能改变函数的接口和主要思路。改错时，请指出行号。1 #include 2 #include 345 char str1 = "ABDFLjlero 我们都是 saf";67 char ToLower(char s[])8 { 9 static size_t i=sizeof(s);1011 for (i; i>=0; i--) { 12 if (s>"A" && s<"Z") { 13 s += 26;14 }15 }16 return s;17 }1819 int A()20 { 21 printf("old str[%s] after lower[%s]n", str1, ToLower(str1));22 }三、编程题：30 分 共 1 题注意：要求提供完整代码，如果可以编译运行酌情加分。
- 两个已排序的整型数组，求交集，最快算法输入：两个已排序的整型数组（int a[m], b[n]）输出：两个数组的交集四、设计题：35 分 共 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.vFF : bananaFA : apple2.vFA: 苹果FF : 香蕉则生成文件为1.rThis is an banana $$. I like banana and apple。2.rThis 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/ www.800cool.net/ 如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/ 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.处理以下文件内容,将域名取出并进行计数排序,如处理: 得到如下结果: 域名的出现的次数 域名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）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。11 题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<N;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排序的时间复杂度可以达到 nlog(n)然后对于元素在其他集合中查找，最坏情况下为（n-1）m查找一个集合是否与其他集合有交集的最坏情况是 mm(n-1)合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为 O(mmnn)需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。(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 分别排序，并请指出排序过程中可能会遇到的哪些问题？如何提高效率？例如： 以及 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 题
- 在排序方法中，关键码比较次数与记录地初始排列无关的是 . A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
- 以下多线程对 int 型变量 x 的操作，哪几个需要进行同步：A. x=y; B. x C. x; D. x=1;
- 代码void func() { static int val; … } 中，变量 val 的内存地址位于：A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
- 同一进程下的线程可以共享以下A. stack B. data section C. register set D. thread ID
- 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
- short a[100]，sizeof(a)返回？A 2 B 4 C 100 D 200 E 400
- 以下哪种不是基于组件的开发技术_____。A XPCOM B XP C COM D CORBA
- 以下代码打印的结果是（假设运行在 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
- STL 中的哪种结构是连续形式的存储A map B set C list D vector
- 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是（ ）A、EDCBA； B、DECBA； C、DCEAB； D、ABCDE 二、简答题：20 分，共 2 题
- （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
- （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 题注意：要求提供完整代码，如果可以编译运行酌情加分。
- 求符合指定规则的数。给定函数 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 题注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
- 假设一个 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) 给定一个 URLID，将其置为不可用限制条件：内存占用不超过 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 ***cStr) { char sDest= NULL; if( 1) { int j; sLen = strlen(***cStr); sDest = new [__2]; if(sDest == NULL) return NULL; sDest[sLen] = '\0'; while(_3) sDest[sLen] = toLowerChar(***cStr[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/www.800cool.net/如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/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.83.以下的 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,14.假设局域网中子网掩码是 255.255.0.0，那么在这个局域网中哪些 IP 地址是可用的?()A.192.168.0.0 B.192.168.0.1 C.192.168.255.1 D.192.168.255.2555.给定数列(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.537.93486781634*22349659874=_____6(30 秒)8.在 Linux 系统中，对命令“In file 1 file2”描述正确的是?()A.建立软链接 file1,并指向 file2B. 建立硬链接 file1,并指向 file2C. 建立软链接 file2,并指向 file1D. 建立硬链接 file2,并指向 file19.在 Shell 编程中，下面哪个表示上一步所运行程序的返回值?()A. $#B. $(后一字符打不出来可以描述一下„S 下面在加一点‟)C. $&D. $!编程和测试设计题(2 道)(一) 简述：实现一个函数，对一个正整数 n,算得到 1 需要的最少操作次数：如果 n 为偶数，将其处以 2; 如果 n 为奇数，可以加 1 或减 1; 一直处理下去。例子：ret = func(7);ret = 4,可以证明最少需要 4 次运算n = 7n—6n/2 3n/2 2n++ 1要求：实现函数(实现尽可能高效)Int func(unsign int n);n 为输入，返回最小的运算次数。给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。请列举测试方法和思路(二) 简述：IP 防火墙Security 公司的网络管理工程师 Mr. leak 最近发现有不少来自公司外部 IP 的请求，试图非法访问公司内部资源，为了不影响数据访问流程。他不得不写一个高效的程序——一个工作在 Ipv4 上的防火墙，如果请求来自非授权的 ip 地址，则将请求丢弃。为了便于管理，通过文本文件 IP.TXT 来配置授权的 IP 地址，文件格式为每行(‟/n‟)一个 IP 地址(或 IP 段)，范围不超过一个 B 类。例如：162.105.91.16359.66.105.0 59.66.105.255211.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/ www.800cool.net/ 如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/ 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 排序的时间复杂度可以达到 nlog(n) 然后对于元素在其他集合中查找，最坏情况下为（n-1）m 查找一个集合是否与其他集合有交集的最坏情况是 mm(n-1) 合并的时间复杂度不会超过查找集合有交集的最坏情况。所以最终最坏时间复杂度为 O(mmn*n) 需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。(3)可能的改进：首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。取 自"1%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/ www.800cool.net/ 如下形式叫做目录页：thursdaythree.net/greenhouses--gas-global-green-house-warming/ 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 亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。取 自"%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(voidptr)：释放 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) 改进 - { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合要求把交集不为空的集合并起来,如上例会得到 { aaa, bb, ccc, dd, ff }, {gg}(1) 思想 (2) 算法及复杂度 (3) 改进取 自"05.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 分别排序，并请指出排序过程中可能会遇到的哪些问题？如何提高效率？例如： 以及 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 类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以忽略），并且签名分布足够均匀。请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁，该如何优化？取 自"%98.htm"、、、、、、、、、、、、、、、、、、、、、、、、、、经过在线笔试、两轮电话面试，今天上午收到了百度的拒信，我的百度求职算是告一段落了…… 从百度校园招聘开始，我就投了一份简历。在别人都有在线笔试机会的时候，我却没有任何消息。听说师兄可以给推荐，我就又通过内部推荐的方式投递了一次，这次很快就有消息了——拒信。那时基本上就放弃了百度。可是大概 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 是存储在什么地方，以什么形式存储的。百度川大站笔试题技术类试卷一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 分钟，再好好想想，偶又憋了半天，还是没想出好的办法，基本上没题都要问一遍，偶实在答不出来了，他说时间不够了，算了，终于长舒了一口气，然后就问了些做过的项目，终于轻松一些了，偶就老老实实做了什么就说什么了，二面是技术经理，就是网上鼎鼎有名的齐玉杰，见到真人后，看起来非常亲切，不知道为什么心情就放松起来了，接下来就聊了聊项目，还有对搜索的看法，还重点文了搜索算法的思路９是没答上来?( 不过齐 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 年的第一道图形推理题，不过我不知道正确答案，知道的童鞋请帮忙告诉一声，我选的 C2、还是往年论坛上有的非技术题，只是换了下字，分析 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 的相关搜索是放在搜索结果左侧的，而百度的相关搜索是放在搜索结果下方，请分析一下，这样做各有什么优缺点，你觉得怎样设计更好？
- 分别列出以下检索 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.简述深度优先及广度优先遍历算法，并说明非递归实现的特点
- 程序找错，一大段。
- 假设有一台迷你计算机，1KB 的内存，1MHZ 的 cpu，已知该计算机执行的程序可出现确定性终止（非死循环），问如何求得这台计算机上程序运行的最长时间，可以做出任何大胆的假设。
-
大型软件有很多组件，编译时存在复杂的依赖关系，比如 N1 和 N2 存在依赖关系，要编
译 N1 必须先编译 N2,假设存在 N<1000 个组件，之间存在复杂的依赖关系，但不存在依赖环，问采用怎样的算法来构建编译规则，说明算法的复杂度。5.写一个函数 int MaxContinuNum(const char inputstr,char outputstr)找出一个字符串中最长的连续数字串，返回最长数字串的长度，并将最长字符串存入Outputstr 指定的地址，如， abcd1234abd123abcd123456789, 最长连续字符串为 123456789，长度为 96.有 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、属性等等。其他笔试经验：昨晚监考百度技术类考试的感想 2008.10.17 09.10.18 百度商业产品部笔试归来~~~真题奉献~ 百度 2010 年校园招聘软件测试笔试题百度笔试-2009.10.18 百度 2010 校招运维部门笔试百度 09 年 10 月 18 号的交大笔试题——质量部09 年 10 月 18 日百度商务搜索笔试题09 年 10 月 18 号百度北京管培笔试09 年 10 月 18 日百度产品市场部笔试题型09.10.18 百度商业应用产品部（非技术类）笔试题目2009.10.18-百度质量部笔试试题09 年 10 月 18 号 RD-2 卷（质量部等）笔试真题百度 08-9-24 成都电子科技大学笔试题(第五套) 百度 08-9-24 成都电子科技大学笔试题(第四套-网工) 百度 08-9-24 成都电子科技大学笔试题(第一套) 2009 校园招聘 NS 试题百度 08-9-24 成都电子科技大学笔试题(第三套) 百度 08-9-24 成都电子科技大学笔试题(第二套) 昨晚百度的笔试题(市场部) 2007.10.23 百度笔我的题目 2007.05.29 baidu 非技术类一道笔试题baidu 2007 校园招聘电子商务软件笔试题百度商业应用产品部笔试真题 2007.09.14 2007 年百度招聘在线笔试真题解答百度往年实习面试经验及体会百度日文产品部实习两周分享 09-09 百度系统部实习面试-2009.6.17 百度搜索新产品研发部实习一面面经-2009.6.17 百度实习面试-2009.6.16 百度往年校园招聘面试经验分享众里寻他签百度--从网申到 OFFER（搜索引擎产品市场部-产品设计师-武汉）在百度 SEARCHPM 做实习生经历北京?百度?互联网产品经理助理?2007-04-25 我也来 88 我所经历的百度SuperHR 找工作需要积极的心态【关于百度之争】产品设计师终面（武汉）百度面试趣味见闻【面经】百度最后的电面！热呼呼的新鲜出炉百度质量部面经-2009.10.19 百度质量部一面热乎的面经-2009.10.22 百度质量部一面面经-2009.10.22 百度产品类（非技术）面经分享 -2009.7.14 百度-搜索应用部-面经+笔经 -2007.9.26 北京-百度系统部面试归来 -2009.6.18 写写百度的事sniper·找工之路·百度篇Suth_Job hunting_百度篇百度 Ecom 二面 2007.10.27 百度电面 2007.10.26 百度二面归来 2007.10.25 百度一面归来 2007.10.25 发滚烫的百度一面面经 2008.09.23 尘埃落定，回顾我的漫漫求职路（4）Baidu 篇分享百度一二面经历 以纪念第一个 offer 2007.09.15 发下午的百度软件质量部面经 2007.10.24 百度软件质量部测试工程师面经 2007.10.24 开始答题
提醒：请注意分配各个部分的答题时间本次在线笔试答题已过时间： 0 小时 06 分 22 秒 剩余时间： 1 小时 53 分 38 秒题目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 … visible1 “Alex Wang” … 1 (all)2 “Jeff Li” … 0 (self)vote_info：vid uidtitle options counts close_time max visible1 1 “Do you like “Yes; No; Who?” “4; 2; 1” 1339071276 1 1Lady Gaga?”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 四个步骤。一个单进程的服务器的伪代码如下： - listen_fd = socket(TCP);
- bind(listen_fd, my_addr);
- listen(listen_fd, backlog);
-
- while(true)
- {
- client_fd = accept(listen_fd);
- read(client_fd, request);
- response = process(request);
- write(client_fd, response);
- close(client_fd);
- }某客户端的伪代码如下：
- fd = connect(server_addr);
- write(fd, request);
- read(fd, response);
- display(response);
- 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 文件) 提交答案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;}}
-
答:很多方法能解决这个问题.第一:用动态代理为 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<String,String> dict=new HashMap<String, String>();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)<source.length() && source.charAt(i+1)=='{'){ i+=2;String var="";while(i<source.length()&&source.charAt(i)!='}'){ var+=source.charAt(i);i++;}sb.append(dict.get(var));}else{ sb.append(ch);}}return sb.toString();}}1912 制作试卷说明：<!--[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 开始计数) 注意：此树不是完全二叉树；所谓的第 K 个节点，是本层中从左到右的第 K 个节点第三题、系统设计题百度打算开发一个投票系统，它提供创建、查看、参与和管理投票功能。用户创建一个投票时，有如下信息可知：创建者、标题、各选项内容、截止时间、可投票数。另外，该投票是否对所有用户可见继承于创建者的个性设置。查看一个投票时，除了显示上述信息外，还需要显示每个选项的投票数。在截止时间之前，用户可以参与投票。管理投票功能为创建者提供删除一个投票和调整进行中投票截止时间的功能。预计该投票系统会很受用户欢迎，每天可望创建超过 1 万个投票。每天浏览次数达数百万，并且有约一百万人次参与投票。经验还表明，用户更喜欢新近的内容。实习生小 A 针对上述需求，打算用数据库来实现这个投票系统，他给出了数据库的表设计如下：user_info：uid name … visible1 “Alex Wang” … 1 (all)2 “Jeff Li” … 0 (self)vote_info：vid uidtitle options counts close_time max visible1 1 “Do you like Lady Gaga?”“Yes; No; Who?” “4; 2; 1” 1339071276 1 12 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 的概率是多少？2、设计函数，输入为一个字符串，里边包含中文、英文、数字等字符，编码为 GBK。中文字符的编码规则假定为：双字节组成，高字节大于 0x80，低字节任意。a) 用常用语言（c/c++/php/java）编写函数，实现功能为：按顺序提取输入文本中的中文字符，形成新的文本串返回调用者。b) 如果调用者有时希望得到输入串的全中文内容，有时希望得到英文内容，那么该函数应如何设计。c) 如果调用者希望获取输入串中包含中文、英文、数字这三种字符中的一种或多种的需求不定时，函数应如何设计。第二题、简答题1、网站如何维护用户的登录状态？百度知道、百度贴吧、百度百科三个网站域名不同，但同在.baidu.com 主域下，它们之间如何共享用户登录状态？如果两个网站域名也不在一个主域下，例如 www.baidu.com 和 www.qiyi.com，那么要如何共享用户登录状态？要求：请尽量提供多种方案并分析各种方案的优劣。(1) 如果在同一域下,可以用 cookie 共享方式实现.在服务器把 cookie 信息写到 response 时,需要加密.当服务器读取 cookie 时,需要解密.(2) 如果在不同的域,可用一个服务器群集来存放用户的登录信息.当需要 session 信息,直接到服务器群集去取得.注：Cookie：Cookie 是由服务器端生成，发送给 User-Agent（一般是浏览器），浏览器会将 Cookie的 key/value 保存到某个目录下的文本文件内，下次请求同一网站时就发送该 Cookie 给服务器（前提是浏览器设置为启用 cookie）。Cookie 名称和值可以由服务器端开发自己定义。Cookie 记录着用户的帐户 ID、密码之类的信息，如果在网上传递，通常使用的是 MD5方法加密。Cookie 欺骗：截获 Cookie 的人不需要知道这些字符串的含义，他们只要把别人的 Cookie 向服务器提交，并且能够通过验证，他们就可以冒充受害人的身份，登陆网站。这种方法叫做 Cookie欺骗。服务器群集技术：最主要的应用即在于网络负载平衡的功能。群集由通过输入/输出系统互联的若干服务器构成。Session：会话在计算机中，尤其是在网络应用中，称为“会话”。 Session 是指一个终端用户与交互系统进行通信的时间间隔，通常指从注册进入系统到注销退出系统之间所经过的时间。具体到 Web 中的 Session 指的就是用户在浏览某个网站时，从进入网站到浏览器关闭所经过的这段时间，也就是用户浏览这个网站所花费的时间。因此从上述的定义中我们可以看到，Session 实际上是一个特定的时间概念。2、在炎炎夏日，你十分口渴，想要买一瓶冰汽水，商店中有三瓶汽水供你选择（如 ABC），其中只有一瓶是冰过的。当你选定了其中的某一瓶后（设为 A），店员摸了下剩余两瓶中的一瓶（设为 B），并告诉你 B 不是冰的，此时你会将你的选择变更为剩余的那瓶嘛（C）？请详述你的理由？答:若 A 已经是冰的，那就不用选择 C；若 A 不是冰的，并且店员已经确认 B 不是冰的，所以只有 C 是冰的。3、TCP 服务器在启动时，需要经过 socket、bind、listen 和 accept 四个步骤。一个单进程的服务器的伪代码如下：
- listen_fd = socket(TCP);
- bind(listen_fd, my_addr);
- listen(listen_fd, backlog);
-
- while(true)
- {
- client_fd = accept(listen_fd);
- read(client_fd, request);
- response = process(request);
- write(client_fd, response);
- close(client_fd);
- }某客户端的伪代码如下：
- fd = connect(server_addr);
- write(fd, request);
- read(fd, response);
- display(response);
- close(fd);假设服务器在 04 行执行了 sleep(1000000)：问题 1：请简介服务器四个步骤的意义或作用是什么？答:socket：是建立套接字.Bind：是让建立的套接字指定到具体的网络接口（如果一个机器有多个网络接口)和端口号.Listen：监听客户端的请求Accept：如果有请求到来,accept 返回一个客户端套接字.此时可以通信了.问题 2：当 1 个客户端访问该服务器时，客户端执行到哪行会失败？会发生阻塞吗？为什么？问题 3：当 50 个客户端从 50 台机器几乎同时访问该服务器时，各个客户端的反应有差别吗？为什么？（注：忽略防火墙因素）答:有差别,因为没有用多个线程或者多进程技术,那么 50 个请求会放在操作系统的队列里面.每一次只能处理一个请求,1,2，...,50 等待时间各不相同.也许后面的会因为超时重传.建议换成多线程技术来处理,也可以用非阻塞 IO 来处理.那么用户的体验没有那么差.2、目前最流行的, 被称为微革命的互联网应用Twitter中, 人民可以在Twitter中互相关注, 被关注的人发出的每一条微型博客(一般都在 140 字以内), 都会被关注他的人看到. 而一个人可能被几万,几十万, 甚至上百万的人关注; 当然, 理论上, 一个人也可以关注几万,几十万,甚至上百万的人.1) 请设计出这样的一个系统, 并详细说明你的设计.2) 请指出你设计中的缺点, 并给出改进后的设计.3) 请评述你的最终设计的优点和缺点.(1) 这个系统中有两张重要数据库表:account, attention_accountaccount 是用户表,而 attention_account 记录关注用户的用户列表.account(id, name, password)attention_account(id, attention_id)--id 为用户 id,比如 zhangsan,而 attention_id 为关注 id 用户的用户 id,比如 lisi每个用户都可以订阅自己感兴趣的用户,当某个用户每发布一篇文章时,都通知关注他的用户.这是典型的发布订阅模式.(2)缺点:发布订阅本来是一种比较好的解决方式,但是用户必须登录到 Twitter 系统才能看到自己感兴趣的信息.所以如果采取 B/s 模式的话,用户很难实时的看到自己感兴趣的信息.所以如果可以,建议在提供 B/s 模式的同时,也提供一个可选的 GUI 客户端,当用户每次登录操作系统的时候,自动启动 GUI 客户端.这样实时性更好.(3)评价:这个系统的优点是采用发布订阅方式,能够在用户发布信息的时候及时通知对其感兴趣的用户.难点是如何让用户实时的读取自己感兴趣的文章.注：GUI：graphical user interface：图形用户接口，采用图形方式显示的计算机操作用户界面。即人机交互图形化用户界面。B/S 模式：browser/server，浏览器/服务器模式，这种方式下，用户工作界面通过 IE 浏览器来实现，最大的优点是能实现不同的人员，从不同的地点，以不同的接入方式访问和操作共同的数据。最大的缺点是对外网环境严重依赖。发布订阅消息模式：注册用户成功后发送一个消息给消息管理器，由消息管理器转发该消息给需要处理的业务。现在，用户业务只依赖于消息管理器了，它再也不会为了注册用户成功后的其他处理而烦恼。发布-订阅消息模式已经呈现在我们面前，利用它可以产生更灵活、更松散耦合的系统。主要是实现客户端与服务端的即时数据交互，客户端通过订阅事件以待接收数据，服务端通过发布服务将即时数据发布至服务，服务通知订阅了事件的客户端。3、有一个图书馆系统，含有 Book 和 BookMaster 两个类。Book 可以用来设置书的属性(如title)，BookMaster 每天做的事情就是根据上级的要求重设设定某些书的 title，以增加借阅者的注意力，让更多的人对书有新的兴趣。有一天，上级需要 BookMaster 在 setTitle 的操作之前都要在日志中记录一条 log。但不幸的是由于一些很特别的原因，没有办法去修改 Book类，无法在 Book 类的 setTitle()方法中增加记录 log 的操作。更不幸的是上级不信任BookMaster 自己的统计结果，使 BookMaster 不能在做 setTitle()之前自己做 log 记录。 请问如何做才能达到目标，请写出必要的实现代码。相关类定义如下：public interface Book { //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、假设系统里有很多模板文件，每个模板文件都有一个唯一的文件名，其内容是一个长字符串，其中包含很多通过$...$方式标记起来的模板变量，如：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 的参数值）