百度2005-2009笔试题

百度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) 改进

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.doczj.com/doc/a06204187.html,/path/about.html，domain、site以及path的定义分别如下：Domain:https://www.doczj.com/doc/a06204187.html,

Site:https://www.doczj.com/doc/a06204187.html,

Path: https://www.doczj.com/doc/a06204187.html,/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类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以忽略），并且签名分布足够均匀。

请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁，该如何优化？

第1题：用C语言实现一个公用库函数void * memmove(void *dest,const void *src,size_t n)。该函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。注意，作为公用库函数，请注意安全检查，注意处理内存区重合的情况。

第2题：已知一个字串由GBK汉字和ansi 编码的数字字母混合组成，编写C语言函数实现从中去掉所有ansi编码的的数字和字母（包括大小写)，要求在原字串上返回结果。函数接口为：int filter_ansi(char* gbk_string)。注：汉字的GBK编码范围是0x8140 - 0xFEFE

第3题：芯片测试。有2k块芯片，已知好芯片比坏芯片多。请设计算法从其中找出一片好芯片，并说明你所用的比较次数上限。其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏；坏芯片和其它芯片比较时，会随机的给出好或是坏。

------------------------------------------------------------ 在这里填写答案：

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

第1题：用C语言实现一个公用库函数void * memmove(void *dest,const void *src,size_t n)。该函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。注意，作为公用库函数，请注意安全检查，注意处理内存区重合的情况。

void* memmove(void * dest, const void * src, size_t n)

{

void* temp = dest;

if (dest <= src || (char *)dest >= ((char *)src + n)) //无内存地址重叠

{

while (n--)

{

*(char *)dest = *(char *)src;

dest = (char *)dest + 1;

src = (char *)src + 1;

}

}

else //有内存地址重叠

{

dest = (char *)dest + n - 1;

src = (char *)src + n - 1;

while (n--)

{

*(char *)dest = *(char *)src;

dest = (char *)dest - 1;

src = (char *)src - 1;

}

}

return (temp);

}

第2题：已知一个字串由GBK汉字和ansi 编码的数字字母混合组成，编写C语言函数实现从中去掉所有ansi编码的的数字和字母（包括大小写)，要求在原字串上返回结果。函数接口为：int filter_ansi(char* gbk_string)。注：汉字的GBK编码范围是0x8140 - 0xFEFE

int filter_ansi(char* gbk_string)

{

char *p = gbk_string, *q = gbk_string;

while (*q != '\0')

{

if ((*q >= 0) && (*q <= 128)) //判断是否为asci的字符

{

if (((*q >= '0') && (*q <= '9')) //判断是否为数字或字母

|| ((*q >= 'a') && (*q <= 'z'))

|| ((*q >= 'A') && (*q <= 'Z')))

{

q++;

}

else

{

*p++ = *q++;

}

}

else

{

if (((*((unsigned short*)q)) >= 0x8140) && ((*((unsigned short*)q)) <= 0xFEFE)) //是汉字

{

*p++ = *((char*)q)++;

*p++ = *((char*)q)++;

}

else //不是汉字

{

q++;

q++;

}

}

}

*p = '\0';

return (p - gbk_string);

}

第3题：芯片测试。有2k块芯片，已知好芯片比坏芯片多。请设计算法从其中找出一片好芯片，并说明你所用的比较次数上限。其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏；坏芯片和其它芯片比较时，会随机的给出好或是坏。

答案：

1．首先两个两个分成一对。如果互测的结果是好好，那么留下，否则扔掉。扔掉的里面总是坏的不会比好的少。这样剩下的要么是两个好的，要么是两个坏的。可以称剩下的这样的对为纯粹对。经过这一次分对，最坏的情况是1000对都留下；

2．然后把留下的对再随便两两分组。这样变成每组里有两个纯粹对。每组比较时，从这两个纯粹对中任意各选一个元素进行比较。如果都是好的，那么留下这组，否则扔掉。这样剩下的要么四个都是好的，要么四个都是坏的，我们把四个看成一个组，这个组是纯粹组。经过这一次分对，最坏的情况是500对都留下；

3．接着把剩下的这些组再随便两两分对。得到的每对里有两个纯粹组。比较每对里的两个纯粹组时，还是任意各选一个元素比较。如果都是好的，那么留下这对，得到一个新的纯粹组，里面有8个好的或者8个坏的。否则扔掉。最坏的情况是留下250对；

4．再把这些剩下的组两两分对。同样从每对的两个纯粹组中各任选一个元素进行比较。都是好的留下，成为新的纯粹组。否则扔掉。这样可得到一个新的纯粹组，其中16个都是好的或者16个都是坏的。最坏的情况是留下125对；

5．同样两两分对，得到62对和一个单独的。我们用同样方法比较这62对。最坏的情况是留下31对，其中每对里32好或者32坏，和单独的一个，其中16好或者16坏。把它们带入下一轮；

6．把剩下的32对再任意两两分组，其中一组是一个含有32好或坏，另一个含有16个好或坏，记为A。其它的15组都是两个含有32好或坏的。同样方法比较这15组，得到新的纯粹组，含有64好或64坏。最坏的情况留下15组。至于A, 我们也是两个中各任选一个代表比较，如果同好，那么留下，成为新的纯粹组，含有48个好或者坏。否则从含有32好或坏的那组中任意选16个和另一组含有16个好或坏的一起扔掉，剩下的16个同好或同坏的成为一个新的纯粹组。这样我们可以保证扔掉的里面总是坏的不比好的少。也就是说最坏的情况是剩下16组。

7．把这16组两两分对。用和第六步一样的方法。我们最坏可以得到8个。其中7个是128好或者128个坏，还有一个是数目小于128的纯粹组。

8．同理，再两两分对，我们可以得到4组；然后得到两组。这时只要从数量最多的那个组中任选一个，即为好的。所以最坏的情况是要比较1000+500+250+125+62+31+16+8+4+2=1998次. （如果剩下的是两组芯片个数一样多，那么可以从两个组中任选一个，即为好的。因为好的数量总比坏的数量多，而且我们每次扔掉的都是坏的比好的多或者相等。所以剩下的这两个组中的芯片只可能都是好的。）

——————————————————、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个

。

为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩

大，该如何多机分布处理？

2008-9-24百度笔试题（第一套题）

一：编程题

现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找不到输出-1。要求：1，时间复杂度最优，能够在短时间内对大量输入逐个输出

2，实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。

3，给出时间复杂度和空间复杂度。TERM组合集合的文件格式举例：

TERM_1 空格TERM_2 TERM_1 空格TERM_3

TERM_1 空格TERM_3 TERM_4

输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）

二：算法题

你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是你知道一个整数M,这些记录满足R1

1,设计一个算法或编写一个程序，将文件中的记录排序为R1'

三：系统设计题

网络上所有的链接都可以用以下的三元素进行描述：

From_url（链接所在页面的URL）

to_url（链接所指向的URL）

anchor（链接在页面上所显示的内容）

现在假设所有的网页链接信息（from_url \ to_url \anchor）按from_url为轴都存储在M 个（M：1k以内）巨型数据库中：

1，链接存储形式：from_url to_url anchor；

2，一个from_url的所有的to_url都存储在同一个数据库中；

3，假设每个数据库存储的数据量相同4，要求设计一个获取所有链接分发程序，将这些数据均匀分发到N个远程数据库中（N:100以内）要求做到：1所有to_url相同的链接需要分到同一个远程数据库，2所有to_url的站点相同的需要分发到同一个远程数据库，3每个远程数据库获取的链接总数要尽量均匀，4每台数据库完成时间尽量保持一致5，获取网页的速度尽量快（从数据库中）

说明：对于url：https://www.doczj.com/doc/a06204187.html,/m?tn=baidump3，其中https://www.doczj.com/doc/a06204187.html,属于站点信息。

2008-9-24百度笔试题（第二套题）

一：算法题

有一段文本，由英文字母、阿拉伯数字、GB2312编码的中文字符和一些常用标点符号（假设只包含全/半角的逗号和句子）组成。请写出程序，统计这段文本中每个字的出现次数，对“字”的定义如下：1，连续的英文字母或者阿拉伯数字，例如ab3或123，但最长不超过32个字符；2，包含不超过一个半角句点的两段连续数字，例如2.34，但最长不超过32个字符3，单个汉字二：开放性题目

ORMapping是进行快速web开发经常使用到的技术，请设计一个简单的ORMapping 框架，请首先说明设计思路，然后给出设计和Mapping部分的编码，并指出实现ORMapping所用到的编程语言的关键语言特性，要求：1，实现简单对象到关系的映射2，完成一对多关系到对象的映射。

三：数据库题

设计一个游戏积分系统，能够实现以下功能：1，用户在客户端结束游戏后，能够通过相应接口将积分进行上传；2，服务端保存结果并能展示该游戏的积分排行情况，分数按照从高到低排列，相同分数下按照提交时间的先后排定顺序；3，排行榜只展现排名前200的用户；4，同一个用户多次提交的情况下，只取分数最高的一次记录；5，系统要有一定的扩展性，能够灵活的增加、删除一个游戏。

要求：1，阐述客户端和服务端如何进行交互，交互流程是怎样的，设计合理的交互过程及接口。2，设计服务端存储系统，阐述采用的存储方案，如果是使用数据库，详细说明表的结构索引等。3，系统要求有很强的防作弊功能，能够屏蔽用户自己伪造数据提交成其他的spam行为。4，在满足功能的前提下，能够尽量提高整套系统的效率，例如：降低负载、缩短响应时间等。5，同时在线游戏的用户有百万级，因此单机很可能承受不了这么大的浏览压力，在设计系统的时候要考虑多台服务器如何部署，怎样保证负载均衡说明：1，用户的登录信息系统可以直接获取到，设计的时候不用考虑这个问题2，要求中第5条为附加功能，在满足功能的前提下再考虑多服务器的部署问题3：客户端与服务器的交互采用简单的HTTP协议即可，不用考虑其他交互方式。

四：设计题

历史操作信息分页显示设计。现有一系统，需要保存用户6个月内的操作信息以提供给用户查询，由于历史操作的数据量特别大，采用每个月的操作信息保存在一张数据表的形式存储。设计实现用户查询操作信息时候的分页显示的实现算法，相关要求如下：需要向用户显示总的符合查询条件的记录数以及总的页数2，以上系统采用WEB形式实现。

2008-9-24百度笔试题（第三套题）

提示：写出你认为最优的答案，若写不出具体代码，也请写明解题思路。

1 名词解释：WEB前端开发指依托于浏览器的HTML/CSS、JavaScript脚本和Flash等开发。

1， 2 请问一份标准的HTML文档有哪几个必须的HTML标签？

2， 3 JavaScript脚本为Array对象添加一个去除重复项的方法？

3， 4 请问在JavaScript中如何调用以下几个CSS属性：font-size，border-top-width, -moz-user-select?

4， 5 JavaScript脚本如何对一个对象进行深度Clone？

5， 6 有一个宽度补丁高度不定的圆角框图，先要切成网页，请写出HTML+CSS 代码？

6，7 用JavaScript写一个图片跑马灯程序，图片从右向左动态无缝移动

7，8 如何对网页的加载进行性能优化？

8，9 [Linux]利用命令find查找当前目录下的名称尾为.C的文件，并将结果输出到标准输出的命令是_____________.

9，10 [Flash附加题]请简要叙述：ActionScript与JavaScript如何进行交互？请

用简要的代码说明。

2008-9-24百度笔试题（第四套题）

一：编程题

现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找不到输出-1。要求：1 时间复杂度最优，能够在短时间内对大量输入逐个输出

2 实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。

3 给出时间复杂度和空间复杂度。

TERM组合集合的文件格式举例：

TERM_1 空格TERM_2

TERM_1 空格TERM_3

TERM_1 空格TERM_3 TERM_4

输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）

二：算法题

你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是你知道一个整数M,这些记录满足R1

1,设计一个算法或编写一个程序，将文件中的记录排序为R1'

1，以下是一个简单的Hello world程序

# include

Int main()

{

Printf(“hello world\n”);

Return 0;

} 编译生成hello后，运行./hello;

会先fork一个子进程，然后调用execve转载可执行程序hello，在调用fork11时采用了一种叫做COW(copy on write,写时复制的策略)，这种思想不仅在内核中而且在应用程序中被广泛地采用。请描述下COW的思想，以及它的实现。

2请描述以下fork clone 和fork的区别。

3运行ldd hello可以得到如下结果

Linux-gate.so.1（oxb7f4f000）

Lib.so.6

/lib/tls/i686/cmov/libc.so.6(oxb7dee000)

/lib/ld-linux.so.2(oxb7f50000)

其中libc.so.6是动态链接库，ld-linux.so.2是动态链接库加载器，请简要描述下动态链接库的加载过程和优点。

四：只记下来一题（似乎有3道小题，任选一题做）

现在需要对2000台机器升级某个软件？已经有这个软件的最新代码，1：你会选择用什么工具自动升级该软件？请给出具体步骤或方法？

2：为了便于后期的运维，如果让你设计一套软件部署方案，你会怎么设计？

2008-9-24 百度网络工程师笔试题(第五套笔试题)

第一大题，共6小题，每题5分，共30分1:什么是保留IP地址,请列举?为什么规定保留IP地址?

2:IPv4和IPv6的地址分别是多少？

3:什么是访问控制列表?它的执行流程?

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

1,设计一个算法或编写一个程序，将文件中的记录排序为R1',R2',...,RN',算法或程序读取文件的次数为O(N),不限内存使用，

2,设计一个算法或编写一个程序，将文件中的记录排序为R1',R2',...,RN',算法或程序读写文件的次数为O(N)，空间复杂度

为O(1)，亦即，你使用的内存大小和M,N 均无关。

第三大题，每小题20分，共40分

1：在某些情况下，网络中会出现路由环路，请根据你的理解，说明可能出现路由环路的原理，并以你最熟悉

2如果用户向你申述上百度主页很慢，你会从哪些方面取分析这个问题，如何高效的分析并判断故障根源所在？

2009百度实习笔试题Zz

一、编程题（30分）

输入：N（整数）

输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节

文件格式如下：

字符串\t数字\n

说明：

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

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

多条记录的出现概率之和为100，如果A.txt 不满足该条件，程序则退出；

如果文件格式错误，程序也退出。要求：

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

地输出字符串，输出N条记录

例如：

输入文件A.txt

abc\t20

a\t30

de\t50

输入为：10

即abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记

录

以下为一次输出的结果,多次输出的结果可能不相同。

abc

a

de

de

abc

de

a

de

a

de

二、算法题（35分）

题目描述：

设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数

程序输出：联接成的多位数

例如：

n=2时，2个整数32，321连接成的最小整数为：32132，

n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]

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

法。

2. 给出算法的时间空间复杂度。

3. 证明你的算法。（非常重要）

三、系统设计题（35分）

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

念

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

写为uid)；则uid的范围是从1到1000万的正整数。

2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的

两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以

被解除

3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发

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

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

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

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

万量级。

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

要求：

1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed ；feed的展现按照时间倒排序，最新的在最前面

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

3、尽可能高效。