优酷土豆2013校招:填空题——技术研发类（2）

填空题
1、设数组定义为a[60][70]，每个元素占2个存储单元，数组按照列优先存储，元素a[0][0]的地址为1024，那么元素a[32][58]的地址为（8048）

2、在一个娱乐节目上，主持人提供有三扇门（假设为A、B、C），只有1扇门后面有奖品，另两扇门后面是空的，而主持人知道具体哪扇门后有奖品。首先，当 你选择了一扇门之后（假设A），主持人会把剩下两扇门中的一扇没有奖品的门打开（假设打开的空门为B），现在你有一次机会决定是否要交换重新选择，如果你 坚持选择A，你中奖的概率是（1/3），如果你交换选择C，你中奖的概率是（2/3）   

假设你选择的1门，而主持人打开的是3门，则奖品在2门后面的概率是

3、一棵深度为h的满二叉树，其最末一层共有（2^h）个节点（根节点深度为0）

4、下面程序的运行结果为（1   3   2）

  
 
 void foo(int *a , int *b)  
    {  
        *a = *a + *b;  
        *b = *a - *b;  
        *a = *a - *b;  
    }  
      
    void main()  
    {  
        int a = 1 , b = 2 , c = 3;  
        foo(&a , &b);  
        foo(&b , &c);  
        foo(&c , &a);  
        printf("%d %d %d\n",a,b,c);  
    } 

5、4个结点可以构造出（14）个不同的二叉树    Catalan数
6、设有n个无序的记录关键字，则直接插入排序的时间复杂度为（O(n^2)），快速排序的平均时间复杂度为（O(nlgn)）
7、设一组初始记录关键字序列为（20,18,22,16,30,19），则以20为中轴的一趟快速排序结果为（19,18,16,20,30,22）
8、C语言的函数参数传递方式有传递值和传递地址
9、分配在堆上和栈上的内存，哪一个需要手动进行内存释放？   堆上的内存
问答题：
一、有一个单向循环链表队列，从头开始报数，当报到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, cnt>键值对，其中id为视频id，cnt为视频被观看次数。
  以cnt作为关键字建立最小堆。遍历所有键值对，若堆的size小于100，则将键值对直接插入堆，否则比较键值对和堆顶元素大小，若cnt大于堆顶元素的cnt，则弹  出堆顶元素并将键值对插入堆。
 对于第一问，由于id个数较少，统计部分可直接使用stl的map容器。
  对于第二问，由于id个数太大，直接hash内存不够，需要mapReduce。
三、给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性时间算法。