百度面試題目之筆試題

申請免費試用、咨詢電話：400-8352-114

輸入：N（整數(shù)）

輸入：數(shù)據(jù)文件A.txt，不超過6條記錄，字符串長度不超過15個字節(jié)文件格式如下：

字符串t數(shù)字n

說明：

每行為1條記錄；字符串中不含有t。

數(shù)字描述的是該字符串的出現(xiàn)概率，小于等于100的整數(shù)。

多條記錄的出現(xiàn)概率之和為100，如果A.txt不滿足該條件，程序則退出；

如果文件格式錯誤，程序也退出。

要求：

編寫一個程序，輸入為N（正整數(shù)），讀入文件A.txt，按照字符串出現(xiàn)概率隨機地輸出字符串，輸出N條記錄

例如：

輸入文件A.txt

abct20
 

at30
 

det50
 

輸入為：10

即 abc有20%的概率輸出，a有30%的概率輸出，de有50%的概率輸出，輸出10條記錄

以下為一次輸出的結(jié)果,多次輸出的結(jié)果可能不相同。
 

abc
 

a
 

de
 

de
 

abc
 

de
 

a
 

de
 

a
 

de

二、算法題（35分）

題目描述：

設(shè)有n個正整數(shù)，

將它們聯(lián)接成一排，組成一個最小的多位整數(shù)。

程序輸入：n個數(shù)

程序輸出：聯(lián)接成的多位數(shù)

例如：

n=2時，2個整數(shù)32，321連接成的最小整數(shù)為：32132，n=4時，4個整數(shù)55，31，312, 33 聯(lián)接成的最小整數(shù)為：312313355

[題目要求]

1. 給出偽代碼即可，請給出對應(yīng)的文字說明，并使用上面給出的例子試驗?zāi)愕乃惴ā?/p>

2. 給出算法的時間空間復(fù)雜度。

3. 證明你的算法。（非常重要）

三、系統(tǒng)設(shè)計題（35分）

在一個有1000萬用戶的系統(tǒng)中，設(shè)計一個推送(feed)系統(tǒng)。以下是一些預(yù)定義概念

1、用戶：在這個系統(tǒng)中，每個用戶用一個遞增的unsigned int來表示user id(簡寫為uid)；則uid的范圍是從1到1000萬的正整數(shù)。

2、好友：用戶之間可以形成好友關(guān)系，好友是雙向的；比如說uid為3和uid為4的兩個用戶可以互為好友。每個用戶好友的上限是500個；用戶之間的好友關(guān)系可以被解除

3、活動：每個用戶只能發(fā)文章；文章可以被作者刪除，其他人不能刪除非自己發(fā)表的文章；每篇文章通過一個blogid表示。

4、feed：我們希望，每個用戶可以看到他所有好友的活動列表，在這個簡化的系統(tǒng)中就是所有好友的文章更新列表。

5、訪問量要求：所有feed訪問量每天在1億量級；所有的blogid增加量每天在百萬量級。

題目：請在以上限制條件下，設(shè)計一個高效的feed訪問系統(tǒng)。

要求：

1、能夠盡快的返回每個用戶的好友feed列表，每個用戶可以最多保留1000條feed；feed的展現(xiàn)按照時間倒排序，最新的在最前面

2、用戶刪除某篇文章后，被推出去的feed需要及時消失。即每個用戶看到的好友feed都是未被刪除的

3、盡可能高效