1、給一個超過100G大小的log file，log中存著IP地址，設(shè)計算法找到出現(xiàn)次數(shù)最多的IP地址？（與如何知道top K的IP，如何使用Linux系統(tǒng)命令實現(xiàn)）
Hash分桶法：
將100G文件分成1000份，將每個IP地址映射到相應(yīng)文件中：file_id = hash(ip) % 1000
在每個文件中分別求出最高頻的IP，再合并Hash分桶法；
使用Hash分桶法把數(shù)據(jù)分發(fā)到不同的文件；
各個文件分別統(tǒng)計top K；
2、給定100億個整數(shù)，設(shè)計算法找到只出現(xiàn)一次的整數(shù)。
Hash分桶法，將100億個整數(shù)映射到不同的區(qū)間，在每個區(qū)間中分別找只出現(xiàn)一次的整數(shù)。
3、給兩個文件，分別有100億個整數(shù)，我們只有1G內(nèi)存，如何找到兩個文件交集
掃描每個整數(shù)是否出現(xiàn)過，節(jié)省內(nèi)存方法使用bitmap。
桶分 + bitmap。如果整數(shù)是32bit，直接使用bitmap的方法實現(xiàn)。
所有整數(shù)共232種可能，每個數(shù)用兩位表示，00表示文件均沒出現(xiàn)，10表示文件1出現(xiàn)過，01表示文件2出現(xiàn)過，11表示兩文件均出現(xiàn)過，共需要232*2/8 = 1GB內(nèi)存，遍歷兩個文件中的所有整數(shù)，然后尋找bitmap中11對應(yīng)的整數(shù)即是兩個文件的交集，這樣即可線性時間復(fù)雜度完成。
4、1個文件有100億個int，1G內(nèi)存，設(shè)計算法找大出現(xiàn)次數(shù)超過2次的所有整數(shù)。
Bitmap擴展：用2個bit表示狀態(tài)，0表示未出現(xiàn)，1出現(xiàn)過1次，2出現(xiàn)過2次或以上。
5、給兩個文件，分別有100億個query，我們只有1G內(nèi)存，如何找到兩個文件交集？分別給出精確算法和近似算法？
精確算法：Hash分桶法
將兩個文件中的query hash到N個小文件中，并標明query的來源；
在各個小文件中找到重合的query
將找到的重合query匯總
近似算法：BloomFilter算法
5、說說Zookeeper
Zookeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現(xiàn)這個機制的協(xié)議叫做Zab協(xié)議。Zab協(xié)議有兩種模式，它們分別是恢復(fù)模式（選主）和廣播模式（同步）。當服務(wù)啟動或者在領(lǐng)導(dǎo)者崩潰后，Zab就進入了恢復(fù)模式，當領(lǐng)導(dǎo)者被選舉出來，且大多數(shù)Server完成了和leader的狀態(tài)同步以后，恢復(fù)模式就結(jié)束了。狀態(tài)同步保證了leader和Server具有相同的系統(tǒng)狀態(tài)。
當leader崩潰或者leader失去大多數(shù)的follower，這時候zk進入恢復(fù)模式，恢復(fù)模式需要重新選舉出一個新的leader，讓所有的Server都恢復(fù)到一個正確的狀態(tài)。
ZooKeeper學(xué)習第一期---Zookeeper簡單介紹
6、說說HBase
7、說說ETL
ETL (Extract-Transform-Load的縮寫,即數(shù)據(jù)抽取、轉(zhuǎn)換、裝載的過程)
是將業(yè)務(wù)系統(tǒng)的數(shù)據(jù)經(jīng)過抽取、清洗轉(zhuǎn)換之后加載到數(shù)據(jù)倉庫的過程，目的是將企業(yè)中的分散、零亂、標準不統(tǒng)一的數(shù)據(jù)整合到一起，為企業(yè)的決策提供分析依據(jù)。
