百度面試題目
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