第第頁百度面試題目

size_tfoo(unsignedint*a1,size_tal1,unsignedint*a2,size_tal2)

其中a1和a2都為無符號數(shù)組，al1和al2為數(shù)組的長度，數(shù)組的長度為偶數(shù)。

無符號數(shù)組由一對數(shù)字區(qū)間組成。如下例：

a1為0,1,3,6,10,20

a2為0,1,20,50,4,5

那么a1表示以下區(qū)間[0,1][3,6][10,20]

a2表示以下區(qū)間[0,1][20,50][4,5]

那么a1,a2的重疊部分為[0,1][4,5]，其長度為2

函數(shù)foo要求返回重疊區(qū)間的長度。上例中為2.

要求：

具體說明自己的解題思路，說明自己實現(xiàn)的一些關(guān)鍵點。

寫出函數(shù)foo原代碼，另外效率盡量高，并給出代碼的繁復(fù)性分析。

限制：

al1和al2的.長度不超過100萬。而且同一個數(shù)組的區(qū)間可能涌現(xiàn)重重疊。

如a1可能為0,5,4,8,9,100,70,80

運用的存儲空間盡量小。

2多人排成一個隊列,我們認(rèn)為從低到高是正確的序列,但是總有部分人不遵守秩序。假如說,前面的人比后面的人高(兩人身高一樣認(rèn)為是合適的),那么我們就認(rèn)為這兩個人是一對“搗亂分子”,比如說,現(xiàn)在存在一個序列:

176,178,180,170,171

這些搗亂分子對為176,170,176,171,178,170,178,171,180,170,180,171,

那么,現(xiàn)在給出一個整型序列,請找出這些搗亂分子對的個數(shù)(僅給出搗亂分子對的數(shù)目即可,不用詳細(xì)的對)

要求：

輸入:

為一個文件(in)，文件的每一行為一個序列。序列全為數(shù)字，數(shù)字間用”,”分隔。

輸出：

為一個文件(out)，每行為一個數(shù)字，表示搗亂分子的對數(shù)。

具體說明自己的解題思路，說明自己實現(xiàn)的一些關(guān)鍵點。并給出實現(xiàn)的代碼，并分析時間繁復(fù)度。

限制：

輸入每行的最大數(shù)字個數(shù)為100000個，數(shù)字最長為6位。程序無內(nèi)存運用限制。

二、下面是兩道選做題，請依據(jù)自己的狀況選擇其中的一道作答(WEB方向請答第4道，其他職位方向答第3道)。

3

考慮一個在線好友系統(tǒng)。系統(tǒng)為每個用戶維護(hù)一個好友列表，列表限制最多可以有500個好友，好友需要是這個系統(tǒng)中的其它用戶。好友關(guān)系是單向的，用戶B是用戶A的好友，但A不肯定是B的好友。

用戶以ID形式表示，現(xiàn)給出好友列表數(shù)據(jù)的文本形式如下：

13,5,7,67,78,3332

2567,890

311,66

14567

7810000

…

每行數(shù)據(jù)有兩列，第一列為用戶ID，第二列為其好友ID，不同ID間