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