百度面試題目

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