长春美容网站建设,新加坡网址大全,廊坊网站制作策划,影视公司联系方式从40亿中产生一个不存在的整数 给定一个输入文件#xff0c;包含40亿个非负整数#xff0c;请设计一个算法#xff0c;产生一个不存在该文件中的整数#xff0c;假设你有1GB的内存来完成这项任务。 进阶#xff1a;如果只有10MB的内存可用#xff0c;该怎么办#xff1f…从40亿中产生一个不存在的整数 给定一个输入文件包含40亿个非负整数请设计一个算法产生一个不存在该文件中的整数假设你有1GB的内存来完成这项任务。 进阶如果只有10MB的内存可用该怎么办 不用写代码将思路方法说清楚。 1GB内存
假设用哈希表来保存出现过的数如果40亿个数都不同则哈希表的记录数为40亿条存一个32位整数需要 4B 空间,所以最差情况下需要40亿 * 4B 160亿字节大约需要16GB的空间不符合要求。10亿字节 0.93GB ≈ 1GB100万字节 0.95MB ≈ 1MB
采用位存储是常用的思路。位存储最大的好处是占用的空间是简单存整数的1/32, 16G / 32 0.5G 500MB 满足要求。
具体地说因为500MB 4,194,304,000 bit 2 ^ 32 bit 4,294,967,295 bit而创建bit数组的大小一般是2的幂次方且在10MB内存限制的场景下一般来说我们以2的整数倍来划分数据块。所以我们申请一个长度为 4,294,967,295 的 bit 类型的数组 bitArr ( boolean 类型)bitArr 上的每个位置只有0或1状态。遍历这40亿个无符号数遍历到某个数就在 bitArr 相应位置的值设置为1。例如遇到1000就把 bitArr[1000] 设置为1。
遍历完数据后再遍历 bitArr ,哪个位置上的值没被设置为1这个位置所表示的数就不在40亿个数中。例如bitArr[8001] 0 ,那么8001就是没出现过的数。遍历完 bitArr 之后所有没出现的数就都找出来了。
位存储的核心是不存储这40亿个数据本身而是存储数据在位图中的对应位置。
10MB内存
使用分块思想用时间换空间通过两次遍历搞定。
40亿个数需要500MB的空间如果只有10MB的空间则至少需要将数据分为50个块。而一般来说我们以2的整数倍来划分数据块。
10MB 83,886,080 bit 2^27 134,217,728 bit而恰好 2^26 bit 67,108,864 bit 8MB 所以每个数据块的大小最大为8MB即分成 4,294,967,295 bit / 67,108,864 bit 63.99 ≈ 64 块 即每个数据块包含67,108,864个数字。在这里最少要分成64块分成128块、256块也是可以的每个数据块所含的数字更少即存储数据占用的内存更少当然可以。
首先将0~4,294,967,295 这个范围平均分成64个区间64块每个区间包含67,108,864个数67,108,864 bit例如
第0区间0 ~ 67108863第1区间67108864 ~ 134217728第 i 区间67108864 * i ~ 67108864 *(i1) - 1…第63区间4227858432~4294967295
因为一共只有40亿个数所以如果统计落在每一个区间上的数分别有多少则至少有一个区间上的计数少于67108864。利用这一特点我们可以找出其中一个乃至多个没出现过的数。
具体则是通过两次遍历40亿个数实现
第一次遍历
申请长度为64的整型数组countArr, countArr[i]用统计在这40亿个数中属于第 i 区间的有多少个。使用的内存是countArr的大小(64 * 4B)非常小可忽略不计。遍历40亿个数根据当前的数来决定哪一个区间上的计数增加。例如如果当前数是3422552090, 3422552090 / 67108864 51,所以第51区间上的计数增加1即countArr[51]。
遍历完40亿个数之后遍历countArr必然存在一个i使countArrl[i]小于67108864表示第i区间上至少有一个数没出现过。
假设第37区间上的计数小于67108864那么我们对这40亿个数据进行第二次遍历
申请长度为 67108864 的bit型数组bits,占用8MB的空间遍历这40亿个数即当前数为num当num满足num / 67108864 37才进行第3步否则继续遍历。将bits[num - 6710886437 * 37]的值设置为1。遍历完40亿个数之后bits中必然存在没被设置成1的位置假设bits中第i个位置没被设置成1,那么6710886437 * 37 i就是一个没出现过的数。
总结一下进阶的解法
根据10MB的内存限制确定统计区间的大小即第二次遍历时bits的大小。利用区间计数的方式找到计数不足的区间countArrl[i]这个区间上肯定存在没出现的数。第二次遍历40亿个数在计数不足的区间上进行位存储再遍历bits这次遍历的耗时可忽略找出一个没出现的数。
用 2GB 内存在 20 亿个整数中找到出现次数最多的数 有一个包含 20 亿个全是 32 位整数的大文件你需要在其中找到出现次数最多的数内存限制为 2GB。 在很多整数中找到出现次数最多的数通常的做法是使用哈希表对出现的每一个数做词频统计哈希表的 key 是某一个整数value 是这个数的出现次数。
就本题来说一共有 20 亿个数哪怕只是一个数出现了 20 亿次用 32 位的整数也可以表示其出现的次数而不会产生溢出2^32 - 1 20亿。哈希表的 key 占用 4Bvalue 占用是 4B。那么哈希表的一条记录key,value需要占用 8B当哈希表记录数为 2 亿个时需要至少 1.6GB 的内存。
如果 20 亿个数中不同的数超过 2 亿种最极端的情况是 20 亿个数都不同那么在哈希表中可能需要产生 20 亿条记录这样内存会不够用所以一次性用哈希表统计 20 亿个数的办法是有很大风险的。
解决办法是把包含 20 亿个数的大文件用哈希函数分成 16 个小文件。根据哈希函数的性质同一种数不可能被散列到不同的小文件上同时每个小文件中不同的数一定不会大于 2 亿种假设哈希函数足够优秀。然后对每一个小文件用哈希表来统计其中每种数出现的次数这样我们就得到了 16 个小文件中各自出现次数最多的数还有各自的次数统计。接下来只要选出这16 个小文件各自的第一名再比较出出现次数最多的即可。
把一个大的集合通过哈希函数分配到多台机器中或者分配到多个文件里这种技巧是处理大数据面试题时最常用的技巧之一。但是到底分配到多少台机器、分配到多少个文件可能是在与面试官沟通的过程中由面试官指定也可能是根据具体的限制来确定。比如本题确定分成 16 个文件就是根据内存限制 2GB 的条件来确定的。
从100亿个URL中查找的问题 题目有一个包含100亿个URL的大文件假设每个URL占用64B,请找出其中所有重复的URL。 使用解决大数据问题的一种常规方法把大文件通过哈希函数分配到机器或者通过哈希函数把大文件拆成小文件一直进行这种划分直到划分的结果满足资源限制的要求。
首先你要向面试官询问在资源上的限制有哪些包括内存、计算时间等要求。在明确了限制要求之后可以将每条URL通过哈希函数分配到若干台机器或者拆分成若干个小文件这里的“若干”由具体的资源限制来计算出精确的数量。
例如将100亿字节的大文件通过哈希函数分配到100台机器上然后每一台机器分别统计分给自己的URL中是否有重复的URL哈希函数的性质决定了同一条URL不可能分给不同的机器或者在单机上将大文件通过哈希函数拆成1000个小文件对每一个小文件再利用哈希表遍历找出重复的URL还可以在分给机器或拆完文件之后进行排序排序过后再看是否有重复的URL出现。
总之牢记一点很多大数据问题都离不开分流要么是用哈希函数把大文件的内容分配给不同的机器要么是用哈希函数把大文件拆成小文件然后处理每一个小数量的集合。 补充问题某搜索公司一天的用户搜索词汇是海量的百亿数据量请设计一种求出每天热门Top100词汇的可行办法。 一句话分流哈希表统计词频小根堆找各自的 top100在汇合比较出最终的 top100。
补充问题最开始还是用哈希分流的思路来处理把包含百亿数据量的词汇文件分流到不同的机器上具体多少台机器由面试官规定或者由更多的限制来决定。对每一台机器来说如果分到的数据量依然很大比如内存不够或存在其他问题可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。处理每一个小文件的时候通过哈希表统计每种词及其词频哈希表记录建立完成后再遍历哈希表遍历哈希表的过程中使用大小为100的小根堆来选出每一个小文件的Top100(整体未排序的Top100)。每一个小文件都有自己词频的小根堆整体未排序的Top100)将小根堆里的词按照词频排序就得到了每个小文件的排序后Top100。然后把各个小文件排序后的Top100进行外排序或者继续利用小根堆就可以选出每台机器上的Top100。不同机器之间的Top100再进行外排序或者继续利用小根堆最终求出整个百亿数据量中的Top100。对于TopK的问题除用哈希函数分流和用哈希表做词频统计之外还经常用堆结构和外排序的手段进行处理。
40亿个非负整数中找到出现两次的数 32位无符号整数的范围是0~4294967295现在有40亿个无符号整数可以使用最多1GB的内存找出所有出现了两次的数。 本题可以看做是第一题的进阶这里将出现次数限制在两次。
首先可以用 bit map位图即位存储的方式来表示数出现的情况。具体地说是申请一个长度为4294967295x2的bit类型的数组bits,用2个位置表示一个数出现的词频1B占用8个bit,所以长度为4294967295 x 2的bits占用1GB空间。
然后遍历这40亿个无符号数初次遇到num,就把bits[num*21]和bits[num*2]设置为01,第二次遇到num,就把bits[num*21]和bits[num*2]设置为10第三次遇到num,就把bits[num*21]和bits[num*2]设置为11。以后再遇到num就不再做任何设置。
40亿个无符号数遍历完成后再遍历bits,如果bits[i*21]和bitArr[i*2]为10那么i就是出现了两次的数。
