1、介紹一下項(xiàng)目。
2、提了一個(gè)問(wèn)題：上千萬(wàn)條記錄，統(tǒng)計(jì)出重復(fù)記錄最多的前N條。
3、一個(gè)概率題：54張撲克牌，除去兩張大小王剩下52張撲克牌。問(wèn)紅桃A和黑桃A同時(shí)被一個(gè)人拿到的概率是多少?
4、多個(gè)線程訪問(wèn)共享內(nèi)存時(shí)因該怎么辦?
5、在寫(xiě)程序遇到問(wèn)題的時(shí)候，通常采用什么調(diào)試方法?
6、一個(gè)client/server的協(xié)議問(wèn)題
7、剩下就是隨便聊聊，比如有缺點(diǎn)、期望工作的性質(zhì)、職業(yè)規(guī)劃等
百度電話面試題目：
1.談?wù)勀銓?duì)數(shù)據(jù)庫(kù)中索引的理解
2.現(xiàn)在普通關(guān)系數(shù)據(jù)庫(kù)用得數(shù)據(jù)結(jié)構(gòu)是什么類型的數(shù)據(jù)結(jié)構(gòu)
3.索引的優(yōu)點(diǎn)和缺點(diǎn)
4.session和cache的區(qū)別是什么
5.如果有幾千個(gè)session，怎么提高效率
6.session是存儲(chǔ)在什么地方，以什么形式存儲(chǔ)的。
給定二叉樹(shù)前序序列："EDBA**C***HF*G***" 。
構(gòu)建此二叉樹(shù)(非遞歸)，
并后序輸出二叉樹(shù)(非遞歸)...。
百度面試題：從輸入url到顯示網(wǎng)頁(yè)，后臺(tái)發(fā)生了什么？
2010-09-11 10:31
當(dāng)在瀏覽器中輸入一個(gè) url 后回車(chē)，后臺(tái)發(fā)生了什么？比如輸入 http://hi.baidu.com/mianshiti 后，你看到了IT面試題的博客首頁(yè)，那么這一切是如何發(fā)生的呢？
簡(jiǎn)單來(lái)說(shuō)有以下步驟：
1. 查找域名對(duì)應(yīng)的IP地址。這一步會(huì)依次查找瀏覽器緩存，系統(tǒng)緩存，路由器緩存，ISP DNS緩存，根域名服務(wù)器。
2. 向IP對(duì)應(yīng)的服務(wù)器發(fā)送請(qǐng)求。
3. 服務(wù)器響應(yīng)請(qǐng)求，發(fā)回網(wǎng)頁(yè)內(nèi)容。
4. 瀏覽器解析網(wǎng)頁(yè)內(nèi)容。
當(dāng)然，由于網(wǎng)頁(yè)可能有重定向，或者嵌入了圖片，AJAX，其它子網(wǎng)頁(yè)等等，這4個(gè)步驟可能反復(fù)進(jìn)行多次才能將最終頁(yè)面展示給用戶。
百度面試題：三個(gè)警察和三個(gè)囚徒的過(guò)河問(wèn)題
2010-04-03 21:30
三個(gè)警察和三個(gè)囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次只能載2人。存在如下的危險(xiǎn)：無(wú)論在河的哪邊，當(dāng)囚徒人數(shù)多于警察的人數(shù)時(shí)，將有警察被囚徒殺死。
問(wèn)題：請(qǐng)問(wèn)如何確定渡河方案，才能保證6人安全無(wú)損的過(guò)河。
警察囚徒過(guò)去，警察回來(lái)
囚徒囚徒過(guò)去，囚徒回來(lái)
警察警察過(guò)去，警察囚徒回來(lái)
警察警察過(guò)去，囚徒回來(lái)
囚徒囚徒過(guò)去，囚徒回來(lái)
囚徒囚徒過(guò)去
百度面試題：設(shè)計(jì)DNS服務(wù)器中cache的數(shù)據(jù)結(jié)構(gòu)
2010-03-25 21:30
要求設(shè)計(jì)一個(gè)DNS的Cache結(jié)構(gòu)，要求能夠滿足每秒5000以上的查詢，滿足IP數(shù)據(jù)的快速插入，查詢的速度要快。（題目還給出了一系列的數(shù)據(jù)，比如：站點(diǎn)數(shù)總共為5000萬(wàn)，IP地址有1000萬(wàn)，等等）
DNS服務(wù)器實(shí)現(xiàn)域名到IP地址的轉(zhuǎn)換。
每個(gè)域名的平均長(zhǎng)度為25個(gè)字節(jié)（估計(jì)值），每個(gè)IP為4個(gè)字節(jié)，所以Cache的每個(gè)條目需要大概30個(gè)字節(jié)。
總共50M個(gè)條目，所以需要1.5G個(gè)字節(jié)的空間。可以放置在內(nèi)存中。（考慮到每秒5000次操作的限制，也只能放在內(nèi)存中。）
可以考慮的數(shù)據(jù)結(jié)構(gòu)包括hash_map，字典樹(shù)，紅黑樹(shù)等等。
我覺(jué)得比較好的解決方法是，將每一個(gè)URL字符串轉(zhuǎn)化為MD5值，作為key，建立最大或最小堆，這樣插入和查找的效率都是O(log(n))。
MD5是128bit的大整數(shù)也就是16byte，比直接存放URL要節(jié)省的多。
百度面試題：將多個(gè)集合合并成沒(méi)有交集的集合
2010-03-20 18:25
給定一個(gè)字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無(wú)交集，例如上例應(yīng)輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
（1）請(qǐng)描述你解決這個(gè)問(wèn)題的思路；
（2）請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度
（3）請(qǐng)描述可能的改進(jìn)。
集合使用hash_set來(lái)表示，這樣合并時(shí)間復(fù)雜度比較低。
1. 給每個(gè)集合編號(hào)為0，1，2，3...
2. 創(chuàng)建一個(gè)hash_map，key為字符串，value為一個(gè)鏈表，鏈表節(jié)點(diǎn)為字符串所在集合的編號(hào)。遍歷所有的集合，將字符串和對(duì)應(yīng)的集合編號(hào)插入到hash_map中去。
3. 創(chuàng)建一個(gè)長(zhǎng)度等于集合個(gè)數(shù)的int數(shù)組，表示集合間的合并關(guān)系。例如，下標(biāo)為5的元素值為3，表示將下標(biāo)為5的集合合并到下標(biāo)為3的集合中去。
開(kāi)始時(shí)將所有值都初始化為-1，表示集合間沒(méi)有互相合并。
在集合合并的過(guò)程中，我們將所有的字符串都合并到編號(hào)較小的集合中去。
遍歷第二步中生成的hash_map，對(duì)于每個(gè)value中的鏈表，首先找到最小的集合編號(hào)（有些集合已經(jīng)被合并過(guò)，需要順著合并關(guān)系數(shù)組找到合并后的集合編號(hào)），然后將鏈表中所有編號(hào)的集合都合并到編號(hào)最小的集合中（通過(guò)更改合并關(guān)系數(shù)組）。
4.現(xiàn)在合并關(guān)系數(shù)組中值為-1的集合即為最終的集合，它的元素來(lái)源于所有直接或間接指向它的集合。
題目中的例子：
0: {aaa bbb ccc}
1: {bbb ddd}
2: {eee fff}
3: {ggg}
4: {ddd hhh}
生成的hash_map，和處理完每個(gè)值后的合并關(guān)系數(shù)組分別為
aaa: 0。[-1, -1, -1, -1, -1]
bbb: 0, 1。[-1, 0, -1, -1, -1]
ccc: 0。[-1, 0, -1, -1, -1]
ddd: 1, 4。[-1, 0, -1, -1, 0]
eee: 2。[-1, 0, -1, -1, 0]
fff: 2。[-1, 0, -1, -1, 0]
ggg: 3。[-1, 0, -1, -1, 0]
hhh: 4。[-1, 0, -1, -1, 0]
所以合并完后有三個(gè)集合，第0，1，4個(gè)集合合并到了一起，
第2，3個(gè)集合沒(méi)有進(jìn)行合并。
算法的復(fù)雜度為O(n)，其中n為所有集合中的元素個(gè)數(shù)。
哈希表加并差集，先用哈希把字符串轉(zhuǎn)成整數(shù)，轉(zhuǎn)換的時(shí)候就用并差集來(lái)操作求集合的并，建立哈希O(n) 哈希查詢O(1) 并差集復(fù)雜度不好估計(jì)，大概為a*O(1)
五桶球，一桶不正常，不知道球的重量和輕重關(guān)系，用天平稱一次找出那桶不正常的球。
面試題匯總：
1.描述一下自己以前做過(guò)的與這個(gè)職位相關(guān)的一些經(jīng)歷，2-3分鐘時(shí)間（從開(kāi)始接觸測(cè)試，到自己的實(shí)習(xí)經(jīng)歷balabala）
2.詳細(xì)描述一下跟這個(gè)職位最接近的實(shí)習(xí)工作的具體內(nèi)容
3.如果進(jìn)了百度，你覺(jué)得你每天都要做些什么樣的工作呢
4.如何測(cè)試百度搜索引擎
5.算法：2n個(gè)數(shù)，一半奇數(shù)，一半偶數(shù)，設(shè)計(jì)一個(gè)程序讓奇數(shù)位上的數(shù)是奇數(shù)，偶數(shù)位上的是偶數(shù)，并計(jì)算程序的空間復(fù)雜度和時(shí)間復(fù)雜度
6.開(kāi)放性問(wèn)題：怎么樣統(tǒng)計(jì)世界上一共有多少個(gè)理發(fā)師
7.現(xiàn)在有一臺(tái)打印機(jī)或者多臺(tái)打印機(jī)，你要怎么樣進(jìn)行測(cè)試，要測(cè)哪些點(diǎn)
2011年百度質(zhì)量部—測(cè)試工程師
1.定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)能夠得到棧的最小元素，要求min，push，及pop的時(shí)間復(fù)雜度都是0（1），簡(jiǎn)要描述思路。2.這道題是一個(gè)程序題，要求寫(xiě)出運(yùn)行結(jié)果，及分析程序的不安全因素。
3.分別采用線性表，二叉平衡樹(shù)木，哈希存儲(chǔ)數(shù)據(jù)，分析優(yōu)劣。
4.有一串首位相連的珠子，m個(gè)，都有自己的顏色，全部顏色共有n（n<10）種，在里面截取一段，要求包含所有顏色，并且長(zhǎng)度越短越好，如何截??？
5.設(shè)計(jì)一個(gè)strmuncmp函數(shù)，比普通的strcmp差別在于當(dāng)字符串遇到數(shù)字時(shí)，以數(shù)字的大小為準(zhǔn)，只有其中一字字符串味數(shù)字的情況，仍用strcmp函數(shù)比較
6.在大規(guī)模數(shù)據(jù)處理中處理一個(gè)詞搭配字典，條件為：
1）字典中存在的項(xiàng)是兩個(gè)詞的搭配例如：“今天”和“晚上”，他們組成的搭配為“今天晚上”“晚上今天”
2）10萬(wàn)量級(jí)的詞集合
3）一個(gè)詞并不會(huì)和其他所有詞搭配，通常只有和不超過(guò)1萬(wàn)個(gè)其他詞搭配
4）字典使用的讀操作很多，通常每秒鐘有上千次請(qǐng)求幾乎沒(méi)寫(xiě)入要求
請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典服務(wù)系統(tǒng)，當(dāng)請(qǐng)求時(shí)兩個(gè)詞的搭配時(shí)候，能夠快速返回搭配的相關(guān)信息，請(qǐng)使用盡可能少的資源，并估算出是使用的機(jī)器資源
今下午兩點(diǎn)剛面完
1、用c完成一個(gè)函數(shù)char* function（char * s，int n），返回s的前n個(gè)字符（這里不清楚char*可以指一個(gè)字符串？），要求盡量考慮健壯性。
磨了幾分鐘發(fā)現(xiàn)還是不會(huì)用c，后來(lái)允許用java后寫(xiě)出來(lái)了個(gè)，沒(méi)怎么考慮太多異常情況。之后又問(wèn)了加入自己測(cè)試這個(gè)函數(shù)，應(yīng)該怎么測(cè)試。balabala了些數(shù)據(jù)
2、假設(shè)有N個(gè)（大約幾百萬(wàn)個(gè)文件），每個(gè)文件存儲(chǔ)的都是英文單詞，文件大小都是1MB左右。輸入一個(gè)單詞，輸出包含這個(gè)單詞的文件名（按文件大小排序）。要求盡量?jī)?yōu)化算法。
一開(kāi)始，理解成文件里面存的是不定長(zhǎng)的連續(xù)字符串了，光給了個(gè)分塊掃描，還想著用KMP，被否決；磨了一段時(shí)間，后來(lái)發(fā)現(xiàn)文件的單詞是用空格隔開(kāi)的。再提示下，給出了個(gè)多叉樹(shù)結(jié)構(gòu)（類似于字典樹(shù)？），每個(gè)節(jié)點(diǎn)存儲(chǔ)包含這個(gè)單詞的文件名鏈表。
再問(wèn)把文件名插入鏈表的時(shí)候如何考慮最優(yōu)算法（要排序）。先說(shuō)了個(gè)遍歷，被否決，二分查找之類的也不行；后來(lái)想到二叉排序樹(shù)，提到了，好像這個(gè)就是面試官要的答案，不過(guò)我又提出用排序樹(shù)查詢方便，但是輸出排序的結(jié)果（深度或廣度遍歷）沒(méi)有直接鏈表遍歷方便。
3、問(wèn)了個(gè)socket編程，如何設(shè)計(jì)服務(wù)器端。
回答多線程，每一個(gè)請(qǐng)求開(kāi)一個(gè)線程。又問(wèn)假設(shè)大量用戶請(qǐng)求來(lái)到的話如何優(yōu)化（提示線程的創(chuàng)建與銷(xiāo)毀比較耗資源）。想到數(shù)據(jù)庫(kù)連接池的原理，套用在這里（其實(shí)不知道socket能不能這樣用），貌似面試官還比較滿意。
4、一個(gè)數(shù)據(jù)庫(kù)，為了保證響應(yīng)速率，會(huì)在數(shù)據(jù)庫(kù)和客戶端之間建立一個(gè)緩存，緩存里存儲(chǔ)數(shù)據(jù)庫(kù)常用的結(jié)果（容量為10000條item或1GB）?？蛻舳讼炔樵兙彺?，若沒(méi)有結(jié)果再查詢數(shù)據(jù)庫(kù)，當(dāng)查到結(jié)果之后再把這條結(jié)果添加到緩存中。對(duì)緩存的操作包括添加、刪除、搜索item。 要求盡量全面的測(cè)試這個(gè)架構(gòu)。
5、其他還問(wèn)了對(duì)測(cè)試流程的理解，問(wèn)了下實(shí)習(xí)情況。面試結(jié)束的時(shí)候還追加了UNIX下I/O模式？和如何在linux下查看程序資源消耗情況（這兩個(gè)都不會(huì)）
總結(jié)：發(fā)覺(jué)這個(gè)面試還是比較靠人品，上午宿舍的被問(wèn)的都是具體的網(wǎng)絡(luò)知識(shí)和一道蠻難的編程題，而我這個(gè)還是比較開(kāi)放性的問(wèn)題，面試的jj也比較好說(shuō)話。另外簡(jiǎn)歷上沒(méi)測(cè)試的內(nèi)容貌似也不太要緊（我是基本一點(diǎn)都沒(méi)有）。但是測(cè)試的基本原理和概念還是得知道的。
有一根27厘米的細(xì)木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個(gè)位置上各有一只螞蟻。木桿很細(xì)，不能同時(shí)通過(guò)一只螞蟻。開(kāi)始時(shí)，螞蟻的頭朝左還是朝右是任意的，它們只會(huì)朝前走或調(diào)頭，但不會(huì)后退。當(dāng)任意兩只螞蟻碰頭時(shí)，兩只螞蟻會(huì)同時(shí)調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。編寫(xiě)程序，求所有螞蟻都離開(kāi)木桿的最小時(shí)間和最大時(shí)間。
百度面試題。
1.
·談?wù)勀銓?duì)數(shù)據(jù)庫(kù)中索引的理解
R1.
使用索引可快速訪問(wèn)數(shù)據(jù)庫(kù)表中的特定信息。索引是對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，例如 employee 表的姓（lname）列。如果要按姓查找特定職員，與必須搜索表中的所有行相比，索引會(huì)幫助您更快地獲得該信息。
建立索引的優(yōu)點(diǎn)
1.大大加快數(shù)據(jù)的檢索速度;
2.創(chuàng)建唯一性索引，保證數(shù)據(jù)庫(kù)表中每一行數(shù)據(jù)的唯一性;
3.加速表和表之間的連接;
4.在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，可以顯著減少查詢中分組和排序的時(shí)間。
索引的缺點(diǎn)
1.索引需要占物理空間。
2.當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)的維護(hù)，降低了數(shù)據(jù)的維護(hù)速度。
唯一索引
唯一索引是不允許其中任何兩行具有相同索引值的索引。
當(dāng)現(xiàn)有數(shù)據(jù)中存在重復(fù)的鍵值時(shí)，大多數(shù)數(shù)據(jù)庫(kù)不允許將新創(chuàng)建的唯一索引與表一起保存。數(shù)據(jù)庫(kù)還可能防止添加將在表中創(chuàng)建重復(fù)鍵值的新數(shù)據(jù)。例如，如果在 employee 表中職員的姓 (lname) 上創(chuàng)建了唯一索引，則任何兩個(gè)員工都不能同姓。
主鍵索引
數(shù)據(jù)庫(kù)表經(jīng)常有一列或列組合，其值唯一標(biāo)識(shí)表中的每一行。該列稱為表的主鍵。
在數(shù)據(jù)庫(kù)關(guān)系圖中為表定義主鍵將自動(dòng)創(chuàng)建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個(gè)值都唯一。當(dāng)在查詢中使用主鍵索引時(shí)，它還允許對(duì)數(shù)據(jù)的快速訪問(wèn)。
聚集索引
在聚集索引中，表中行的物理順序與鍵值的邏輯（索引）順序相同。一個(gè)表只能包含一個(gè)聚集索引。
如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數(shù)據(jù)訪問(wèn)速度。
2.
現(xiàn)在普通關(guān)系數(shù)據(jù)庫(kù)用得數(shù)據(jù)結(jié)構(gòu)是什么類型的數(shù)據(jù)結(jié)構(gòu)
3.
索引的優(yōu)點(diǎn)和缺點(diǎn)
4.
session 和 cache 的區(qū)別是什么
R4.
Session 是單用戶的會(huì)話狀態(tài)。
當(dāng)用戶訪問(wèn)網(wǎng)站時(shí)，產(chǎn)生一個(gè) SESSIONID。并存在于 COOKIES 中。每次向服務(wù)器請(qǐng)求時(shí)，發(fā)送這個(gè) COOKIES ，再?gòu)姆?wù)器中檢索是否有這個(gè) SESSIONID 保存的數(shù)據(jù)。。。
而 CACHE ，則是服務(wù)器端的緩存，是所有用戶都可以訪問(wèn)和共享的。
5.
如果有幾千個(gè) session，怎么提高效率
6.
session 是存儲(chǔ)在什么地方，以什么形式存儲(chǔ)的
R6.
session是存在服務(wù)器的內(nèi)存中
每個(gè)會(huì)話對(duì)應(yīng)一個(gè)sessionId
通過(guò)sessionId開(kāi)區(qū)分是那個(gè)會(huì)話的session
7.
多人排成一個(gè)隊(duì)列,我們認(rèn)為從低到高是正確的序列,但是總有部分人不遵守秩序。如果說(shuō),前面的人比后面的人高(兩人身高一樣認(rèn)為是合適的),那么我們就認(rèn)為這兩個(gè)人是一對(duì)“搗亂分子”,比如說(shuō),現(xiàn)在存在一個(gè)序列:
176, 178, 180, 170, 171
這些搗亂分子對(duì)為<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,現(xiàn)在給出一個(gè)整型序列,請(qǐng)找出這些搗亂分子對(duì)的個(gè)數(shù)(僅給出搗亂分子對(duì)的數(shù)目即可,不用具體的對(duì))
要求：
輸入:
為一個(gè)文件(in)，文件的每一行為一個(gè)序列。序列全為數(shù)字，數(shù)字間用”,”分隔。
輸出：
為一個(gè)文件(out)，每行為一個(gè)數(shù)字，表示搗亂分子的對(duì)數(shù)。
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。并給出實(shí)現(xiàn)的代碼 ，并分析時(shí)間復(fù)雜度。
限制：
輸入每行的最大數(shù)字個(gè)數(shù)為100000個(gè)，數(shù)字最長(zhǎng)為6位。程序無(wú)內(nèi)存使用限制。
9.
考慮一個(gè)在線好友系統(tǒng)。系統(tǒng)為每個(gè)用戶維護(hù)一個(gè)好友列表，列表限制最多可以有500個(gè)好友，好友必須是這個(gè)系統(tǒng)中的其它用戶。好友關(guān)系是單向的，用戶B是用戶A的好友，但A不一定是B的好友。
用戶以ID形式表示，現(xiàn)給出好友列表數(shù)據(jù)的文本形式如下：
1 3,5,7,67,78,3332
2 567,890
31 1,66
14 567
78 10000
…
每行數(shù)據(jù)有兩列，第一列為用戶ID，第二列為其好友ID，不同ID間用”,”分隔，ID升序排列。列之間用”t”分隔。
要求：
請(qǐng)?jiān)O(shè)計(jì)合適的索引數(shù)據(jù)結(jié)構(gòu)，來(lái)完成以下查詢：
給定用戶A和B，查詢A和B之間是否有這樣的關(guān)系：B是A的二維好友（好友的好友）。
如上例中，10000為1的二維好友，因?yàn)?8為1的好友，10000為78的好友。
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。并給出實(shí)現(xiàn)的偽代碼實(shí)現(xiàn)建立索引過(guò)程和查詢過(guò)程，并說(shuō)明空間和時(shí)間復(fù)雜度。
限制：
用戶數(shù)量不超過(guò)1000萬(wàn)，平均50個(gè)好友。
10.
有關(guān)系模式：User（userId, userName）， Article（articleId, userId, title, content），Vote（articleId, score），User為用戶關(guān)系，Article為用戶發(fā)表的文章關(guān)系，Vote為文章得票關(guān)系，title為文章標(biāo)題、score為得票數(shù)。
（1）用SQL語(yǔ)言查詢所有沒(méi)發(fā)表過(guò)文章的用戶名；
（2）用SQL語(yǔ)言查詢得票數(shù)大于100的所有文章標(biāo)題，按得票數(shù)倒序排列；
（3）用SQL語(yǔ)言查詢出發(fā)表文章數(shù)大于5，文章平均得票數(shù)大于100的用戶名，按平均得票數(shù)倒序排列；
（4）設(shè)計(jì)這些表的主鍵、外鍵和索引，并指出上面三個(gè)查詢所使用的索引。
（5）當(dāng)用戶數(shù)超過(guò)1000萬(wàn)，文章數(shù)超過(guò)1億時(shí)，如何考慮存儲(chǔ)及性能的改進(jìn)和優(yōu)化？
11.
每天論壇訪問(wèn)量300萬(wàn)左右，更新帖子10萬(wàn)左右。
請(qǐng)給出數(shù)據(jù)庫(kù)表結(jié)構(gòu)設(shè)計(jì)，并結(jié)合范式簡(jiǎn)要說(shuō)明設(shè)計(jì)思路。
R11.
這是我看見(jiàn)的百度面試題，以前也在cdsn上面看見(jiàn)過(guò)類似的問(wèn)題，沒(méi)有仔細(xì)想就寫(xiě)了自己的見(jiàn)解和答案，很可惜我以前的想法是錯(cuò)誤的；算是誤人子弟阿，郁悶！因此我還是先把和幾個(gè)朋友討論的結(jié)果和自己的想法做一個(gè)總結(jié)，算是彌補(bǔ)我以前想法造成別人曲解的過(guò)錯(cuò)； 首先，我們先來(lái)分析一下這道面試題：用戶名，email，主頁(yè)，電話，聯(lián)系地址，發(fā)帖標(biāo)題，發(fā)帖內(nèi)容，回復(fù)標(biāo)題，回復(fù)內(nèi)容。這些字段可以基本歸為三類：
1、用戶基本信息：用戶名(UserName)，email(Email)，主頁(yè)(HomePage)，電話(Tel)，聯(lián)系地址(Address)；
2、發(fā)帖主題信息：發(fā)帖標(biāo)題(Title)，發(fā)帖內(nèi)容(Content)；
3、回復(fù)信息：回復(fù)標(biāo)題(RTitle)，回復(fù)內(nèi)容(RContent)；
以上一步有基本開(kāi)發(fā)經(jīng)驗(yàn)的人都知道，只是對(duì)基本的信息進(jìn)行劃分；相信將用戶基本信息存放在一張表內(nèi)不會(huì)有什么好討論的，我創(chuàng)建一張表叫T_Users，并建立主鍵UserID，用戶基本信息所需要存放的內(nèi)容都放置在此表內(nèi)；那么是應(yīng)該把發(fā)帖主題和回復(fù)信息分別創(chuàng)建兩張表存放數(shù)據(jù)呢還是應(yīng)該存放在一張表內(nèi)？字段內(nèi)容還是比較接近的，因此從數(shù)據(jù)冗余的角度看，一張表和兩張表在此方面的區(qū)別并不影響設(shè)計(jì)；假設(shè)按照大多數(shù)論壇的設(shè)計(jì)思路，將2、3設(shè)計(jì)成兩個(gè)表T_Topics和T_Reverts后，再來(lái)分析看看是否合適這里的要求；
現(xiàn)在“每天論壇訪問(wèn)量300萬(wàn)左右，更新帖子10萬(wàn)左右”對(duì)這句話進(jìn)行分析，才是這個(gè)面試題的關(guān)鍵所在。面試題顯然要求在操作數(shù)據(jù)庫(kù)的性能方面要有更高的要求。而對(duì)數(shù)據(jù)庫(kù)的操作而言，檢索數(shù)據(jù)的性能基本不會(huì)對(duì)數(shù)據(jù)造成很大的影響（精確查找的情況下），而對(duì)表與表之間的連接卻會(huì)產(chǎn)生巨大的影響，特別在有巨量數(shù)據(jù)的表之間；而對(duì)數(shù)據(jù)庫(kù)的連接也是相當(dāng)消耗性能的操作（這在ADO.NET的教程中都多次提醒的）；因此對(duì)問(wèn)題的定位基本可以確定：在顯示和檢索數(shù)據(jù)時(shí)，盡量減少數(shù)據(jù)庫(kù)的連接以及表與表之間的連接；
解決問(wèn)題的指導(dǎo)性原則找到了，那就來(lái)看看，從上面的設(shè)計(jì)中，有哪一些地方會(huì)產(chǎn)生我們提到的表與表之間的連接；（連接數(shù)據(jù)庫(kù)的次數(shù)盡量減少到每打開(kāi)一個(gè)頁(yè)面只連接一次數(shù)據(jù)庫(kù)就可以得到所有的數(shù)據(jù)）1、用戶基本信息中的用戶名在發(fā)帖主題列表以及打開(kāi)一個(gè)主題查看回復(fù)內(nèi)容時(shí)上面會(huì)有所顯示，需要在T_Users和其他兩張表進(jìn)行連接；2、在打開(kāi)一個(gè)主題查看回復(fù)內(nèi)容時(shí)，需要在T_Topics和T_Reverts之間進(jìn)行連接；其他應(yīng)該是不需要產(chǎn)生表與表之間的連接；按照面試題來(lái)推測(cè)：T_Users的數(shù)據(jù)量應(yīng)該在1萬(wàn)-10萬(wàn)之間，T_Topics應(yīng)該在100-1000萬(wàn)之間，T_Reverts應(yīng)該在1000萬(wàn)-1億之間；從上面兩類連接可以看出來(lái)，T_Users和T_Topics會(huì)在列表頁(yè)面連接一次；T_Users、T_Topics和T_Reverts三張表會(huì)連接一次；
我說(shuō)不上來(lái)第一種連接是否可以允許（至少在我開(kāi)發(fā)的系統(tǒng)里面都是允許的），但是另外三張表連接是絕對(duì)不會(huì)允許的！特別是T_Topics和T_Reverts兩表之間的連接會(huì)產(chǎn)生很大的性能損耗，因此需要避免這樣的情況產(chǎn)生。那怎么樣的設(shè)計(jì)可以避免T_Topics和T_Reverts兩表之間的連接呢？前面已經(jīng)進(jìn)行了分析：可以考慮把發(fā)帖主題和回復(fù)信息存放在一張表（T_Infos）里面，看看是否可以解決這個(gè)問(wèn)題；我們?cè)O(shè)計(jì)一個(gè)字段（Flag）來(lái)標(biāo)記是主題還是回復(fù)的內(nèi)容；設(shè)計(jì)一個(gè)字段（ParentID,主題此字段為ID值）來(lái)指定是哪一個(gè)特定主題的回復(fù)；在開(kāi)打回復(fù)信息時(shí)，只需要按照所知道的主題ID，就可以檢索到這個(gè)主題的內(nèi)容以及所有的回復(fù)內(nèi)容，上面指出的問(wèn)題就可以解決！
為了性能，我們?cè)僖淮螌?duì)T_Users和T_Infos連接對(duì)性能的影響進(jìn)行一下細(xì)致的分析，可以通過(guò)在T_Infos表內(nèi)增加UserName字段來(lái)解決和它的連接，這樣至少在顯示時(shí)，性能能夠得到保證；但是這樣的設(shè)計(jì)因?yàn)閁serName字段是冗余的，因此在用戶修改UserName的時(shí)候就會(huì)產(chǎn)生同步數(shù)據(jù)的問(wèn)題，這個(gè)需要程序來(lái)進(jìn)行彌補(bǔ)，并是我們認(rèn)為用戶不會(huì)經(jīng)常性的修改他的用戶名這樣的前提下；
因此這道面試題的答案應(yīng)該是設(shè)計(jì)兩張表，用戶基本信息表T_Users和內(nèi)容表T_Infos，這兩張表的連接還是通過(guò)UserID，但是T_Infos中增加UserName這個(gè)字段來(lái)增加性能！
上面的面試題算是分析完了，但是從這道題目的分析中我們可以看出來(lái)，這樣的設(shè)計(jì)是建立在“一個(gè)簡(jiǎn)單的論壇系統(tǒng)”這樣的基礎(chǔ)上的極端事例，在我們真實(shí)的世界中，不太會(huì)有很多的人喜歡這樣簡(jiǎn)單的論壇，而且這樣的論壇在擴(kuò)展性方面會(huì)產(chǎn)生很大的限制；這算不算這道題目是應(yīng)試教育的產(chǎn)物呢？而且在設(shè)計(jì)的時(shí)候不僅僅是為了適應(yīng)現(xiàn)在系統(tǒng)的需求還需要提供將來(lái)新的要求的變化，因此在實(shí)際的開(kāi)發(fā)過(guò)程中間并不推薦使用這道面試題的答案。
12.
給你a、b兩個(gè)文件，各存放50億條url，每條url各占用64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url。
R12.
可以估計(jì)每個(gè)文件的大小為5G*64=300G，遠(yuǎn)大于4G。所以不可能將其完全加載到內(nèi)存中處理?？紤]采取分而治之的方法。
遍歷文件a，對(duì)每個(gè)url求取hash(url)%1000，然后根據(jù)所得值將url分別存儲(chǔ)到1000個(gè)小文件（設(shè)為a0,a1,...a999）當(dāng)中。這樣每個(gè)小文件的大小約為300M。遍歷文件b，采取和a相同的方法將url分別存儲(chǔ)到1000個(gè)小文件(b0,b1....b999)中。這樣處理后，所有可能相同的url都在對(duì)應(yīng)的小文件(a0 vs b0, a1 vs b1....a999 vs b999)當(dāng)中，不對(duì)應(yīng)的小文件（比如a0 vs b99）不可能有相同的url。然后我們只要求出1000對(duì)小文件中相同的url即可。
比如對(duì)于a0 vs b0，我們可以遍歷a0，將其中的url存儲(chǔ)到hash_map當(dāng)中。然后遍歷b0，如果url在hash_map中，則說(shuō)明此url在a和b中同時(shí)存在，保存到文件中即可。
如果分成的小文件不均勻，導(dǎo)致有些小文件太大（比如大于2G），可以考慮將這些太大的小文件再按類似的方法分成小小文件即可。
13.
給你一個(gè)單詞a，如果通過(guò)交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞?，F(xiàn)在給你一個(gè)字典，用戶輸入一個(gè)單詞，讓你根據(jù)字典找出這個(gè)單詞有多少個(gè)兄弟單詞。 （這道題面試官說(shuō)有O(1) 的解法，。。。。。）
R13.
使用hash_map和鏈表。
首先定義一個(gè)key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。
使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。
開(kāi)始時(shí)，先遍歷字典，將每個(gè)單詞都按照key加入到對(duì)應(yīng)的鏈表當(dāng)中。當(dāng)需要找兄弟單詞時(shí)，只需求取這個(gè)單詞的key，然后到hash_map中找到對(duì)應(yīng)的鏈表即可。
這樣創(chuàng)建hash_map時(shí)時(shí)間復(fù)雜度為O(n)，查找兄弟單詞時(shí)時(shí)間復(fù)雜度是O(1)。
//////
只要定義一個(gè)合適的特征碼，然后用hash結(jié)構(gòu)保存，就可以達(dá)到O(1)的解法。
比如：對(duì)單詞aadb 定義特征碼如下a2b1d1， dddabc的特征碼是a1b1c1d3，以此類推（各位大俠可以設(shè)計(jì)更好的特征碼）。
數(shù)據(jù)結(jié)構(gòu)定義如：hash_map >,其中hash_map的key是特征碼，value是兄弟單詞集。首先掃描字典，將所有單詞的特征碼和相應(yīng)單詞集裝入這個(gè)數(shù)據(jù)結(jié)構(gòu)。
查找時(shí)，先計(jì)算出待查單詞的特征碼，然后搜索一下hash_map里相應(yīng)set的大小，就知道有多少個(gè)兄弟單詞了。
14.
五桶球，一桶不正常，不知道球的重量和輕重關(guān)系，用天平稱一次找出那桶不正常的球。
R14.
這個(gè)問(wèn)題的解法如下（首先假定只要不把球從天平拿下來(lái)就還算一次，另外每個(gè)桶內(nèi)的球是一樣的）：
1）從1號(hào)和2號(hào)桶各拿一個(gè)，放上天平（1號(hào)左，2號(hào)右），如果平衡，說(shuō)明這兩桶球都是正常的，可以做為砝碼。如果不平衡，那么1號(hào)和2號(hào)桶必有一個(gè)不正常，而其他3，4，5桶是正常的，可以作為砝碼。
2）首先考慮1號(hào)2號(hào)桶不平衡的情況，這時(shí)從1號(hào)和3號(hào)桶再各拿一個(gè)球，放上天平（1號(hào)右，3號(hào)左），如果這時(shí)平衡了，說(shuō)明1號(hào)桶是不正常的，如果還是不平衡，那么2號(hào)桶是不正常的。
3）如果第一步1號(hào)2號(hào)桶是平衡的，那么也好辦，把3，4號(hào)桶各拿一個(gè)放上天平（3號(hào)左，4號(hào)右），這時(shí)如果還是平衡的，那么5號(hào)桶必然是不正常的。如果不平衡，說(shuō)明不正常的就在3，4號(hào)桶之中。我們?cè)儆?）的方法找出來(lái)即可。
1 完成函數(shù)
size_t foo(unsigned int *a1, size_t al1, unsigned int* a2, size_t al2)
其中a1和a2都為無(wú)符號(hào)數(shù)組，al1和al2為數(shù)組的長(zhǎng)度，數(shù)組的長(zhǎng)度為偶數(shù)。
無(wú)符號(hào)數(shù)組由一對(duì)數(shù)字區(qū)間組成。如下例：
a1 為 0,1,3,6,10,20
a2 為 0,1,20,50,4,5
則 a1表示以下區(qū)間[0,1] [3,6] [10,20]
a2表示以下區(qū)間[0,1] [20,50] [4,5]
則a1,a2的重疊部分為[0,1] [4,5]，其長(zhǎng)度為2
函數(shù)foo要求返回重疊區(qū)間的長(zhǎng)度。上例中為2.
要求：
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。
寫(xiě)出函數(shù)foo原代碼，另外效率盡量高，并給出代碼的復(fù)雜性分析。
限制：
al1和al2的長(zhǎng)度不超過(guò)100萬(wàn)。而且同一個(gè)數(shù)組的區(qū)間可能出現(xiàn)重重疊。
如a1可能為 0,5, 4,8, 9,100, 70,80
使用的存儲(chǔ)空間盡量小。
2 多人排成一個(gè)隊(duì)列,我們認(rèn)為從低到高是正確的序列,但是總有部分人不遵守秩序。如果說(shuō),前面的人比后面的人高(兩人身高一樣認(rèn)為是合適的),那么我們就認(rèn)為這兩個(gè)人是一對(duì)“搗亂分子”,比如說(shuō),現(xiàn)在存在一個(gè)序列:
176, 178, 180, 170, 171
這些搗亂分子對(duì)為<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,現(xiàn)在給出一個(gè)整型序列,請(qǐng)找出這些搗亂分子對(duì)的個(gè)數(shù)(僅給出搗亂分子對(duì)的數(shù)目即可,不用具體的對(duì))
要求：
輸入:
為一個(gè)文件(in)，文件的每一行為一個(gè)序列。序列全為數(shù)字，數(shù)字間用”,”分隔。
輸出：
為一個(gè)文件(out)，每行為一個(gè)數(shù)字，表示搗亂分子的對(duì)數(shù)。
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。并給出實(shí)現(xiàn)的代碼 ，并分析時(shí)間復(fù)雜度。
限制：
輸入每行的最大數(shù)字個(gè)數(shù)為100000個(gè)，數(shù)字最長(zhǎng)為6位。程序無(wú)內(nèi)存使用限制。
二、下面是兩道選做題，請(qǐng)根據(jù)自己的情況選擇其中的一道作答(WEB方向請(qǐng)答第4道，其他職位方向答第3道）。
3
考慮一個(gè)在線好友系統(tǒng)。系統(tǒng)為每個(gè)用戶維護(hù)一個(gè)好友列表，列表限制最多可以有500個(gè)好友，好友必須是這個(gè)系統(tǒng)中的其它用戶。好友關(guān)系是單向的，用戶B是用戶A的好友，但A不一定是B的好友。
用戶以ID形式表示，現(xiàn)給出好友列表數(shù)據(jù)的文本形式如下：
1 3,5,7,67,78,3332
2 567,890
31 1,66
14 567
78 10000
…
每行數(shù)據(jù)有兩列，第一列為用戶ID，第二列為其好友ID，不同ID間用”,”分隔，ID升序排列。列之間用”t”分隔。
要求：
請(qǐng)?jiān)O(shè)計(jì)合適的索引數(shù)據(jù)結(jié)構(gòu)，來(lái)完成以下查詢：
給定用戶A和B，查詢A和B之間是否有這樣的關(guān)系：B是A的二維好友（好友的好友）。
如上例中，10000為1的二維好友，因?yàn)?8為1的好友，10000為78的好友。
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。并給出實(shí)現(xiàn)的偽代碼實(shí)現(xiàn)建立索引過(guò)程和查詢過(guò)程，并說(shuō)明空間和時(shí)間復(fù)雜度。
限制：
用戶數(shù)量不超過(guò)1000萬(wàn)，平均50個(gè)好友。
4
有關(guān)系模式：User（userId, userName）， Article（articleId, userId, title, content），Vote（articleId, score），User為用戶關(guān)系，Article為用戶發(fā)表的文章關(guān)系，Vote為文章得票關(guān)系，title為文章標(biāo)題、score為得票數(shù)。
（1）用SQL語(yǔ)言查詢所有沒(méi)發(fā)表過(guò)文章的用戶名；
（2）用SQL語(yǔ)言查詢得票數(shù)大于100的所有文章標(biāo)題，按得票數(shù)倒序排列；
（3）用SQL語(yǔ)言查詢出發(fā)表文章數(shù)大于5，文章平均得票數(shù)大于100的用戶名，按平均得票數(shù)倒序排列；
（4）設(shè)計(jì)這些表的主鍵、外鍵和索引，并指出上面三個(gè)查詢所使用的索引。
（5）當(dāng)用戶數(shù)超過(guò)1000萬(wàn)，文章數(shù)超過(guò)1億時(shí)，如何考慮存儲(chǔ)及性能的改進(jìn)和優(yōu)化？
一、選擇題：15分 共10題
1. 任何一個(gè)基于“比較”的內(nèi)部排序的算法，若對(duì)6個(gè)元素進(jìn)行排序，則在最壞情況下所需的比較次數(shù)至少為_(kāi)___。
A．10 B．11 C．21 D．36
2. 關(guān)系模型有三類完整性約束，定義外鍵實(shí)現(xiàn)的是 完整性.
A. 實(shí)體完整性 B. 參照完整性
C. 用戶定義的完整性 D. 實(shí)體完整性、參照完整性和用戶定義的完整性
3. 64位linux系統(tǒng)和機(jī)器，int類型、long類型分別占用多大的空間(字節(jié)數(shù))
A. 4,4 B. 4,8 C. 8,4 D. 8,8
4. 下面說(shuō)法正確的是：
A. 根據(jù)gprof統(tǒng)計(jì)的程序運(yùn)行時(shí)函數(shù)調(diào)用次數(shù)及執(zhí)行時(shí)間，進(jìn)行程序代碼優(yōu)化，這是amdahl定律的應(yīng)用
B. 計(jì)算機(jī)網(wǎng)絡(luò)設(shè)備的緩沖區(qū)是時(shí)間和空間局部性原理的應(yīng)用
C. 局域網(wǎng)內(nèi)的計(jì)算機(jī)發(fā)送數(shù)據(jù)包的數(shù)學(xué)模型遵循泊松分布
D. 分支預(yù)測(cè)使用先前運(yùn)行時(shí)得到的配置文件，這是依據(jù)正態(tài)分布
5. 下列敘述正確的是：
A . #define fun(x,y) (x/y)
Int I = fun(2+4, 3);
I 的值為2
B．var++ 與 ++var 沒(méi)有區(qū)別
C．C++程序，拋出異常時(shí)，一定會(huì)發(fā)生異常對(duì)象的拷貝過(guò)程
D．quick sort 是一種穩(wěn)定排序。
6. 上下文無(wú)關(guān)文法是一種____。
A 左線性文法 B 右線性文法 C 正則文法 D 以上都不上
7. 關(guān)系表達(dá)式 !(A&&(B||C)) 和下面哪個(gè)表達(dá)式表達(dá)的意思一致：
A (!(A&&B))||(!(A&&C)) B (!(A&&B))&&((!A)||(!B))
C (!(A||B))&&(!(A&&B)) D (!A)||((!B)||(!C))
8. 設(shè)int x=4; 則執(zhí)行以下語(yǔ)句: x+=x-=x-x--;后,x的值為
A. -1； B. 5； C. 7； D. 11；
9. 以下IO函數(shù)中，哪個(gè)是流式IO函數(shù)（）
A、read； B、fread； C、mmap； D、recv；
10. 已知：
struct st
{
int n；
struct st *next；
}；
static struct st a[3]={1,&a[1],2,&a[2],3,&a[0]},*p；
如果下述語(yǔ)句的顯示是2，則對(duì)p的賦值是____。
printf("%d",++(p->next->n))；
A. p=&a[0]； B. p=&a[1]； C. p=&a[2]； D. p=*a；
二、簡(jiǎn)答題：20分，共2題
1. （10分）已知某種線上服務(wù)存在3種異常D1, D2, D3，根據(jù)每天在固定時(shí)間段長(zhǎng)期人工監(jiān)控的統(tǒng)計(jì)結(jié)果，3種異常的發(fā)生率是：D1 0.28%, D2 0.12%, D3 0.32%?，F(xiàn)開(kāi)發(fā)一種監(jiān)控程序，分別對(duì)這三種異常做監(jiān)控，如果發(fā)現(xiàn)某種異常就發(fā)出相應(yīng)報(bào)警。記無(wú)異常為D4，無(wú)報(bào)警為A4。在各種異常情況下發(fā)出報(bào)警的 溉率如下表：
D1 D2 D3 D4
A1 0.90 0.06 0.02 0.02
A2 0.05 0.80 0.06 0.01
A3 0.03 0.05 0.82 0.02
A4 0.02 0.09 0.10 0.95
請(qǐng)?jiān)u價(jià)該監(jiān)控程序的敏感性和正確性。
2. （10分）以下是一個(gè)常駐內(nèi)存的C程序，請(qǐng)問(wèn)程序中有什么問(wèn)題？
int f(int number)
{
FILE * fp;
char file_name[20];
int sum=0;
for(int i=0; i<number; i++)
{
if(0==i%30)
{
sprintf(file_name, ”file_%d.txt”, i/20);
fp=fopen(file_name,”r”);
if(fp==NULL) return -1;
}
sum += i;
}
fclose(fp);
return sum;
}
三、編程題：30分 共1題
注意：要求提供完整代碼，如果可以編譯運(yùn)行酌情加分。
1. 一條1百萬(wàn)節(jié)點(diǎn)的單向鏈表，鏈表所有節(jié)點(diǎn)是按value字段從小到大的順序鏈接；下面是一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)
typedef struct node_t{
int value; /* 節(jié)點(diǎn)排序字段 */
int group; /* 組號(hào): 0,1,2,3,4,5,6,7,8,9 */
struct node_t *pnext; /* 下個(gè)節(jié)點(diǎn)的指針 */
}node_t;
node_t head; /*該單向鏈表的頭節(jié)點(diǎn)，全局變量 */
試設(shè)計(jì)程序：針對(duì)各個(gè)group(0-->9)，根據(jù)value字段排序，輸出各組top 10的節(jié)點(diǎn)。（top10是從小到大，取后面的大值top10.）
要求：盡量減少計(jì)算復(fù)雜度、遍歷次數(shù)，不允許大量的輔助內(nèi)存
四、設(shè)計(jì)題：35分 共1題
注意：請(qǐng)盡可能詳細(xì)描述你的數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、設(shè)計(jì)思路等。建議多寫(xiě)一些偽代碼或者流程說(shuō)明。
1. 設(shè)想網(wǎng)絡(luò)上的一個(gè)發(fā)送者和64個(gè)接收者，發(fā)送者每秒有不超過(guò)128條的命令產(chǎn)生，每條命令包含一個(gè)512字節(jié)的頭部command_head_t和至多4K字節(jié)的變長(zhǎng)內(nèi)容。command_head_t的結(jié)構(gòu)如下：
typedef struct {
int cmd_no; //該命令的命令號(hào)，唯一識(shí)別一個(gè)命令
int version; //產(chǎn)生該命令的程序的版本
int detail_len; //變產(chǎn)內(nèi)容的實(shí)際長(zhǎng)度
char *content; //指向變長(zhǎng)內(nèi)容的指針
…
} command_head_t;
發(fā)送者根據(jù)命令號(hào)將這些命令分別發(fā)送給接收者去處理，例如：發(fā)送者產(chǎn)生c1，c2，c3，c4命令，并設(shè)定將c1，c2命令發(fā)送到接收者r1和r2，將c2、c3，c4命令發(fā)送到r3。
接收者執(zhí)行接收到的命令，并相應(yīng)修改自己的狀態(tài)。
現(xiàn)在的問(wèn)題是：在盡可能多的考慮各種可能的意外情況下（包括但不限于網(wǎng)絡(luò)故障、傳輸錯(cuò)誤、程序崩潰、停電…），如何設(shè)計(jì)命令的存儲(chǔ)、發(fā)送、接收的流程，以保證命令的：
1) 傳輸中的有序、無(wú)漏、無(wú)重復(fù)性
2) 整個(gè)過(guò)程中命令和數(shù)據(jù)的正確性
3) 多個(gè)同一類型的接收者（例如r1與r2）的狀態(tài)可以在有限時(shí)間內(nèi)趨于一致
最后，請(qǐng)針對(duì)你考慮到的意外情況，說(shuō)明所采用的避免、解決或恢復(fù)方案。
三個(gè)警察和三個(gè)囚徒的過(guò)河問(wèn)題
三個(gè)警察和三個(gè)囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次只能載2人。存在如下的危險(xiǎn)：無(wú)論在河的哪邊，當(dāng)囚徒人數(shù)多于警察的人數(shù)時(shí)，將有警察被囚徒殺死。
問(wèn)題：請(qǐng)問(wèn)如何確定渡河方案，才能保證6人安全無(wú)損的過(guò)河。
回答：
警察囚徒過(guò)去，警察回來(lái)
囚徒囚徒過(guò)去，囚徒回來(lái)
警察警察過(guò)去，警察囚徒回來(lái)
警察警察過(guò)去，囚徒回來(lái)
囚徒囚徒過(guò)去，囚徒回來(lái)
囚徒囚徒過(guò)去
1、給你一組離散的點(diǎn)集合S和一個(gè)坐標(biāo)P，在S中找到一個(gè)點(diǎn)使其到給定點(diǎn)P的距離最短；（要求：不能求兩個(gè)點(diǎn)之間的距離）
2、任意給定平面上n個(gè)點(diǎn)的坐標(biāo)，要求你確定一個(gè)圓，將這個(gè)n個(gè)點(diǎn)平均分為兩部分，其中一部分在圓的內(nèi)部，另外一部分在圓的外部，這個(gè)圓不一定是唯一，只要輸出其中一個(gè)圓的圓心和坐標(biāo)就可以了。（要求：不能求兩個(gè)點(diǎn)之間的距離）
為某圖書(shū)館開(kāi)發(fā)在線瀏覽系統(tǒng)，使用戶可以通過(guò)自定義的圖書(shū)別名瀏覽相關(guān)聯(lián)的圖書(shū)
內(nèi)容。假設(shè)該圖書(shū)館有1000萬(wàn)注冊(cè)用戶，館藏圖書(shū)1000萬(wàn)部。在線瀏覽系統(tǒng)允許用戶自
定義分類名稱，每個(gè)分類可以包含若干部書(shū)籍。用戶可以添加、刪除分類，修改分類的
名稱（同一用戶不允許有名稱相同的分類），可以在分類下添加、刪除書(shū)籍，修改書(shū)籍
的別名（同一分類下不允許有名稱相同的別名）?，F(xiàn)在設(shè)定每個(gè)用戶最多可以自定義10
0個(gè)分類，每個(gè)分類最多可以包含100部書(shū)籍。
A、假定用數(shù)據(jù)庫(kù)解決存儲(chǔ)問(wèn)題，請(qǐng)?jiān)O(shè)計(jì)相關(guān)的數(shù)據(jù)表結(jié)構(gòu)，并給出設(shè)計(jì)考慮。
B、請(qǐng)給出下列操作的SQL語(yǔ)句
展示用戶A的所有分類
展示用戶A所設(shè)置的分類F下的所有書(shū)籍信息
C、請(qǐng)根據(jù)題目A的結(jié)果，嘗試分析一下當(dāng)用戶數(shù)目增長(zhǎng)到1億，館藏圖書(shū)達(dá)到10億冊(cè)，每
天訪問(wèn)用戶達(dá)到500萬(wàn)，平均每人有10次操作時(shí)，系統(tǒng)應(yīng)當(dāng)做哪些改進(jìn)或優(yōu)化。
2011-1-9 20:42
滿意回答
該圖書(shū)館有1000萬(wàn)注冊(cè)用戶，館藏圖書(shū)1000萬(wàn)部。在線瀏覽系統(tǒng)允許用戶自
定義分類名稱，每個(gè)分類可以包含若干部書(shū)籍。如書(shū)架名、書(shū)名號(hào)接下去為代碼加上自己的代號(hào)就行。
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
