百度考试题，请赐教！
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和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

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

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

4
有关系模式：User（userId, userName）， Article（articleId, userId, title, content），Vote（articleId, score），User为用户关系，Article为用户发表的文章关系，Vote为文章得票关系，title为文章标题、score为得票数。
（1）用SQL语言查询所有没发表过文章的用户名；
（2）用SQL语言查询得票数大于100的所有文章标题，按得票数倒序排列；
（3）用SQL语言查询出发表文章数大于5，文章平均得票数大于100的用户名，按平均得票数倒序排列；
（4）设计这些表的主键、外键和索引，并指出上面三个查询所使用的索引。
（5）当用户数超过1000万，文章数超过1亿时，如何考虑存储及性能的改进和优化？

[解决办法]
C#写的
static public int foo( int[] a1, int al1, int[] a2, int al2)
{
int[,] nArrayOne = new int[20, 2];
int[,] nArrayTwo = new int[20, 2];
int i = 0;
int j = 0;
int k = 0;
int r = 0;
int nNum = 0;
int n = 0;
int m = 0;
for (i = 0; i < al1; i++)
{
nArrayOne[n,m] = a1[i];
m++;
if (m == 2)
{
m = 0;
n++;
}
}
n = 0;
m = 0;
for (i = 0; i < al2; i++)
{
nArrayTwo[n, m] = a2[i];
m++;
if (m == 2)
{
m = 0;
n++;
}
}

for (i = 0; i < al1 / 2; i++)
{
for (j = nArrayOne[i,0]; j < nArrayOne[i,1]; j++)
{
for (k = 0; k < al2 / 2; k++)
{
for (r = nArrayTwo[k, 0]; r < nArrayTwo[k, 1]; r++)
{
if (j == r)
{
nNum++;
}
}
}
}
}
Console.WriteLine(nNum);

return 1;
}
[解决办法]
/*第一题！好做！*/
size_t foo(unsigned int *a1, size_t al1, unsigned int* a2, size_t al2)
{
size_t M,i,x,n=0;


M=al2;
if (al1> al2)
M=al1;
for(i=1,x=1;i <=M-1;i+=2)
{
x+=2;
if(a1[i]==a1[x] && a1[i+1]==a1[x+1])
n++;
if(a2[i]==a2[x] && a2[i+1]==a2[x+1])
n++;
if(a1[i]==a2[i]) && a1[i+1]==a2[i+1]
n++;
}
reture n;
}
思路形像设计两个指针，对长的组数进行一对一对的比较。另一组数组也同时跟随比较，并且同时两组数组对比！其中只要有一个是OK，就给重叠计算n加1；最后返回n
[解决办法]
第一道我的思路是：
1. 分别合并a1 a2， 如 0,5, 4,8, 9,100, 70,80
-〉 0， 8， 9， 100 （在这一步额外记录一下左小值0， 右大值100）
2. 在[左小值0， 右大值100]区间内用“非”的方式记录区间， 如上例为：
8，9
3. 在[左小值0， 右大值100]区间内逐个去掉a1， a2的“非”， 得结果c
4. c的长度即所求。

时间复杂度为
1 = O(n^2)
2 = O(n)
3 = O(n)
4 = o(n)

空间复杂度， 主要是C的分配，最坏情况也不过al1+al2

发出回复前审查了一下，发现1 2 步是可以合在一起做的。算了，当作抛砖引玉吧。

工作先~