百度面試題目

第第頁(yè)百度面試題目

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

其中a1和a2都為無(wú)符號(hào)數(shù)組，al1和al2為數(shù)組的長(zhǎng)度，數(shù)組的長(zhǎng)度為偶數(shù)。

無(wú)符號(hào)數(shù)組由一對(duì)數(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]，其長(zhǎng)度為2

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

要求：

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

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

限制：

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

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

運(yùn)用的存儲(chǔ)空間盡量小。

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

176,178,180,170,171

這些搗亂分子對(duì)為176,170,176,171,178,170,178,171,180,170,180,171,

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

要求：

輸入:

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

輸出：

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

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

限制：

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

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

3

考慮一個(gè)在線好友系統(tǒng)。系統(tǒng)為每個(gè)用戶維護(hù)一個(gè)好友列表，列表限制最多可以有500個(gè)好友，好友需要是這個(gè)系統(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間