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

　　Pfix T to S

　　else

　　insert J in S after T

　　不過這個題目還有一個問題：對于每個字符串，生成的期望個數(shù)并不一定為整數(shù)。例子中的N改成5的話，那就是期望輸出1.5個a和2.5個de，隨機序列自然沒法搞。這個時候回到第一個方法仍然可以做，不過題目也因此解釋不通了。同學(xué)的解釋是，如果是期望輸出1.4個a和2.6個de，這一個a和de的爭議值，在2/5的情況下輸出a，剩下的情況輸出b。不過我們其實是沒有理由把這個不確定的情況限制在一個整數(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)的文字說明，并使用上面給出的例子試驗?zāi)愕乃惴ā?/p>

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

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

　　解答:

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

　　時間復(fù)雜度，每次比較的平均時間復(fù)雜度為O(1)，假設(shè)輸入為隨機整數(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)驗，因此都是靠感覺來。沒用什么技巧，除了數(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標題決定

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

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

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

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