1000
百度麵試題
百度麵試題，僅提供一些參考。
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
使用的存儲空間盡量小。
解題方法：先對兩個數組的區間進行排序，排序規則以區間的第一個數為鍵，然後將一個數組構建二叉排序樹，將另一個數組中的區間一次在二叉排序樹中查找。 時間複雜度（nlogn） 。
有人提出了log(+n)的複雜度，就是將兩個數組排序，排序規則如上，然後對兩個數組進行歸並，歸並出的結果即為所得。
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億時，如何考慮存儲及性能的改進和優化？
最後更新：2017-04-04 07:03:49