優(yōu)酷土豆2019校園招聘筆試題和面試題答案(三)

問(wèn)答題：

　　一、有一個(gè)單向循環(huán)鏈表隊(duì)列，從頭開(kāi)始報(bào)數(shù)，當(dāng)報(bào)到m或者m的倍數(shù)的元素出列，根據(jù)出列的先后順序重新組成單向循環(huán)鏈表。

　　函數(shù)原型：void reorder(Node head , int m)

　　二、優(yōu)酷是中國(guó)第一的視頻網(wǎng)站，每天有上億的視頻被觀看，現(xiàn)在公司請(qǐng)研發(fā)人員找出最熱門(mén)的視頻。

　　該問(wèn)題的輸入可以簡(jiǎn)化為一個(gè)字符串文件，每一行都表示一個(gè)視頻id，然后要找出出現(xiàn)次數(shù)最多的前100個(gè)視頻id，將其輸出，同時(shí)輸出該視頻的出現(xiàn)次數(shù)。

　　1、假設(shè)每天的視頻播放次數(shù)為3億次，被觀看的視頻數(shù)量為一百萬(wàn)個(gè)，每個(gè)視頻ID的長(zhǎng)度為20個(gè)字節(jié)，限定使用的內(nèi)存為1G。請(qǐng)先描述做法，再寫(xiě)代碼。

　　2、假設(shè)每個(gè)月的視頻播放次數(shù)為100億次，被觀看的視頻數(shù)量為1億個(gè)，每個(gè)視頻ID的長(zhǎng)度為20個(gè)字節(jié)，一臺(tái)機(jī)器被限定使用的內(nèi)存為1G。

　　那么想找這個(gè)月被播放次數(shù)最多的前100個(gè)視頻，應(yīng)該怎么做?請(qǐng)描述清楚可能的辦法。

　　解析：海量數(shù)據(jù)的處理。無(wú)法一次性裝入內(nèi)存，可先hash之分為多個(gè)文件處理，堆或者Trie樹(shù)統(tǒng)計(jì)次數(shù)，求出每個(gè)文件中的Top 100。歸并之求出總的top 100。

　　對(duì)于第二問(wèn)：還可以hadoop mapReduce處理之。

　　首先統(tǒng)計(jì)每個(gè)視頻被觀看次數(shù)，得到鍵值對(duì)，其中id為視頻id，cnt為視頻被觀看次數(shù)。

　　以cnt作為關(guān)鍵字建立最小堆。遍歷所有鍵值對(duì)，若堆的size小于100，則將鍵值對(duì)直接插入堆，否則比較鍵值對(duì)和堆頂元素大小，若cnt大于堆頂元素的cnt，則彈 出堆頂元素并將鍵值對(duì)插入堆。

　　對(duì)于第一問(wèn)，由于id個(gè)數(shù)較少，統(tǒng)計(jì)部分可直接使用stl的map容器。

　　對(duì)于第二問(wèn)，由于id個(gè)數(shù)太大，直接hash內(nèi)存不夠，需要mapReduce。

　　三、給你一個(gè)由n-1個(gè)整數(shù)組成的未排序的序列，其元素都是1到n中的不同的整數(shù)。請(qǐng)寫(xiě)出一個(gè)尋找序列中缺失整數(shù)的線性時(shí)間算法。