蓄水池抽樣及Google搜索之星分析
今日面試題，蓄水池抽樣，又稱隨機抽樣問題，表示如下：
要求從N個元素中隨機的抽取k個元素，其中N無法確定。
這種應用的場景一般是數據流的情況下，由于數據只能被讀取一次，而且數據量很大，并不能全部保存，因此數據量N是無法在抽樣開始時確定的；但又要保持隨機性，于是有了這個問題。所以搜索網站有時候會問這樣的問題。
這里的核心問題就是“隨機”，怎么才能是隨機的抽取元素呢？我們設想，買彩票的時候，由于所有彩票的中獎概率都是一樣的，所以我們才是“隨機的”買彩票。那么要使抽取數據也隨機，必須使每一個數據被抽樣出來的概率都一樣。
Google 搜索之星分析
題目：
給你一天的Google搜索日志，你怎么設計算法找出是否有一個搜索詞，它出現的頻率占所有搜索的一半以上？如果肯定有一個搜索詞占大多數，你能怎么提高你的算法找到它？再假定搜索日志就是內存中的一個數組，能否有O(1)空間，O(n)時間的算法？
分析：
首先要看清題目，說的是“一半以上”，“大多數”，"majority"，也就是大于５０％。
很多情形下，尤其在面試比較緊張的情形下，經常會下意識的很快得出一個如下的方法（這個沒有錯，能有解決方案勝于完全沒想法）。定義一個哈希表，里面存放數組里面的每個元素以及出現的次數。可以通過兩個過程來做。
第一步是映射，將每個元素放進去，存在加一，不存在置一。同時統計元素個數。
第二步是遍歷整個哈希表，判斷是否找到出現次數大于數組長度一半的。如果有，找到。否則沒有。
顯然，這個要求O(n)的空間在存儲哈希表，并不理想。
另外的下意識的方法， 比如說，先將元素排序，然后再進行判斷。因為如果有大多數的話，取數組中間點的那個元素即為所要找的那個。不過這種方法首先排序就需要O(NlogN)的時間復雜度，并不是很理想。
題中說到肯定有一個搜索詞是大多數，這個條件可能蘊藏著提高的空間。
面試時，我們會經常寫下一個例子，手工做些運算，也許能找到好的方案。
比如，1，2，2，3，2，2，3 顯然2是多數元素 去除1，2，在2，3，2，2，3 中2仍是多數元素 去除1，3，在2，3，2，2，3 中2更是多數元素
再比如，1，3，2，3，2，2，3 顯然沒有多數元素 去除1，3，在2，3，2，2，3 中2成了多數
觀察結論：在原序列中去除兩個不同的元素后，那么在原序列中的多數元素在新序列中還是多數元素。但新序列中的多數元素在原序列不一定是多數，所以需要驗證。但原題說是肯定有多數，所以我們可以忽略驗證。
基于這個觀察，假設我們一開始從數組的開頭，碰到某個元素的時候，就設置該元素為當前元素。當前出現的次數為1，后面，如果接著碰到的元素和該元素 相同，則當前次數加1，否則減1。如果當前出現的次數為0，則表示當前元素不確定。如果結合我們有大多數元素這個前提的話，必然最后的結果是大于0的，而 且最終獲取到的值就是大多數元素。
對于這個大多數算法（Majority Algorithm）, 國外有教授有研究并發表論文：《MJRTY - A Fast Majority Vote Algorithm》
