百度筆試題和面試題答案（2019最新）(二)

　　順著百度的筆試不可能那么弱智的想法，同時給出的例子也符合第二種情況的形勢，就照著第二種思路往下做。這個題目在從鼓樓到浦口的鼓揚線上最近剛看過，就是編程珠璣II(More Programming Pearls) ，第13章的內容(絕妙的取樣)。對于這個題，就是給出abc2, a3, de5，輸出隨機排列。比較笨的算法就是每次得到一個隨機數，如果這個隨機數代表的球已經耗盡，那就取下一個隨機數。這樣的缺點是效率低，越往后效率越低，基本是在拼RP。還是拿例子說事兒，如果隨機數為1-2，則輸出abc，3-5輸出a，6-10輸出de。如果到了第9次，還剩下一個abc沒輸出，則要一直隨機到出現1，2為止才結束。

　　第二種辦法是Floyd提出來的(似乎就是那個Floyd-Warshall)。算法如下：

　　S = []

　　for j= 1 to N do

　　T = RandInt(1, j);

　　if T is not in S then

　　Pfix T to S

　　else

　　insert J in S after T

　　不過這個題目還有一個問題：對于每個字符串，生成的期望個數并不一定為整數。例子中的N改成5的話，那就是期望輸出1.5個a和2.5個de，隨機序列自然沒法搞。這個時候回到第一個方法仍然可以做，不過題目也因此解釋不通了。同學的解釋是，如果是期望輸出1.4個a和2.6個de，這一個a和de的爭議值，在2/5的情況下輸出a，剩下的情況輸出b。不過我們其實是沒有理由把這個不確定的情況限制在一個整數單位區間里的，即對于1.4個a和2.6個 de，必須輸出1a+3de或者2a+2de才算合法輸出，而把4de，3a+1de的情況定位非法。我覺得這塊說不同，所以不需要考慮非整數的不確定情況(如果直接四舍五入到整數，還是算整數的確定情況的)。

　　設有n個正整數

　　設有n個正整數，將它們聯接成一排，組成一個最小的多位整數。

　　程序輸入：n個數

　　程序輸出：聯接成的多位數

　　例如：

　　n=2時，2個整數32，321連接成的最小整數為：32132，

　　n=4時，4個整數55，31，312, 33 聯接成的最小整數為：312313355

　　[題目要求]

　　1. 給出偽代碼即可，請給出對應的文字說明，并使用上面給出的例子試驗你的算法。

　　2. 給出算法的時間空間復雜度。

　　3. 證明你的算法。(非常重要)

　　解答:

　　這題我沒怎么考慮。同學的思想在于，把n個正整數按優先級排個序，然后按照排序的結果從小到大排列組成最小的整數。注意這個排序并不是普通的算術排序，而是基于一定的規則。比較的時候把兩個數字當成字符串進行字典排序，如果一個數字正好是另外一個數字的前綴的時候，去掉較長字符串的前綴，繼續進行比較，直到分出勝負。當然也有旗鼓相當的時候，比如31和313131，這兩者的優先級即相同。

　　時間復雜度，每次比較的平均時間復雜度為O(1)，假設輸入為隨機整數;排序使用快排，復雜度為O(nlgn)，所以最終時間復雜度為O(nlgn)�？臻g復雜度就是O(n)。

　　算法證明的話我倒是一時半會兒沒搞出來。

　　在一個有1000萬用戶的系統中

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

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

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

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

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

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

　　題目：請在以上限制條件下，設計一個高效的feed訪問系統。

　　要求：

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

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

　　3、盡可能高效。

　　解答:

　　考慮了很久還是決定用數據庫做，設計表。完全沒有海量數據的表結構設計的經驗，因此都是靠感覺來。沒用什么技巧，除了數據庫的水平分庫。

　　數據庫結構設計為4張表，結構如下(引用只是表示關聯關系，并非加上外鍵約束)：

　　User

　　int uid#主鍵

　　char(12) username

　　Friend

　　int uid#用戶uid，引用User.uid，加索引

　　int fuid#朋友uid，引用User.uid，加索引

　　Blog

　　int blogid#主鍵

　　int uid#發表用戶uid，引用User.uid，加索引

　　varchar(60) title

　　text content

　　datetime publish_time

　　Feed#存儲每個用戶的好友feed列表

　　int uid#引用User.uid，加索引

　　int blogid#引用Blog.blogid，加索引

　　varchar(60) title#可有可無，根據生成Feed是否需要Feed標題決定

　　在存儲方面，Friend表和Feed表數量較大，因此采用水平分庫存儲的形式。即Friend表分散在幾個數據庫內，按照第一個uid的最后幾位進行劃分。如有10個數據庫，即可根據個位數映射到0-9號數據庫上。同理可得Feed表的存儲方式，按照uid進行水平分庫。

　　如果用戶a和用戶b是好朋友，則在Friend表中添加(a,b)和(b,a)兩條記錄，分別添加到a，b所屬的庫里。解除關系的話刪除這兩條記錄。

　　用戶發表文章的時候，首先在Blog表添加一條記錄;第二，查詢Friend表得出當前用戶的所有好友，然后給Feed表添加記錄，格式為(好友id, blogid, title)，一共添加好友個數條記錄。第三查詢所有好友的Feed數記錄，如果Feed超過了1000條，則刪除該好友最早的一條Feed。第二第三步可以根據好友uid，把存儲在相同庫的好友Feed在同一次操作里批量添加/查詢/刪除。

　　用戶要得到自己的Feed列表，只需要先計算自己的uid屬于哪個數據庫，然后從該數據庫里取出所有的Feed記錄，即可以快速得到