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

問答題：

　　一、有一個單向循環鏈表隊列，從頭開始報數，當報到m或者m的倍數的元素出列，根據出列的先后順序重新組成單向循環鏈表。

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

　　二、優酷是中國第一的視頻網站，每天有上億的視頻被觀看，現在公司請研發人員找出最熱門的視頻。

　　該問題的輸入可以簡化為一個字符串文件，每一行都表示一個視頻id，然后要找出出現次數最多的前100個視頻id，將其輸出，同時輸出該視頻的出現次數。

　　1、假設每天的視頻播放次數為3億次，被觀看的視頻數量為一百萬個，每個視頻ID的長度為20個字節，限定使用的內存為1G。請先描述做法，再寫代碼。

　　2、假設每個月的視頻播放次數為100億次，被觀看的視頻數量為1億個，每個視頻ID的長度為20個字節，一臺機器被限定使用的內存為1G。

　　那么想找這個月被播放次數最多的前100個視頻，應該怎么做?請描述清楚可能的辦法。

　　解析：海量數據的處理。無法一次性裝入內存，可先hash之分為多個文件處理，堆或者Trie樹統計次數，求出每個文件中的Top 100。歸并之求出總的top 100。

　　對于第二問：還可以hadoop mapReduce處理之。

　　首先統計每個視頻被觀看次數，得到鍵值對，其中id為視頻id，cnt為視頻被觀看次數。

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

　　對于第一問，由于id個數較少，統計部分可直接使用stl的map容器。

　　對于第二問，由于id個數太大，直接hash內存不夠，需要mapReduce。

　　三、給你一個由n-1個整數組成的未排序的序列，其元素都是1到n中的不同的整數。請寫出一個尋找序列中缺失整數的線性時間算法。