經過了三個月的斷斷續續的面試和準備，最近一陣抓了很多時間努力準備， 本以為最后的一次面試能彌補前面的不足，可惜還是功虧一簣... 想想主要是自己編程水平不行，不能快速的寫出bug free code，另外 design和算法方面有差距，另外是前面的準備不足，后面拼命努力最終還是無補 :( 把面試題給大家分享，希望大家都能拿到滿意的offer。

　　1) 一個range的序列（鏈表或數組），如[1,3], [2,6], [8,10]，[15,18] 寫程序合并有重疊的range，比如上面的序列合并為[1,6], [8,10], [15,18] 如果這個序列不是靜態的，而是一個數據流，如何 處理？

　　 后來聽說了interval tree，不過還是不太清楚具體如何解決，有大牛能詳細說說么？

　　2) 利用快速排序的劃分方法，把數組分成三部分，< val, = val, val。

　　后來發現 programming peals 上有原題..

　　3) 對于google查詢的詞組成的動態的數據流，在任意時刻取出10個完全隨機的查詢。

　　當時死活沒答上來，后來在板上發現是經典的 reservior sampling，早點到板上看面經就好了..

　　 4) 把一個字符串轉換成32bit的整數 = 要注意處理溢出的情況

　　5) 在一個數組中尋找三個數，使得它們的和為0

　　這個是找兩個和為0的數的擴展

　　6) 大概是用一位數組來表示二維數組，但是每一行的元素個數可以不同，實現get，set函數

　　這個算是比較簡單的

　　7) 已知每個待查找的字符串長度為10，如何在一個很長的字符串的序列里快速查找這樣的字符串

　　當時的思路是，遍歷字符串把所有長度為10的的字符串算出累加值， 類似于 sum = a0 * 10 + a1 * 10^2 + ... + a9 *10^9，然后用這個sum 做hash，面試官ms覺得還馬馬虎虎。應該有更好的辦法。

　　 8) 寫程序生成邊長為n的如下的方陣 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 = 順時針生成即可，注意邊界條件

　　9) 應用程序的re-order的buffer的設計,如果滿了可以丟棄 大概是應用程序需要in order的數據包，但是收到的數據可能是亂序的（類似于IP分片，每一個數據片有一個序列號，但是不同的數據片 到達應用程序的順序可能和發送的順序不一樣，引起亂序）。然后有 一個buffer，可以存放幾個數據片，問如何設計算法通過這個buffer 把數據片變成有序。說了仿照IP分片重組，設置timer再加上ack來做， 面試官好像不太滿意。

　　10) 假設有很多多邊形，最大的是地球，每一個國家可以認為是一個多邊形，每一個省 ，市，區，小區，樓都可以認為是一個多邊形，這些多邊形之間要么是相互包含的，要么是互相沒有交集的，（不存在overlap的情況）。給出一個多邊形，要求寫程序求出最小的包含它的多邊形。已知有現成的函數可以判斷兩個多邊形是否相互包含， iscontained(poly p1, poly p2)。

　　如何加速？如果在多機的情況下呢？

　　可以用樹結構表示包含的關系。可以用二分搜索做加速。多機的話可以range一個機器處理一個區域，另外要考慮前端處理機的負載不要成為瓶頸，所以讓每個機器自己判斷此多邊形是否包含。