数据结构与算法试题集锦

1 数组
1.1 两个已排序的整型数组，求交集，最快算法 
（百度）输入：两个已排序的整型数组（int a[m], b[n]）
输出：两个数组的交集
分析：注意有4种情况：
a升序，b升序；
a升序，b降序；
a降序，b升序；
a降序，b降序。
1.2 逆序对
（百度）多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为 <176, 170>,  <176, 171>,  <178, 170>,  <178, 171>,  <180, 170>,  <180, 171>, 
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)


要求：
输入:
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
输出：
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。


详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码 ，并分析时间复杂度。


限制：
输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。
解答：见算法导论P24页，分治法+修改合并排序
2 字符串
2.1 字符串原地倒序
（百度）用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。
2.2 判断字符串b的所有字符是否都在字符串a中出现过
（百度）判断字符串 b 的所有字符是否都再字符串 a 中出现过，a,b都是可能包含汉字的字符串。b中重复出现的汉字，那么a中也要至少出现相同的次数。汉字使用gbk编码（简单的说，用两个字节表示一个汉字，高字节最高位为1的代表汉字，低字节最高位可以不为1）。
int is_include(char *a ,  char *b)
返回0 表示没有都出现过，返回1表示都出现过
解答：哈希表
2.3 内存移动
（百度）用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
解答：memmove要考虑内存区域重叠的情况。
2.4 英文拼写纠错
（百度）在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度；
（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。
参考：http://blog.youxu.info/spell-correct.html 
2.5 中英文混合字符串
（百度）下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。 
for (char *piterator = szWord; *piterator != 0; piterator++) 
{ 
if (*piterator & 0x80 != 0) 
{ 
piterator++; 
} 
else if (*piterator >= 'A' && *piterator <= 'Z') 
piterator += 32; 
}
解答：
for (char *piterator = szWord; *piterator != 0; piterator++) 
{ 
if ( (*piterator & 0x80) != 0) 
{ 
piterator++; 
} 
else if (*piterator >= 'A' && *piterator <= 'Z') 
piterator += 32; 
}
注意：不是所有的汉字编码方案都是用2个字节表示一个汉字。
2.6 字符串模板替换
（百度）注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
考虑一个字符串替换的过程，在一个文本文件中含有一些文本内容和一些需要替换的变量，变量的格式为“$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苹果。
分析：先分析处理一个模板文件的情况。一个变量文件包含的变量数在百万数量级10^6，假设每个变量的名和值占用10Byte，一个变量文件占用VAR_FILE_SIZE=10^7Byte，约等于10M==0.01G。内存有2G，可以一次读入VAR_FILE_COUNT=100个变量文件，将变量名和变量值存入哈希表。建立哈希表时，使用再哈希：先以变量名为键，值是另一个哈希表的指针；另一个哈希表以变量文件编号为键，值就是变量值即<变量名，<变量文件编号，变量值> >。CPU有4个，并行运行THREAD_COUNT=4个线程，设线程ID为1,2,3,4，每个线程处理FILE_COUNT_PER_THREAD=25个变量文件。线程i处理模板文件时，遍历扫描到一个变量，在哈希表中查找变量文件编号为(i-1)*25到i*25的变量值，分别写入生成文件(i-1)*25到i*25。处理完这VAR_FILE_COUNT个变量文件后，再处理下VAR_FIEL_COUNT个变量文件，直到处理完所有的变量文件。至此，一个模板文件处理完了。按照相同的方法处理下一个模板文件。优化：
1、 在程序运行过程中，监控CPU和内存使用率。若使用率较低，可以增大一次处理的变量文件数目VAR_FILE_COUNT和线程数目THREAD_COUNT。
2、 读入变量文件建立哈希表和处理模板文件可以并行运行，有可能对某一个变量文件，还没有完全读入，就处理完了。
3、 使用异步IO。
3 集合
3.1 集合合并
（百度）给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。
参考：并查集
4 图论
4.1 在线好友系统
（百度）考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。


用户以ID形式表示，现给出好友列表数据的文本形式如下：
1  3,5,7,67,78,3332
2  567,890
31  1,66
14    567
78  10000
…
每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。


要求：
请设计合适的索引数据结构，来完成以下查询：
给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。


详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。


限制：
用户数量不超过1000万，平均50个好友。


解答：有向图+广度优先搜索
5 关于数字
5.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
…
解答：可以得到的数都可以表示成1001a+101b+11c+2d，其中0=<a,b,c,d<=9
如，78 = 78+7+8=70+8+7+8=70+7+8+8=11*7+2*8
99 = 99+9+9=90+9+9+9=99+9+9+9=11*9+2*9
589 = 589+5+8+9=500+80+9+5+8+9=505+88+2*9
编程时，注意：1、递归，2、2<=A<=18时，单独处理
伪代码：
bool get_n(int A, int &n)
{
If (A >= 1 && A <= 9 && A 是奇数)
return  false;
If (A >=0 && A<=18 && A是偶数)
{
n = A / 2;
return  true;
}
int d = A的位数;
int base = 10^(d-1)+1;
int x = A / base;
bool flag = get_n(A % base, y);
if (flag == false)
x -= 1;
flag = get_n(A%base+base, y);
if (flag == true)
{
N = x * base + y;
return  true;
}
else
return  true;
}
6 排列组合
6.1 s是序列seq的第几个字符串
（百度）序列 seq=[a,b,…,z,aa,ab,…,az,ba,bb,…,bz,…,za,zb,…,zz,aaa,…]类似于excel的字母序排列，任意给一字符串 s=[a-z]+(由a-z字符串组成的任意长度字符串)，请问s是序列seq的第几个字符串。
解答：
a: 1 
b: 2 
... 
z: 26 


aa = 1 * 26^1 + 1 = 27 
aaa = 1 * 26^2 + 1 * 26^1 + 1 = 703 


将字母序列从右往左依次编号为 i，最右边一位为 0，最左边一位为 n，
在 i 位上字母的值为 K[i]=字母asscii码值-‘a’+1，则序列为：
 
相当于26进制。具体计算时，采用霍纳规则。
扩展：给出一个索引值，求它对应的字符串
解答：类似于十进制转换为二进制
7 计算几何
7.1 计算重叠区间的长度
（百度）完成函数
size_t  foo(unsigned int *a1, size_t al1, unsigned int* a2, size_t al2)
其中a1和a2都为无符号数组，al1和al2为数组的长度，数组的长度为偶数。
无符号数组由一对数字区间组成。如下例：
a1 为 0,1,3,6,10,20
a2 为 0,1,20,50,4,5
则 a1表示以下区间[0,1] [3,6] [10,20]
   a2表示以下区间[0,1] [20,50] [4,5]
则a1,a2的重叠部分为[0,1] [4,5]，其长度为2
函数foo要求返回重叠区间的长度。上例中为2.
要求：
   详细说明自己的解题思路，说明自己实现的一些关键点。
写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。
限制：
al1和al2的长度不超过100万。而且同一个数组的区间可能出现重重叠。
   如a1可能为 0,5,  4,8,  9,100,  70,80
   使用的存储空间尽量小。
解答：对每一个数组按照区间左端点从小到大排序，合并重叠区间，遍历两个数组计算重叠区间长度。
8 海量数据处理
8.1 寻找热门查询
（百度）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
解答：哈希统计+顺序统计量+排序
8.2 查找长数组前500个单元
（百度）注意：要求尽可能提供完整代码，如果可以编译运行酌情加分。
内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。
解答：操作数组索引+顺序统计量+排序
8.3 设计字典
（百度）注意：请尽可能详细描述你的数据结构、系统架构、设计思路等，建议多写一些伪代码或者流程说明。 
1.请设计一个字典。以字符串为索引，存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数，可以由字符串映射到一个签名，每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名，完全没有重复（或者重复的概率可以忽略），并且签名分布足够均匀。 
请描述你的数据结构？内存如何申请？增、删、查、改的功能如何实现？如果操作很频繁，该如何优化？
解答：双哈希表+内存池
8.4 对上亿条URL排序
（百度）对给定的上亿条无序的url，请按照domain、site以及path分别排序，并请指出排序过程中可能会遇到的哪些问题？如何提高效率？ 
例如：http://www.baidu.com/path/about.html，domain、site以及path的定义分别如下： 
Domain:baidu.com 
Site:www.baidu.com 
Path: www.baidu.com/path 
解答：
1.题目给定的是 "上亿条无序的url ",第一个感觉就是这么多的数据不可能同时装入到内存中， "External Sorting "是必然的了。第二个感觉就是URL的长度差别很大的，有的很长，有的却很段，选择什么样的数据结构来存放这些数据就需要考虑。定长的数据应该是不合适的，变长的数据是个选择。 可以考虑trie树。
2.在domain,site,path中，我们可以先对domain排序，处于同一个domain的URL可以存放在一起，这样他们有类似的数据，例如:XX.baidu.com/XXX。然后我们可以对site进行排序，最后对path进行排序。
9 系统设计题
9.1 设计一个比较公平的评分系统
（百度）需求：需要引入用户对搜索结果相关性的评分，100分制。希望用户的打分能帮助搜索引擎排序，但又避免恶意投票、作弊等。请设计一个比较公平的评分系统。
解答：将所有用户的打分统计呈柱状图，越靠近峰值的打分权重越高，越偏离峰值的打分权重越低，避免恶意打高分或打低分。在服务器端用数据库或在浏览器端用cookie记录已打分过的IP地址，避免重复打分。
9.2 设计MP3搜索引擎
（百度）注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。


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 个。
分析：
SONG_ID和URL_ID都从0开始。
一首歌曲的最大URL列表的大小：2^10 * 4 = 2^12 Byte = 4 KB
一个文件最多容纳歌曲数目：2G / 4KB = 2*2^30 / 2^12 = 2^19
最少文件数目：2^24 / 2^19 = 2^5 = 32
解答：1、文件系统
文件以二进制格式存储数据，以FILE_ID唯一确定，从0开始。
一个文件容纳歌曲数目为SONG_COUNT = 2^18，需要的文件数目为FILE_COUNT = 64。
文件存储的信息分为两部分：在文件头部存储歌曲信息：歌曲ID，能收听该歌曲的URL数目，URL列表在文件中的偏移量，即：SONG_ID，URL_COUNT，URL_OFFSET。一首歌曲占用SONG_INFO_SIZE = 12Byte，所有歌曲占用即文件头部大小为SONG_COUNT*SONG_INFO_SIZE。下一部分对于每一首歌曲，按顺序存储其URL列表，一首歌曲的URL列表占用SONG_URL_SIZE = 4KB，所有歌曲占用SONG_COUNT*SONG_URL_SIZE。
所有的歌曲无论存在与否，都写入文件，预先占用空间。若歌曲不存在，其SONG_ID设置为-1，其余数据未定义。
给定一首歌曲的SONG_ID，确定它的位置：存储它的文件FILE_ID = SONG_ID / SONG_COUNT，在文件中的偏移量是FILE_OFFSET = SONG_ID % SONG_COUNT * SONG_INFO_SIZE。
再用另外一个文件存储所有的URL是否可用，一个URL对应一个bit，1为可用，0为不可用，占用2^30bit。
2、主系统
采用缓存方案，用户查询时，先从缓存中查找，若找到，直接返回，若找不到，从文件中查找，并读取到缓存中。
用户查询系统，分层：一是接入层，接收用户查询请求，将请求存到请求队列，从响应队列取出响应，发送给用户；二是业务逻辑层，从请求队列读取请求，调用缓存系统的方法得到歌曲数据，处理，将响应存到响应队列。接入层需要管理大量Socket，windows平台使用IO完成端口，Linux平台使用epoll。在多核平台，业务逻辑层可使用线程池。
缓存系统，使用哈希表存储歌曲信息，以SONG_ID为键，URL列表为值，保持2^10首歌曲信息。缓存系统负责，从文件中读取歌曲信息和URL信息，将改变了的歌曲信息或URL信息存回文件，以老化算法定期清理最近最少访问的歌曲。
给定一个 SONG_ID，为其添加一个新的 URL_ID，二叉查找新URL应该在的位置，可能需要将该位置以后的URL_ID集体后移。
10 智力趣味题
10.1 蚂蚁爬杆
（百度）有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
解答：最小时间是蚂蚁们分别向左或向右走, 其中在11厘米处的蚂蚁应该向左走比较近, 所以最小时间就是中间的蚂蚁向左处走出杆的时间, 也就是11秒。求最大时间呢? 假设蚂蚁走路能够相互穿透，当它们碰头时虽然题目里说是分别掉头, 但我们可以看成它们只是穿过了对方的身体而继续往前走, 要求最大时间也就是找到那个走出杆最久的蚂蚁, 很显然是3厘米的蚂蚁往右走(也就是木杆27厘米处), 时间为24秒。