系統設計題(30分)
某流量監控系統每天生成大量的資料記錄，每條記錄 包括url,訪問IP,時間，這些資料記錄需要進行儲存和維護，並提供查詢。請設計一個系統能夠儲存和維護1000億條資料，實現實時監控，並能支援一下兩種查詢：
1.指定任意一個時間段(精確到分鐘)和某個ip,查出該時段內該ip的總訪問量。
2.指定任意一個時間段(精確到分鐘)和某個url,查出該時段內對該url的總訪問量。下面是當時筆試的一些思路，具體細節不太記得了。
1.很多地方都見到這道題，extern “c”是指將該段程式碼以C語言形式進行編譯、連結。由於C不支援函式過載，C與C++對於同一函式進行編譯後在符號表中儲存的函式名存在差異，故當進行C、C++混編時會出現一些問題。
2.記得上學期還特意去借了一本《設計模式》書來看，翻是翻了幾下，結果啥也沒記住，這題直接空了。對於設計模式記得最深的一句就是“過分在意設計模式會阻礙你的創新思維”。
3.前段時間騰訊筆試時有道選擇題也是考TCP的幾個狀態，當時做錯了。回來後看了下TCP的連線和釋放，這次還真用上了。time_wait是TCP釋放四次握手中的一個狀態，當第三次握手完成時，即客戶端收到來自服務器的FIN後，再發送一個ACK,客戶便開始了time_wait狀態。
同時一個記時器開始記時，當達到2倍一個報文段在因特網中最大的.生存期時代表超時。如果在超時前客戶端再次收到FIN，則表示是伺服器重發的FIN,客戶端需重發送ACK。
4.依題目得知是求有向圖的一個拓撲序列。
5.直接掃描一遍。
int count_prefect_sentence(string str) { int i = 0, cnt = 0, hasOneLetter = 0; while(str[i]) { if(str[i] == '.') { if(hasOneLetter) cnt++; hasOneLetter = 0; } else if(isalpha(str[i])) hasOneLetter = 1; i++; } return cnt; }
6.海量資料處理題，當時花了很長時間在想這兩題，感覺沒有想到什麼好的思路。這樣的系統應當是實時性優先吧，在時間空間上首先考慮時間。
a、建個二維對映Map[time]et, time代表某一時間點，將時間點表示為
時間秒差數字作為對映索引。第二維考慮bitset的方式, 建立一個2^32(整型的最大位數)的陣列(bitset),每一個bit位0或1代表該位上代表的IP整數是否訪問過. 統計時列舉每個時間點，再按位和indexIP進行與運算進行統計，時間效率應該不差。以儲存30天為例，空間為(30*24*3600)*(2^32)bit = 2^50B = 1000TB = 1PB
b、時間以分鐘為單位，第二維直接為IP, 對映值為該分鐘訪問量。(30*24*60)*(2^32)B= 2^50B = 1000TB = 1PB
7、對映Map[url][time],將url進行字串hash，再進行列舉統計。
這兩題如果做成兩維對映，記憶體吃不消，既然兩題中的一維是已經指定的，變化的只是時間段，因此可以用一維表示，先預處理，再進行統計。