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