公司个人怎么制作网站,手机网站焦点图,中国化工建设协会网站,外包网络安全管理白银挑战-海量数据场景下的热门算法题
1.从40亿中产生一个不存在的整数
题目要求#xff1a; 给定一个输入文件#xff0c;包含40亿个非负整数#xff0c;请设计一个算法#xff0c;产生一个不存在该文件中的整数#xff0c;假设你有1GB的内存来完成这项任务。
进阶拓展…白银挑战-海量数据场景下的热门算法题
1.从40亿中产生一个不存在的整数
题目要求 给定一个输入文件包含40亿个非负整数请设计一个算法产生一个不存在该文件中的整数假设你有1GB的内存来完成这项任务。
进阶拓展如果只有10MB的内存可用该怎么办
1.1 位图存储大数据的原理
假设用哈希表来保存出现过的数如果40亿个数都不同则哈希表的记录路为 40亿 条。 占用空间统计1个32位整数占用 4B40亿个占用 40* 100 000 000 *4B ≈ 16 GB
如果用位方式俗称位图统计40亿/8 B 5* 100 1000 1000 ≈ 0.5 GB
占用大小 0.5 GB , 对应的bit数组的长度 0.5*1024*1024*1024*8 4 294 967 295 (42亿)
具体实现 创建一个4 294 967 295长度的bit数组 bitArr 遍历40亿个无符号数组把bitArr对应位置的值设置为1如遇到1000bitArr[1000] 1 遍历完成之后bitArr数组中不为1的位置索引就是没有出现的数
位图存储核心存储的并不是这40亿个数据本身而是其对应的位置
1.2 使用10MB来存储
只有10MB内存位图也不能搞定了需要另寻他法。这里我们可以使用分块思想时间换空间通过两次遍历来搞定。
确定需要划分块的个数 40亿个数 需要500MB的空间如果只有10MB的空间至少需要50个块。一般划分都是使用2的整数倍这里划分成64个块比较合理
将2^32(42亿)划分成 64(2^6) 个块每个块是 232/26 2^26 67 108 864 个数如
第0区间0 ~ 2^26 - 1第1区间2^26 ~ 2^27 - 1第i区间(i)*2^26 ~ (i1)2^26 - 1… …第63区间(26-1)*226 ~ 2^32 - 1
一共有 40 亿个数统计落在每一个区间上的数有多少至少有一个区间上的数少于 2^26 个 如果落在某区间上的数少于 2^26 个则该区间中存在没有出现过的数
第一次遍历 申请长度为 64 的整形数组countArr[0…63]统计区间i上的数有多少。遍历 40亿 个数根据遍历值决定哪一个区间上的计数增加。 此时使用的内存为 64*4B 256B
第二次遍历 假设第 37 区间上的数少于 2^26
申请长度为 2^26 的位数组bitArr占用 2^26 / 8 B 2^23 B 2^3 MB 8MB的空间遍历 40亿 个数此时遍历只关注落在第 37 区间上的数记为 num num满足 num // 2^26 37其他区间的数忽略如果num在第 37 区间上bitArr[num] 1遍历 40亿 个数完成后查找bitArr上未设置成1的数如bitArr[i] ! 1则 2^26*37 i 就是40亿中没有出现过的数
总结
根据10MB的内存限制确定统计区间的大小即第二次遍历时 bitArr 的大小利用区间计数的方式找到计数不足的区间这个区间上肯定有没出现的数对这个区间上的数做bit map映射再遍历bit map找到一个没出现的数
1.3 如何确定分块的区间
保证第二次遍历时每个块都能放进限制的空间中
上面例子中2^23B 10MB 224B223B 8MB所以每块大小确定为8MB分成64块 所以至少分成 64 块分成128块、256块也是可以的。
2.用2GB内存在 20亿 个整数中找到出现次数最多的数
题目要求 有一个包含 20亿 个全是32位整数的大文件在其中找到出现次数最多的数要求内存限制为 2GB。
思路分析 在很多整数中找到出现次数最多的数通常做法是用哈希表做词频统计key为整数value为出现次数 20亿2^32-1 value不会溢出一条记录占用内存 4B4B 8B 当哈希表记录数为 2亿 条时需要占用内存 2亿*8B 1.6GB内存 极端情况20亿个整数都不同需要20亿条记录占用16GB内存不满足要求
内存溢出解决办法
把包含 20亿 个数的大文件用哈希函数分成16个小文件然后对每一个小文件用哈希表来统计每种数出现的次数得到16个小文件中各自出现次数最多的数及其次数统计后面选出这16个小文件中各自的第一名中谁出现的次数最多即可
根据哈希函数的性质
同一种数不可能被散列到不同的小文件上每个小文件中不同的数一定不会大于2亿种
注 此处哈希函数自己定义比如此处可将哈希函数定义为 num % 16将大文件数据分成16份 类似nginx或者一些负载均横的技术能够做到的那样子来了一个数据根据Hash原则将其打到不同的机器上去
总结
把一个大的集合通过哈希函数分配到多台机器中或者分配到多个文件里这种技巧是处理大数据面试时最常用的技巧之一。 但是具体分配多少台机器分配到多少个文件在解题时一定要确定下来面试官指定或者具体的限制 本题中确定分成16个文件就是根据内存限制 2GB 的条件来确定的
3.从100亿个URL中查找的问题
题目有一个包含 100 亿个URL的大文件假设每个URL占用64B请找出其中所有重复的URL
补充问题某搜索公司一天的用户搜索词汇是海量的百亿数据量请设计一种求出每天热门 top 100词汇的可行办法
思路分析
使用解决大数据问题的常规方法 把大文件通过哈希函数分配到机器或者把大文件拆分成小文件一直进行这种规划直到划分的结果满足资源限制的要求。
首先需要向面试官询问资源上的限制有哪些包括内存、计算时间等要求。明确限制条件之后将每条URL通过哈希函数分配到若干台机器或者拆分成若干小文件此处若干由具体的资源限制来计算出精确的数量然后处理每一个小数量的集合
牢记哈希函数分流/分小文件处理小数量集合
补充问题分析 还是用分流的思路来处理加上堆结构和外排序的手段进行处理
处理每一个小文件/每一台机器的时候通过哈希表统计每种词及其词频 哈希表记录建立完成后遍历哈希表的过程中使用大小为 100 的小根堆 来筛选出每一个小文件/每一台机器的top100 然后不同机器/不同小文件 之间的top100再进行外排序或者继续利用小根堆最终求出整个百亿数据量中的top100
总结
对于top k的问题除用哈希函数分流和用哈希表做词频统计之外还经常用堆结构和外排序的手段进行处理
4.从40亿个非负整数中找到出现两次的数
题目要求 32位无符号整数的范围是 0~2^32 - 1(4294967295)现在有 40 亿个无符号整数可以使用最多1GB的内存找出所有出现了两次的数。
注本题可以看做是第一题的进阶问题这里将出现次数限制在了两次
思路分析
可以用 bit map 的方式来表示数出现的情况 申请一个长度为 (2^32-1)*2 的 bit 类型的数组bitArr用2个位置表示一个数出现的词频 bitArr占用空间计算 (2^32-1)*2 bit 2^3 * 2^10 * 2^10 * 2^10 - 2 bit ≈ 1GB具体操作遍历 40亿 个非负整数 如num数字 未出现初始设置 bitArr[num2]和bitArr[num21]分别设置为 00 首次出现 bitArr[num2]和bitArr[num21]分别设置为 01 2次出现 bitArr[num2]和bitArr[num21]分别设置为 10 2次出现 bitArr[num2]和bitArr[num21]分别设置为 11 遍历 bitArr 若 bitArr[i2]和[i21]为10则i就是出现了两次的数
