优酷土豆2018校园招聘笔试题和面试题答案(三)

问答题：

　　一、有一个单向循环链表队列，从头开始报数，当报到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中的不同的整数。请写出一个寻找序列中缺失整数的线性时间算法。