各大計算機公司 筆試及面試 題目 - 百度（四）

1.一個int數組，裡面資料無任何限制，要求求出所有這樣的數a[i]，其左邊的數都小于等于它，右邊的數都大于等于它。能否隻用一個額外數組和少量其它空間實作。

2.一個檔案，内含一千萬行字元串，每個字元串在1K以内，要求找出所有相反的串對，如abc和cba。

3.STL的set用什麼實作的？為什麼不用hash？

4.給出兩個集合A和B，其中集合A={name}，集合B={age、sex、scholarship、address、...}，

要求：

問題1、根據集合A中的name查詢出集合B中對應的屬性資訊；

問題2、根據集合B中的屬性資訊（單個屬性，如age<20等），查詢出集合A中對應的name。

5.給出一個檔案，裡面包含兩個字段{url、size}，即url為網址，size為對應網址通路的次數，

要求：

問題1、利用Linux Shell指令或自己設計算法，查詢出url字元串中包含“baidu”子字元串對應的size字段值；

問題2、根據問題1的查詢結果，對其按照size由大到小的排列。

（說明：url資料量很大，100億級以上）

6.給定一個存放整數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數。

要求：空間複雜度O(1)，時間複雜度為O（n）。

7.用C語言實作函數void * memmove(void *dest, const void *src, size_t n)。memmove函數的功能是拷貝src所指的記憶體内容前n個位元組到dest所指的位址上。

分析：

由于可以把任何類型的指針賦給void類型的指針,這個函數主要是實作各種資料類型的拷貝。

8.2010年3道百度面試題[相信，你懂其中的含金量]

a~z包括大小寫與0~9組成的N個數

用最快的方式把其中重複的元素挑出來。

9.已知一随機發生器，産生0的機率是p，産生1的機率是1-p，現在要你構造一個發生器，使得它構造0和1的機率均為1/2；構造一個發生器，使得它構造1、2、3的機率均為1/3；...，

構造一個發生器，使得它構造1、2、3、...n的機率均為1/n，要求複雜度最低。

10.有10個檔案，每個檔案1G，每個檔案的每一行都存放的是使用者的query，每個檔案的query都可能重複。要求按照query的頻度排序.

備注： 轉載于 周磊的部落格，http://blog.csdn.net/v_JULY_v/article/details/6057286