左神算法——大数据题目
大数据
常见数据
- 2的32次方差不多是42亿
- int类型的范围是 2的32次方 -1
技巧罗列
- 哈希函数分流思想是万能的
- 这类题严格意义上讲的内存限制题目，并且只有以上几种套路，是面试过程中最好准备的
例题
问题1
32位无符号整数的范围是0~4,294,967.295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数?
【进阶】
内存限制为 10MB，但是只用找到一个没出现过的数即可
空间充足
哈希表一个一个存储
空间紧凑
利用int类型来作为byte数组，校验范围内每一个数是否出现，并且由于是索引判断，更新速度很快，最后只需要遍历一次byte数组即可
空间非常紧凑
在给定的范围内求最大可以分成多长的int数组，得出的结果向下取一个最近的2的整数次幂，指数的大小就是数组的大小。然后用该数组对给定的数进行分割，可以使用 / 操作，获取对应的索引并将该位置上的值++，最后有不满足最大值的就是缺了，然后对于确定是缺少数组的范围再次进行上述操作，不同的是这次不在这个范围内的数不放进去，同时对这个范围的数 进行 / 操作求得索引，周而复始，最后一定能定位到没有出现的数字
最最极端
只能申请有限变量
对int的范围进行一个二分操作，校验范围内落在两边数据的数量，那边不够就是落在那边，依次二分。
总结
最后两个最多需要跑32次整体数据
问题2
某搜索引擎公司一天有上百亿条数据，求出100Top的热词
解法
哈希函数分流，对每一个文件区间内通过哈希表的形式进行计算，求得当前文件内的100Top，最后做一个整合。
由于哈希函的性质，对于key值一样的来说，只会得到同样的哈希值，相同的url词汇只会出现在一个区间内
如上图所示，是该题目的具体过程，每次从总大根堆中弹出堆顶元素，然后将该元素对应的小文件的大根堆堆顶进行弹出，并将新的堆顶元素加入的总堆中去
同时因为堆的结构，相应的调整代价很低
这种堆上套堆的结构被称为二维堆。
问题3
32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。
【补充】
可以使用最多10MB的内存，怎么找到这40亿个整数的中位数?
解法
- 哈希表分流
- 位图表示，使用两位来表示一个数的出现次数，正好一个G可以用完
- 分段统计，见问题1的第三种空间限制解法，稍微改变策略，最后对词频进行求和操作，根据数据总量来找到中位数出现的范围，然后依次进行之前的操作
问题4
对海量的数据进行词频排序操作 –据说是腾讯二面原题
解法1
主要应用的是问题1中第三种情况，将给定的空间按照 最小操作数 的大小进行划分，不同于问题1的第三种情况，这里不再不需要分段统计，因为题目要求的是升序词频输出，具体思路流程见下图解析
还需要强调的是 2的27次方-1这个操作，实际上还是为了和2的31次方-1这种有符合int最大值做一个匹配
每一次出区间划分都将内容按照小的去全检挑选出来
解法2
