百度面試題目之筆試題

申請(qǐng)免費(fèi)試用、咨詢電話：400-8352-114

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

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

字符串t數(shù)字n

說(shuō)明：

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

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

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

如果文件格式錯(cuò)誤，程序也退出。

要求：

編寫一個(gè)程序，輸入為N（正整數(shù)），讀入文件A.txt，按照字符串出現(xiàn)概率隨機(jī)地輸出字符串，輸出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個(gè)正整數(shù)，

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

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

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

例如：

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

[題目要求]

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

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

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

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

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

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

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

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

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

5、訪問量要求：所有feed訪問量每天在1億量級(jí)；所有的blogid增加量每天在百萬(wàn)量級(jí)。

題目：請(qǐng)?jiān)谝陨舷拗茥l件下，設(shè)計(jì)一個(gè)高效的feed訪問系統(tǒng)。

要求：

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

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

3、盡可能高效