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

　　第二種辦法是Floyd提出來的(似乎就是那個(gè)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

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

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

　　設(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)的文字說明，并使用上面給出的例子試驗(yàn)?zāi)愕乃惴ā?/p>

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

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

　　解答:

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

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

　　算法證明的話我倒是一時(shí)半會(huì)兒沒搞出來。

　　在一個(gè)有1000萬用戶的系統(tǒng)中

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

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

　　2、好友：用戶之間可以形成好友關(guān)系，好友是雙向的;比如說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增加量每天在百萬量級(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、盡可能高效。

　　解答:

　　考慮了很久還是決定用數(shù)據(jù)庫做，設(shè)計(jì)表。完全沒有海量數(shù)據(jù)的表結(jié)構(gòu)設(shè)計(jì)的經(jīng)驗(yàn)，因此都是靠感覺來。沒用什么技巧，除了數(shù)據(jù)庫的水分庫。

　　數(shù)據(jù)庫結(jié)構(gòu)設(shè)計(jì)為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#存儲(chǔ)每個(gè)用戶的好友feed列表

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

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

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

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

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

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

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