面試題之趣味邏輯題

　　1.給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url?

　　方案1：可以估計(jì)每個(gè)文件安的大小為5G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理?？紤]采取分而治之的方法。

　　遍歷文件a，對(duì)每個(gè)url求取hash(url)%1000，然后根據(jù)所取得的值將url分別存儲(chǔ)到1000個(gè)小文件(記為a0,a1,…,a999)中。這樣每個(gè)小文件的大約為300M。

　　遍歷文件b，采取和a相同的方式將url分別存儲(chǔ)到1000小文件(記為b0,b1,…,b999)。這樣處理后，所有可能相同的url都在對(duì)應(yīng)的小文件(a0vsb0,a1vsb1,…,a999vsb999)中，不對(duì)應(yīng)的小文件不可能有相同的url。然后我們只要求出1000對(duì)小文件中相同的url即可。

　　求每對(duì)小文件中相同的url時(shí)，可以把其中一個(gè)小文件的url存儲(chǔ)到hash_set中。然后遍歷另一個(gè)小文件的每個(gè)url，看其是否在剛才構(gòu)建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

　　方案2：如果允許有一定的錯(cuò)誤率，可以使用Bloomfilter，4G內(nèi)存大概可以表示340億bit。將其中一個(gè)文件中的url使用Bloomfilter映射為這340億bit，然后挨個(gè)讀取另外一個(gè)文件的url，檢查是否與Bloomfilter，如果是，那么該url應(yīng)該是共同的url(注意會(huì)有一定的錯(cuò)誤率)。

　　Bloomfilter日后會(huì)在本BLOG內(nèi)詳細(xì)闡述。補(bǔ)充：另外一種思路，是將url通過算法轉(zhuǎn)為數(shù)字類型，轉(zhuǎn)換后的連接就是比較數(shù)值是否相等了。

　　2.有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M，要求返回頻數(shù)最高的100個(gè)詞。

　　Step1：順序讀文件中，對(duì)于每個(gè)詞x，取hash(x)%5000，然后按照該值存到5000個(gè)小文件(記為f0,f1,...,f4999)中，這樣每個(gè)文件大概是200k左右，如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M;

　　Step2：對(duì)每個(gè)小文件，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率(可以采用trie樹/hash_map等)，并取出出現(xiàn)頻率最大的100個(gè)詞(可以用含100個(gè)結(jié)點(diǎn)的最小堆)，并把100詞及相應(yīng)的頻率存入文件，這樣又得到了5000個(gè)文件;

　　Step3：把這5000個(gè)文件進(jìn)行歸并(類似與歸并排序);

　　草圖如下(分割大問題，求解小問題，歸并)：

　　3.現(xiàn)有海量日志數(shù)據(jù)保存在一個(gè)超級(jí)大的文件中，該文件無(wú)法直接讀入內(nèi)存，要求從中提取某天出訪問百度次數(shù)最多的那個(gè)IP。

　　Step1：從這一天的日志數(shù)據(jù)中把訪問百度的IP取出來(lái)，逐個(gè)寫入到一個(gè)大文件中;

　　Step2：注意到IP是32位的，最多有2^32個(gè)IP。同樣可以采用映射的方法，比如模1000，把整個(gè)大文件映射為1000個(gè)小文件;

　　Step3：找出每個(gè)小文中出現(xiàn)頻率最大的IP(可以采用hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個(gè))及相應(yīng)的頻率;

　　Step4：在這1000個(gè)最大的IP中，找出那個(gè)頻率最大的IP，即為所求。

　　4.LVS和HAProxy相比，它的缺點(diǎn)是什么?

　　之前，的確是用LVS進(jìn)行過MySQL集群的負(fù)載均衡，對(duì)HAProxy也有過了解，但是將這兩者放在眼前進(jìn)行比較，還真沒試著了解過。面試中出現(xiàn)了這么一題，面試官給予的答案是LVS的配置相當(dāng)繁瑣，后來(lái)查找了相關(guān)資料，對(duì)這兩種負(fù)載均衡方案有了更進(jìn)一步的了解。LVS的負(fù)載均衡性能之強(qiáng)悍已經(jīng)達(dá)到硬件負(fù)載均衡的F5的百分之60了，而HAproxy的負(fù)載均衡和Nginx負(fù)載均衡，均為硬件負(fù)載均衡的百分之十左右。由此可見，配置復(fù)雜，相應(yīng)的效果也是顯而易見的。在查找資料的過程中，試著將LVS的10種調(diào)度算法了解了一下，看似數(shù)量挺多的10種算法其實(shí)在不同的算法之間，有些只是有著一些細(xì)微的差別。在這10種調(diào)度算法中，靜態(tài)調(diào)度算法有四種，動(dòng)態(tài)調(diào)度算法有6種。

　　靜態(tài)調(diào)度算法：

　?、賀R輪詢調(diào)度算法

　　這種調(diào)度算法不考慮服務(wù)器的狀態(tài)，所以是無(wú)狀態(tài)的，同時(shí)也不考慮每個(gè)服務(wù)器的性能，比如我有1-N臺(tái)服務(wù)器，來(lái)N個(gè)請(qǐng)求了，第一個(gè)請(qǐng)求給第一臺(tái)，第二個(gè)請(qǐng)求給第二臺(tái)，，，第N個(gè)請(qǐng)求給第N臺(tái)服務(wù)器，就醬紫。

　?、诩訖?quán)輪詢

　　這種調(diào)度算法是考慮到服務(wù)器的性能的，你可以根據(jù)不同服務(wù)器的性能，加上權(quán)重進(jìn)行分配相應(yīng)的請(qǐng)求。

　?、刍谀康牡刂返膆ash散列

　　這種調(diào)度算法和基于源地址的hash散列異曲同工，都是為了維持一個(gè)session，基于目的地址的hash散列，將記住同一請(qǐng)求的目的地址，將這類請(qǐng)求發(fā)往同一臺(tái)目的服務(wù)器。簡(jiǎn)而言之，就是發(fā)往這個(gè)目的地址的請(qǐng)求都發(fā)往同一臺(tái)服務(wù)器。而基于源地址的hash散列，就是來(lái)自同一源地址的請(qǐng)求都發(fā)往同一臺(tái)服務(wù)器。

　?、芑谠吹刂返膆ash散列

　　上述已講，不再贅述。

　　動(dòng)態(tài)調(diào)度

　　①最少連接調(diào)度算法

　　這種調(diào)度算法會(huì)記錄響應(yīng)請(qǐng)求的服務(wù)器上所建立的連接數(shù)，每接收到一個(gè)請(qǐng)求會(huì)相應(yīng)的將該服務(wù)器的所建立連接數(shù)加1，同時(shí)將新來(lái)的請(qǐng)求分配到當(dāng)前連接數(shù)最少的那臺(tái)機(jī)器上。

　?、诩訖?quán)最少連接調(diào)度算法

　　這種調(diào)度算法在最少連接調(diào)度算法的基礎(chǔ)上考慮到服務(wù)器的性能。當(dāng)然，做這樣子的考慮是有其合理性存在的，如果是同一規(guī)格的服務(wù)器，那么建立的連接數(shù)越多，必然越增加其負(fù)載，那么僅僅根據(jù)最少連接數(shù)的調(diào)度算法，必然可以實(shí)現(xiàn)合理的負(fù)載均衡。但如果，服務(wù)器的性能不一樣呢?比如我有一臺(tái)服務(wù)器，最多只能處理10個(gè)連接，現(xiàn)在建立了3個(gè)，還有一臺(tái)服務(wù)器最多能處理1000條連接，現(xiàn)在建立了5個(gè)，如果單純地按照上述的最少連接調(diào)度算法，妥妥的前者嘛，但前者已經(jīng)建立了百分之三十的連接了，而后者連百分之一的連接還沒有建立，試問，這合理嗎?顯然不合理。所以加上權(quán)重，才算合理。相應(yīng)的公式也相當(dāng)簡(jiǎn)單：active*256/weight。

　?、圩疃唐谕{(diào)度算法

　　這種算法，是避免出現(xiàn)上述加權(quán)最少連接調(diào)度算法中的一種特殊情況，導(dǎo)致即使加上權(quán)重，調(diào)度器也無(wú)差別對(duì)待了，舉個(gè)栗子：

　　假設(shè)有三臺(tái)服務(wù)器ABC，其當(dāng)前所建立的連接數(shù)相應(yīng)地為1,2,3，而權(quán)重也是1,2,3。那么如果按照加權(quán)最少連接調(diào)度算法的話，算出來(lái)是這樣子的：

　　A:1256/1=256

　　B:2256/2=256

　　C:3256/3=256

　　我們會(huì)發(fā)現(xiàn)，即便加上權(quán)重，A、B、C，經(jīng)過計(jì)算還是一樣的，這樣子調(diào)度器會(huì)無(wú)差別的在A、B、C中任選一臺(tái)，將請(qǐng)求發(fā)過去。

　　而最短期望將active256/weight的算法改進(jìn)為(active+1)256/weight

　　那么還是之前的例子：

　　A:(1+1)256/1=2/1256=2256

　　B:(2+1)256/2=3/2256=1.5256

　　C:(3+1)256、3=4/3256≈1.3256

　　顯然C

　?、苡啦慌抨?duì)算法

　　將請(qǐng)求發(fā)給當(dāng)前連接數(shù)為0的服務(wù)器上。

　　⑤基于局部的最少連接調(diào)度算法

　　這種調(diào)度算法應(yīng)用于Cache系統(tǒng)，維持一個(gè)請(qǐng)求到一臺(tái)服務(wù)器的映射，其實(shí)我們仔細(xì)想想哈，之前做的一系列最少連接相關(guān)的調(diào)度算法?？紤]到的是服務(wù)器的狀態(tài)與性能，但是一次請(qǐng)求并不是單向的，就像有一個(gè)從未合作過的大牛，他很閑，你讓他去解決一個(gè)之前碰到過的一個(gè)問題，未必有找一個(gè)之前已經(jīng)跟你合作過哪怕現(xiàn)在不怎么閑的臭皮匠效果好哦~，所以基于局部的最少連接調(diào)度算法，維持的這種映射的作用是，如果來(lái)了一個(gè)請(qǐng)求，相對(duì)應(yīng)的映射的那臺(tái)服務(wù)器，沒有超載，ok交給老伙伴完事吧，俺放心，如果那臺(tái)服務(wù)器不存在，或者是超載的狀態(tài)且有其他服務(wù)器工作在一半的負(fù)載狀態(tài)，則按最少連接調(diào)度算法在集群其余的服務(wù)器中找一臺(tái)將請(qǐng)求分配給它。

　?、藁趶?fù)制的局部最少連接調(diào)度算法

　　這種調(diào)度算法同樣應(yīng)用于cache系統(tǒng)，但它維持的不是到一臺(tái)服務(wù)器的映射而是到一組服務(wù)器的映射，當(dāng)有新的請(qǐng)求到來(lái)，根據(jù)最小連接原則，從該映射的服務(wù)器組中選擇一臺(tái)服務(wù)器，如果它沒有超載則交給它去處理這個(gè)請(qǐng)求，如果發(fā)現(xiàn)它超載，則從服務(wù)器組外的集群中，按最少連接原則拉一臺(tái)機(jī)器加入服務(wù)器組，并且在服務(wù)器組有一段時(shí)間未修改后，將最忙的那臺(tái)服務(wù)器從服務(wù)器組中剔除。

　　5.有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。

　　方案：順序讀文件中，對(duì)于每個(gè)詞x，取hash(x)%5000，然后按照該值存到5000個(gè)小文件(記為x0,x1,…x4999)中。這樣每個(gè)文件大概是200k左右。

　　如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。

　　對(duì)每個(gè)小文件，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率(可以采用trie樹/hash_map等)，并取出出現(xiàn)頻率最大的100個(gè)詞(可以用含100個(gè)結(jié)點(diǎn)的最小堆)，并把100個(gè)詞及相應(yīng)的頻率存入文件，這樣又得到了5000個(gè)文件。下一步就是把這5000個(gè)文件進(jìn)行歸并(類似與歸并排序)的過程了。

　　6.有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行存放的都是用戶的query，每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序。

　　還是典型的TOPK算法，解決方案如下：

　　方案1：

　　順序讀取10個(gè)文件，按照hash(query)%10的結(jié)果將query寫入到另外10個(gè)文件(記為)中。這樣新生成的文件每個(gè)的大小大約也1G(假設(shè)hash函數(shù)是隨機(jī)的)。

　　找一臺(tái)內(nèi)存在2G左右的機(jī)器，依次對(duì)用hash_map(query,query_count)來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對(duì)應(yīng)的query_cout輸出到文件中。這樣得到了10個(gè)排好序的文件(記為)。

　　對(duì)這10個(gè)文件進(jìn)行歸并排序(內(nèi)排序與外排序相結(jié)合)。

　　方案2：

　　一般query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對(duì)于所有的query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用trie樹/hash_map等直接來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。

　　方案3：

　　與方案1類似，但在做完hash，分成多個(gè)文件后，可以交給多個(gè)文件來(lái)處理，采用分布式的架構(gòu)來(lái)處理(比如MapReduce)，最后再進(jìn)行合并。

　　7.騰訊面試題：給40億個(gè)不重復(fù)的unsignedint的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中?

　　第一反應(yīng)時(shí)快速排序+二分查找。以下是其它更好的方法：

　　方案1：oo，申請(qǐng)512M的內(nèi)存，一個(gè)bit位代表一個(gè)unsignedint值。讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

　　方案2：這個(gè)問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路

作者：傳智播客大數(shù)據(jù)培訓(xùn)學(xué)院
首發(fā)：http://cloud.itcast.cn