## 系統設計 **1、搜索關鍵詞智能提示suggestion** 百度搜索框中，輸入“北京”，搜索框下面會以北京為前綴，展示“北京愛情故事”、“北京公交”、“北京醫院”等等搜索詞，輸入“[結構之](http://www.baidu.com/s?wd=結構之&ie=utf-8)”，會提示“結構之法”，“結構之法 算法之道”等搜索詞。 請問，如何設計此系統，使得空間和時間復雜度盡量低。  提示：此題比較開放，簡單直接的方法是：用trie樹存儲大量字符串，當前綴固定時，存儲相對來說比較熱的后綴。然后用hashmap+堆，統計出如10個近似的熱詞，也就是說，只存與關鍵詞近似的比如10個熱詞，我們把這個統計熱詞的方法稱為TOP K算法。 當然，在實際中，還有很多細節需要考慮，有興趣的讀者可以繼續參閱相關資料。 **2** 某服務器流量統計器，每天有1000億的訪問記錄數據，包括時間、URL、IP。設計系統實現記錄數據的保存、管理、查詢。要求能實現以下功能： - 計算在某一時間段（精確到分）時間內的，某URL的所有訪問量。 - 計算在某一時間段（精確到分）時間內的，某IP的所有訪問量。 **3** 假設某個網站每天有超過10億次的頁面訪問量，出于安全考慮，網站會記錄訪問客戶端訪問的IP地址和對應的時間，如果現在已經記錄了1000億條數據，想統計一個指定時間段內的區域IP地址訪問量，那么這些數據應該按照何種方式來組織，才能盡快滿足上面的統計需求呢？ 設計完方案后，并指出該方案的優缺點，比如在什么情況下，可能會非常慢？
提示：用B+樹來組織，非葉子節點存儲（某個時間點，頁面訪問量），葉子節點是訪問的IP地址。這個方案的優點是查詢某個時間段內的IP訪問量很快，但是要統計某個IP的訪問次數或是上次訪問時間就不得不遍歷整個樹的葉子節點。或者可以建立二級索引，分別是時間和地點來建立索引。 **4** 給你10臺機器，每個機器2個CPU和2GB內存，現在已知在10億條記錄的數據庫里執行一次查詢需要5秒，問用什么方法能讓90%的查詢能在100毫秒以內返回結果。 提示：將10億條記錄排序，然后分到10個機器中，分的時候是一個記錄一個記錄的輪流分，確保每個機器記錄大小分布差不多，每一次查詢時，同時提交給10臺機器，同時查詢，因為記錄已排序，可以采用二分法查詢。 如果無排序，只能順序查詢，那就要看記錄本身的概率分布，否則不可能實現。畢竟一個機器2個CPU未必能起到作用，要看這兩個CPU能否并行存取內存，取決于系統架構。 **5** 有1000萬條URL，每條URL長度為50字節，只包含主機前綴，要求實現URL提示系統，并滿足以下條件： - 實時更新匹配用戶輸入的地址，每輸出一個字符，輸出最新匹配URL - 每次只匹配主機前綴，例如對www.abaidu.com和www.baidu.com，用戶輸入www.b時只提示www.baidu.com - 每次提供10條匹配的URL **6** 例如手機朋友網有n個服務器，為了方便用戶的訪問會在服務器上緩存數據，因此用戶每次訪問的時候最好能保持同一臺服務器。 已有的做法是根據ServerIPIndex[QQNUM%n]得到請求的服務器，這種方法很方便將用戶分到不同的服務器上去。但是如果一臺服務器死掉了，那么n就變為了n-1，那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%(n-1)]基本上都不一樣了，所以大多數用戶的請求都會轉到其他服務器，這樣會發生大量訪問錯誤。 問： 如何改進或者換一種方法，使得： - 一臺服務器死掉后，不會造成大面積的訪問錯誤， - 原有的訪問基本還是停留在同一臺服務器上； - 盡量考慮負載均衡。 提示：一致性hash算法。 **7** 對于給定的整數集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都屬于S。集合的元素個數小于等于2000個，元素的取值范圍在[-2^28，2^28 - 1]，假定可用內存空間為100MB，硬盤使用空間無限大，試分析時間和空間復雜度，找出最快的解決方法。 有一大批數據，百萬級別的。數據項內容是：用戶ID、科目ABC各自的成績。其中用戶ID為0~1000萬之間，且是連續的，可以唯一標識一條記錄。科目ABC成績均在0~100之間。有兩塊磁盤，空間大小均為512MB，內存空間64MB。 - 為實現快速查詢某用戶ID對應的各科成績，問磁盤文件及內存該如何組織； - 改變題目條件，ID為0~10億之間，且不連續。問磁盤文件及內存該如何組織； - 在問題2的基礎上，增加一個需求。在查詢各科成績的同時，獲取該用戶的排名，問磁盤文件及內存該如何組織。 **8** 有幾百億的整數，分布的存儲到幾百臺通過網絡連接的計算機上，你能否開發出一個算法和系統，找出這幾百億數據的中值？就是在一組排序好的數據中居于中間的數。顯然，一臺機器是裝不下所有的數據。也盡量少用網絡帶寬。 **9** 類似做一個手機鍵盤，上面有1到9個數字，每個數字都代表幾個字母（比如1代表abc三個字母，z代表wxyz等等），現在要求設計當輸入某幾個數字的組合時，查找出通訊錄中的人名及電話號碼。 **10** 這是一種用戶登錄驗證手段，例如銀行登錄系統，這個設備顯示6位數字，每60秒變一次，再經過服務器認證，通過則允許登錄。問How to design this system？ - 系統設計思路？服務器端為何能有效認證動態密碼的正確性？ - 如果是千萬量級永固，給出系統設計圖示或說明，要求子功能模塊劃分清晰，給出關鍵的數據結構或數據庫表結構。 考慮用戶量級的影響和擴展性，用戶密碼的隨機性等，如果設計系統以支持這幾個因素. - 系統算法升級時，服務器端和設備端可能都要有所修改，如何設計系統，能夠使得升級過程（包括可能的設備替換或重設）盡量平滑？ **11** http服務器會在用戶訪問某一個文件的時候，記錄下該文件被訪問的日志，網站管理員都會去統計每天每文件被訪問的次數。寫一個小程序，來遍歷整個日志 文件，計算出每個文件被訪問的訪問次數。 - 請問這個管理員設計這個算法 - 該網站管理員后來加入騰訊從事運維工作，在騰訊，單臺http服務器不夠用的，同樣的內容，會分布在全國各地上百臺服務器上。每臺服務器上的日志數量， 都是之前的10倍之多，每天服務器的性能更好，之前他用的是單核cpu，現在用的是8核的，管理員發現在這種的海量的分布式服務器，基本沒法使用了，請重新設計一個算法。 **12** 一在線推送服務，同時為10萬個用戶提供服務，對于每個用戶服務從10萬首歌的曲庫中為他們隨機選擇一首，同一用戶不能推送重復的，設計方案，內存盡可能小，寫出數據結構與算法。 **13** 每個城市的IP段是固定的，新來一個IP，找出它是哪個城市的，設計一個后臺系統。 **14** 請設計一個排隊系統，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出；當有人退出影響到用戶的位置排名時需要及時反饋到用戶。 **15** 設計相應的數據結構和算法，盡量高效的統計一片英文文章（總單詞數目）里出現的所有英文單詞，按照在文章中首次出現的順序打印輸出該單詞和它的出現次數。 **16** 有幾百億的整數，分布的存儲到幾百臺通過網絡連接的計算機上，你能否開發出一個算法和系統，找出這幾百億數據的中值？就是在一組排序好的數據中居于中間的數。顯然，一臺機器是裝不下所有的數據。也盡量少用網絡帶寬。 **17** 假設已有10萬個敏感詞，現給你50個單詞，查詢這50個單詞中是否有敏感詞。 分析：換句話說，題目要你判斷這50個單詞是否存在那10萬個敏感詞庫里，明顯是字符串匹配，由于是判斷多個單詞不是一個，故是多模式字符串匹配問題，既是多模式字符串匹配問題，那么便有一類稱之為多模式字符串匹配算法，而這類算法無非是KMP、hash、trie、AC自動機、wm等等。 那到底用哪種算法呢？這得根據題目的應用場景而定。 10萬 + 50，如果允許誤差的話，你可能會考慮用布隆過濾器；否則，只查一次的話，可能hash最快，但hash消耗空間大，故若考慮tire的話，可以針對這10萬個敏感詞建立trie樹，然后對那50個單詞搜索這棵10萬敏感詞構建的tire樹，但用tire樹同樣耗費空間，有什么更好的辦法呢？Double Array Trie么？請讀者繼續思考。