2016年百度筆試經(jīng)驗(yàn)
英文拼寫糾錯
在用戶輸入英文單詞時，經(jīng)常發(fā)生錯誤，我們需要對其進(jìn)行糾錯。假設(shè)已經(jīng)有一個包含了正確英文單詞的詞典，請你設(shè)計一個拼寫糾錯的程序。
(1)請描述你解決這個問題的思路;
(2)請給出主要的處理流程，算法，以及算法的復(fù)雜度;
(3)請描述可能的改進(jìn)(改進(jìn)的方向如效果，性能等等，這是一個開放問題)。
解答：
(1)思路 :
字典以字母鍵樹組織，在用戶輸入同時匹配
(2)流程:
每輸入一個字母：
沿字典樹向下一層，
a)若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果;
b)若該處不能匹配，糾錯處理，給出拼寫建議，繼續(xù)至a);
算法:
1.在字典中查找單詞
字典采用27叉樹組織，每個節(jié)點(diǎn)對應(yīng)一個字母，查找就是一個字母一個字母匹配.算法時間就是單詞的長度k.
2.糾錯算法
情況:當(dāng)輸入的最后一個字母不能匹配時就提示出錯，簡化出錯處理，動態(tài)提示可能處理方法:
(a)當(dāng)前字母前缺少了一個字母：搜索樹上兩層到當(dāng)前的匹配作為建議;
(b)當(dāng)前字母拼寫錯誤：當(dāng)前字母的鍵盤相鄰作為提示;(只是簡單的描述，可以有更多的)
根據(jù)分析字典特征和用戶單詞已輸入部分選擇(a)，(b)處理
復(fù)雜性分析：影響算法的效率主要是字典的實(shí)現(xiàn)與糾錯處理
(a)字典的實(shí)現(xiàn)已有成熟的算法，改進(jìn)不大，也不會成為瓶頸;
(b)糾錯策略要簡單有效 ，如前述情況，是線性復(fù)雜度;
(3)改進(jìn)
策略選擇最是重要，可以采用統(tǒng)計學(xué)習(xí)的方法改進(jìn)。
尋找熱門查詢
搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個記錄，這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。
(1)請描述你解決這個問題的思路;
(2)請給出主要的處理流程，算法，以及算法的復(fù)雜度。
解答:
(1)思路：
用哈希做
(2)
首先逐次讀入查詢串，算哈希值，保存在內(nèi)存數(shù)組中，同時統(tǒng)計頻度(注意值與日志項(xiàng)對應(yīng)關(guān)系)選出前十的頻度，取出對應(yīng)的日志串，簡單不過了。
哈希的設(shè)計是關(guān)鍵。
集合合并
給定一個字符串的集合，格式如：
{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應(yīng)輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
(1)請描述你解決這個問題的思路;
(2)請給出主要的處理流程，算法，以及算法的復(fù)雜度
(3)請描述可能的改進(jìn)(改進(jìn)的方向如效果，性能等等，這是一個開放問題)。
解答:
(1)思路：先將集合按照大小排列后，優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，如果小集合與所有其他集合都沒有交集，則獨(dú)立。獨(dú)立的集合在下一輪的比較中不用考慮。這樣就可以盡量減少字符串的比較次數(shù)。當(dāng)所有集合都獨(dú)立的時候，就終止。
(2)處理流程：
1.將集合按照大小排序，組成集合合并待處理列表
2.選擇最小的集合，找出與之有交集的集合，
如果有，合并之;
如果無，則與其它集合是獨(dú)立集合，從待處理列表 中刪除。
3.重復(fù)直到待處理列表為空
算法：
1。將集合按照大小從小到大排序，組成待處理的集合列表。
2。取出待處理集合列表中最小的集合，對于集合的每個元素，依次在其他集合中搜索是否有此元素存在：
1>若存在，則將此小集合與大集合合并，并根據(jù)大小插入對應(yīng)的位置 。轉(zhuǎn)3。
2>若不存在，則在該集合中取下一個元素。如果無下一個元素，即所有元素都不存在于其他集合。則表明此集合獨(dú)立，從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)3。
3。如果待處理集合列表不為空，轉(zhuǎn)2。如果待處理集合列表為空，成功退出，則結(jié)果集合列表就是最終的輸出。
算法復(fù)雜度分析：
假設(shè)集合的個數(shù)為n，最大的集合元素為m
排序的時間復(fù)雜度可以達(dá)到n*log(n)
然后對于元素在其他集合中查找，最壞情況下為(n-1)*m
查找一個集合是否與其他集合有交集的最壞情況是m*m*(n-1)
合并的時間復(fù)雜度不會超過查找集合有交集的最壞情況。
所以最終最壞時間復(fù)雜度為O(m*m*n*n)
需要說明的是：此算法的平均時間復(fù)雜度會很低，因?yàn)闊o論是查找還是合并，都是處于最壞情況的概率很小，而且排序后優(yōu)先用最小集合作為判斷是否獨(dú)立的對象，優(yōu)先與最大的集合進(jìn)行比較，這些都最大的回避了最壞情況。
(3)可能的改進(jìn)：
首先可以實(shí)現(xiàn)將每個集合里面的字符串按照字典序進(jìn)行排列，這樣就可以將查找以及合并的效率增高。
另外，可能采取恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找以及合并等操作的效率得到提高。
需要引入用戶對搜索結(jié)果相關(guān)性的評分
需求：需要引入用戶對搜索結(jié)果相關(guān)性的評分，100分制。希望用戶的打分能幫助搜索引擎排序，但又避免惡意投票、作弊等。請設(shè)計一個比較公平的評分系統(tǒng)。
輸入：N(整數(shù))
輸入：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)概率隨機(jī)地輸出字符串，輸出N條記錄
例如：
輸入文件A.txt
abc/t20
a/t30
de/t50
輸入為：10
即 abc有20%的概率輸出，a有30%的概率輸出，de有50%的概率輸出，輸出10條記錄
以下為一次輸出的結(jié)果，多次輸出的結(jié)果可能不相同。
abc
a
de
de
abc
de
a
de
a
de
解答:
這個題目感覺意思有歧義。什么是”按照字符串出現(xiàn)概率隨機(jī)地輸出字符串，輸出N條記錄”?可以有幾種理解。第一，每次擲骰子，擲出了哪個就輸出哪個，不管前面輸出了什么。第二，要考慮前面出現(xiàn)的字符串。按照題目里的例子，如果前面輸出了兩次abc，那接下來的無論隨機(jī)出了什么數(shù)，都不能輸出abc，最后的結(jié)果在數(shù)量上符合開始給的概率條件，只是順序有所不同。這讓我想起了排列組合里的袋中取黑球紅球問題。把字符串a(chǎn)bc，a，de當(dāng)作2個紅球，3個黑球和 5個白球，放入袋中。每次拿一個球出來，并記錄拿出球的顏色。第一種情況就是拿出球后，把球放回袋中進(jìn)行下一次抽取;而第二種自然就是不放回的抽取。
更多相關(guān)筆試題目推薦：
百度2014校園招聘筆試題 百度2014招聘研發(fā)工程師筆試題 百度軟件工程師筆試題大全 2014百度筆試題(軟件研發(fā)工程師) 百度搜狐人人去哪兒校招筆試題 2014網(wǎng)易校園招聘筆試題大全 2015建行筆試題目(附答案解析) 2015年普通話水平測試題 Linux招聘常見筆試真題薈萃
軟件測試常見筆試真題
順著百度的筆試不可能那么弱智的想法，同時給出的例子也符合第二種情況的形勢，就照著第二種思路往下做。這個題目在從鼓樓到浦口的鼓揚(yáng)線上最近剛看過，就是編程珠璣II(More Programming Pearls) ，第13章的內(nèi)容(絕妙的取樣)。對于這個題，就是給出abc*2， a*3， de*5，輸出隨機(jī)排列。比較笨的算法就是每次得到一個隨機(jī)數(shù)，如果這個隨機(jī)數(shù)代表的球已經(jīng)耗盡，那就取下一個隨機(jī)數(shù)。這樣的缺點(diǎn)是效率低，越往后效率越低，基本是在拼RP。還是拿例子說事兒，如果隨機(jī)數(shù)為1-2，則輸出abc，3-5輸出a，6-10輸出de。如果到了第9次，還剩下一個abc沒輸出，則要一直隨機(jī)到出現(xiàn)1，2為止才結(jié)束。
第二種辦法是Floyd提出來的(似乎就是那個Floyd-Warshall)。算法如下：
S = []
for j= 1 to N do
T = RandInt(1， j);
if T is not in S then
prefix T to S
else
insert J in S after T
不過這個題目還有一個問題：對于每個字符串，生成的期望個數(shù)并不一定為整數(shù)。例子中的N改成5的話，那就是期望輸出1.5個a和2.5個de，隨機(jī)序列自然沒法搞。這個時候回到第一個方法仍然可以做，不過題目也因此解釋不通了。同學(xué)的解釋是，如果是期望輸出1.4個a和2.6個de，這一個a和de的爭議值，在2/5的情況下輸出a，剩下的情況輸出b。不過我們其實(shí)是沒有理由把這個不確定的情況限制在一個整數(shù)單位區(qū)間里的，即對于1.4個a和2.6個 de，必須輸出1a+3de或者2a+2de才算合法輸出，而把4de，3a+1de的情況定位非法。我覺得這塊說不同，所以不需要考慮非整數(shù)的不確定情況(如果直接四舍五入到整數(shù)，還是算整數(shù)的確定情況的)。
設(shè)有n個正整數(shù)
設(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)的文字說明，并使用上面給出的例子試驗(yàn)?zāi)愕乃惴ā?/p>
2. 給出算法的時間空間復(fù)雜度。
3. 證明你的算法。(非常重要)
解答:
這題我沒怎么考慮。同學(xué)的思想在于，把n個正整數(shù)按優(yōu)先級排個序，然后按照排序的結(jié)果從小到大排列組成最小的整數(shù)。注意這個排序并不是普通的算術(shù)排序，而是基于一定的規(guī)則。比較的時候把兩個數(shù)字當(dāng)成字符串進(jìn)行字典排序，如果一個數(shù)字正好是另外一個數(shù)字的前綴的時候，去掉較長字符串的前綴，繼續(xù)進(jìn)行比較，直到分出勝負(fù)。當(dāng)然也有旗鼓相當(dāng)?shù)臅r候，比如31和313131，這兩者的優(yōu)先級即相同。
時間復(fù)雜度，每次比較的平均時間復(fù)雜度為O(1)，假設(shè)輸入為隨機(jī)整數(shù);排序使用快排，復(fù)雜度為O(nlgn)，所以最終時間復(fù)雜度為O(nlgn)�？臻g復(fù)雜度就是O(n)。
算法證明的話我倒是一時半會兒沒搞出來。
在一個有1000萬用戶的系統(tǒng)中
在一個有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、盡可能高效。
解答:
考慮了很久還是決定用數(shù)據(jù)庫做，設(shè)計表。完全沒有海量數(shù)據(jù)的表結(jié)構(gòu)設(shè)計的經(jīng)驗(yàn)，因此都是靠感覺來。沒用什么技巧，除了數(shù)據(jù)庫的水平分庫。
數(shù)據(jù)庫結(jié)構(gòu)設(shè)計為4張表，結(jié)構(gòu)如下(引用只是表示關(guān)聯(lián)關(guān)系，并非加上外鍵約束)：
User
int uid#主鍵
char(12) username
Friend
int uid#用戶uid，引用User.uid，加索引
int fuid#朋友uid，引用User.uid，加索引
Blog
int blogid#主鍵
int uid#發(fā)表用戶uid，引用User.uid，加索引
varchar(60) title
text content
datetime publish_time
Feed#存儲每個用戶的好友feed列表
int uid#引用User.uid，加索引
int blogid#引用Blog.blogid，加索引
varchar(60) title#可有可無，根據(jù)生成Feed是否需要Feed標(biāo)題決定
在存儲方面，F(xiàn)riend表和Feed表數(shù)量較大，因此采用水平分庫存儲的形式。即Friend表分散在幾個數(shù)據(jù)庫內(nèi)，按照第一個uid的最后幾位進(jìn)行劃分。如有10個數(shù)據(jù)庫，即可根據(jù)個位數(shù)映射到0-9號數(shù)據(jù)庫上。同理可得Feed表的存儲方式，按照uid進(jìn)行水平分庫。
如果用戶a和用戶b是好朋友，則在Friend表中添加(a，b)和(b，a)兩條記錄，分別添加到a，b所屬的庫里。解除關(guān)系的話刪除這兩條記錄。
用戶發(fā)表文章的時候，首先在Blog表添加一條記錄;第二，查詢Friend表得出當(dāng)前用戶的所有好友，然后給Feed表添加記錄，格式為(好友id， blogid， title)，一共添加好友個數(shù)條記錄。第三查詢所有好友的Feed數(shù)記錄，如果Feed超過了1000條，則刪除該好友最早的一條Feed。第二第三步可以根據(jù)好友uid，把存儲在相同庫的好友Feed在同一次操作里批量添加/查詢/刪除。
用戶要得到自己的Feed列表，只需要先計算自己的uid屬于哪個數(shù)據(jù)庫，然后從該數(shù)據(jù)庫里取出所有的Feed記錄，即可以快速得到
【2016年百度筆試經(jīng)驗(yàn)】相關(guān)文章：
百度筆試經(jīng)驗(yàn)分享11-19
強(qiáng)生筆試經(jīng)驗(yàn)會計筆試經(jīng)驗(yàn)分享07-08
百度面試經(jīng)驗(yàn)08-11
百度筆試題及答案11-23
百度合肥筆試題目11-10
百度面試經(jīng)驗(yàn)分享02-06