九月十月百度，迅雷，華為，阿里巴巴，最新校招筆試面試五十題(4)

　　蜻蜓FM2014校招研發筆試

　　10月11日，騰訊web前端面試

　　一個數組 var arr = ['abc','ddadbc','adbdcd','abcqew'.......] 長度一萬， 用最有效率的方法計算出包含被元素出現最多的。

　　單機5G內存，磁盤200T的數據，分別為字符串，然后給定一個字符串，判斷這200T數據里面有沒有這個字符串，怎么做?

　　如果查詢次數會非常的多, 怎么預處理?

　　點評：如果數據是200g且允許少許誤差的話，可以考慮用布隆過濾器Bloom Filter：http://blog.csdn.net/v_july_v/article/details/6685894。但本題是200T，得另尋良策。

　　OK，以下是@cy 提供的題解(暴露出的一個問題是題意不是特別明確，因為題解中有不少自己的假設，所以日后各位面試時一定要跟面試官徹底弄清題意再作答，包括各種使用條件)：

　　“①. 內存和數據比是 5GB / 200TB, 約為 1 比 4w, 所以trie啥的就不用想了, 唯一的就是hash.

　?、? 簡單的假設每個字符串是相對短的(只要不會超過5GB)

　　1. 幾MB, 甚至百MB的字符串也能處理, 但是確實對最終的效果有很大影響, 如果只是部分case特別大,可以特殊處理下.

　?、? 一個字符串塊 在內存中需要一個 條目 來標識

　　1. value 需要 8 字節, key約為4字節

　　1. 200TB總共有 200 * 2^40 位, 地址空間至少為48個bit, 存儲長度用16bit則一個條目的value 需要8個字節

　　1. 這里的長度是用來存一個 字符串塊 的長度, 單位可以優化為KB, 甚至MB, 16bit肯定是夠的

　　1. key用4個字節有些緊張, 可以考慮占用部分長度的位

　　1. 長度也可以不在條目中出現, 而是在塊頭出現, 但這樣取塊的時候有可能浪費, 也有可能要取多次.

　　2. 所謂一個 字符串塊 就是hash值相同的字符串挨個存在一起, 從而得到的字符串塊.

　?、? 這樣的話, 5GB 可以存放最多 5GB / 8 約為 4億個條目.

　?、? 把原來的200TB字符串挨個的hash, 并按hash排序后, 存起來, 建立索引.

　　1. hash值可以用md5之類的散列到足夠開, 然后 mod 4億值來求

　?、? 根據重排后的文件, 建立索引, key為hash值, value為前面說到的, 該hash對應字符串塊在文件中的偏移, 和 塊的長度.

　?、卟樵儠r, 根據hash值, 找到該字符串可能在的字符串, 然后將整個字符串讀出來, 用kmp比較即可.

　　200TB的數據, 被劃到 4億 個字符塊當中, 平均一塊應該在 800KB 附近, 考慮到hash不均衡, 一般也就是幾MB的樣子,

　　比較起來應該還OK.

　?、嗥渌男灮c:

　　1. 不是一個文件, 而是若干個文件, 但是不影響偏移的編號

　　1. 為什么做hash再分塊? 避免通用前綴過多,導致分塊極不均勻

　　1. 大長的字符串容易導致 字符串塊 暴大, 可以考慮分為若干小串, 同時記錄原來的位置, 知道是否是一個整串

　　1. 壓縮...留一些空間做常用查詢串的緩存...

　?、嵩僬f怎么優化這個預處理的排序過程. 每次讀5GB的數據進來, 算好hash分好桶, 這種OK吧, 然后按桶回寫到下去, 這里也是批量寫的. 處理完繼續處理下一個5GB, 全部處理完后, 再做歸并, 搞幾輪后, 就OK了嘛. 當然, 為了把內存中排序時浪費的IO補回來, 可以 并行做, 一個在算的時候,另一個在讀....”。

　　10月12日，百度一面

　　JAVA里面的線程同步機制、異常處理機制、集合類、簡單的設計模式、hashmap和hashtable的區別，及HashMap和ConcurrentHashMap的區別。

　　點評：關于hashmap和hashtable的區別，請看上文第13題，其余請自己查閱相關書籍。

　　stat、SDE、PM、DS等相關職位的面試題

　　1、有一組數據，很長，有ID，經緯度，時間4個變量。

　　怎么找出兩人是否有一面之緣。怎么找出所有relationship(定義是在100米范圍內一起度過1小時以上)。

　　2、怎么找出競爭對手購買了哪些搜索關鍵詞。

　　3、怎么判斷兩個TB級別的文本是否雷同，是否近似。

　　4、怎么用C實現SQL的join功能。

　　5、怎么最快的在一個大文本里面搜索字符串。

　　6、coding計算斐波那契數列。

　　更多請參看：http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000300&itemidx=1&sign=173a62e0db86cb4c76a0bb1e9c22f3e5。

　　10月12日，網易游戲專業一面

　　1、怎么判斷單鏈表有沒有環

　　2、怎么判斷兩個無環單鏈表是否相交

　　3、101個硬幣中有一個假幣，有一個無砝碼的天平，稱兩次，判斷假幣比真幣重還是輕。

　　點評：老掉牙的題，沒點評的欲望，原文請看：http://blog.csdn.net/cqsctlsss/article/details/12747631。

　　10月13日，百度筆試題：

　　1、 給出數組A={a_0,a_1,a_2,...,a_n}(n是可變的)，打印出所有元素的組合

　　2、 數組A中任意兩個相鄰元素大小相差1，現給定這樣的數組A和目標整數t，找出t在數組A中的位置。

　　3、 求二叉樹的面積(高乘寬)，高為二叉樹根到葉子節點的最大距離，寬慰二叉樹最多的節點數。

　　4、給了一個百度地圖的截圖，對于地圖上的某一點，需要在地圖上標注該點的信息，將信息抽象成一個矩形，可以在該點的左邊標記，也可以在該點右邊標記。但是任意兩點標記后的矩形是不能有覆蓋的，否則刪除其中一個點

　　問題1，現給一固定區域，有n個點，設計一個算法，要求標記足夠多的點

　　問題2，當點足夠多時候，算法會遇到性能瓶頸，需要對算法重新優化。

　　更多題目請參見：http://blog.csdn.net/xyanghomepage/article/details/12687771。

　　騰訊筆試題兩道

　　1、有100W個關鍵字，長度小于等于50字節。用高效的算法找出top10的熱詞，并對內存的占用不超過1MB。

原文轉自：http://blog.csdn.net/v_july_v/article/details/11921021