百度面试题目
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
使用的存储空间尽量小。
2 多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:
176, 178, 180, 170, 171
这些捣乱分子对为<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的.对)
要求:
输入:
为一个文件(in),文件的每一行为一个序列。序列全为数字,数字间用”,”分隔。
输出:
为一个文件(out),每行为一个数字,表示捣乱分子的对数。
详细说明自己的解题思路,说明自己实现的一些关键点。并给出实现的代码 ,并分析时间复杂度。
限制:
输入每行的最大数字个数为100000个,数字最长为6位。程序无内存使用限制。
二、下面是两道选做题,请根据自己的情况选择其中的一道作答(WEB方向请答第4道,其他职位方向答第3道)。
3
考虑一个在线好友系统。系统为每个用户维护一个好友列表,列表限制最多可以有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