面试总结:大数据题

1. 认识布隆过滤器

题目

不安全网页的黑名单包含 100 亿个黑名单网页,每个网页的 URL 最多占用 64 B。限制响应实现一种网页过滤系统,可以根据网页的 URL 判断该网页是否在黑名单上,请设计该系统。

要求

  1. 该系统允许有万分之一以下的判断失误率。
  2. 使用的额外空间不要超过 30 GB。

解答

提示:一个布隆过滤器精确地代表一个集合,并且可以精确判断一个元素是否在集合中。

补充:一个优秀的哈希函数能够做到很多不同的输入值所得到的返回值非常均匀地分布在 S 上,那么将所有的返回值对 m 取余,可以认为所有的返回值也会均匀地分布在 0 ~ m-1 的空间上。

布隆过滤器:假设有一个长度为 m 的 bit 类型的数组,即数组中的每一个位置只占一个 bit,每一个 bit 只有 0 和 1 两种状态。再假设一共有 k 个哈希函数,这些函数的输入域 S 都大于或等于 m,并且这些哈希函数都足够优秀,彼此之间也完全独立。那么对同一个输入对象(假设是一个字符串记为 URL),经过 k 个哈希函数算出来的结果也是独立的,可能相同,也可能不同,但彼此独立。对算出来的每一个结果都对 m 取余,然后在 bit array 上把相应的位置设为 1。我们把 bit 类型的数组记为 bitMap。至此,一个输入对象对 bitMap 的影响过程就结束了,即 bitMap 中的一些位置会被涂黑。接下来按照该方法处理所有的输入对象,每个对象都可能把 bitMap 中的一些白位置涂黑,也可能遇到已经涂黑的位置,遇到已经涂黑的位置让其继续为黑即可。处理完所有的输入对象后,可能 bitMap 中已经有相当多的位置被涂黑。至此,一个布隆过滤器生成完毕,这个布隆过滤器代表之前所有输入对象组成的集合。

那么在检查阶段时,假设一个对象为 a,想检查它是否是之前的输入对象,就把 a 通过 k 个哈希函数算出 k 个值,然后把 k 个值取余,就得到在 0 ~ m-1 范围上的 k 个值。接下来在 bitMap 上看这些位置是不是都为黑,如果有一个不为黑,就说明 a 一定不在这个集合里。如果都为黑,说明 a 在这个集合里。

如果 bitMap 的大小 m 相比输入对象的个数 n 过小,失误率会变大。接下来介绍根据 n 的大小和我们想要达到的失误率 p,如果确定布隆过滤器的大小 m 和哈希函数的个数 k,最后是布隆过滤器的失误率分析。

比如,黑名单样本的个数为 100 亿个,记为 n;失误率不能超过 0.01%,记为 p;每个样本的大小为 64 B,这个信息不会影响布隆过滤器的大小,只和选择哈希函数有关,一般的哈希函数都可以接收 64 B 的输入对象,所以使用布隆过滤器还有一个好处是不用顾忌单个样本的大小,它丝毫不能影响布隆过滤器的大小。

所以 n = 100 亿,p = 0.01%,布隆过滤器的大小 m 由以下公式确定:

$$m = - \frac{n \times ln p}{(ln 2)^2}$$

根据公式计算出 m = 19.19n,向上取整为 20n,即需要 2000 亿个 bit,也就是 25 GB。

哈希函数的个数由以下公式决定:

$$k = ln 2 \times \frac{m}{n} = 0.7 \times \frac{m}{n}$$

计算出哈希函数个数为 k = 14 个。

然后用 25 GB 的 bitMap 再单独实现 14 个哈希函数,根据如上描述生成布隆过滤器即可。

因为我们在确定布隆过滤器大小的过程中选择了向上取整,所以还要用如下公式确定布隆过滤器真实的失误率为:

$$(1 - e^{- \frac{nk}{m}})^k$$

根据这个公式算出真实的失误率为0.006%,这是比 0.01 % 更低的失误率。

2. 只用 2GB 内存在 20 亿个整数中找到出现次数最多的数

题目

在一个包含 20 亿个全是 32 位整数的大文件,在其中找到出现次数最多的数。

要求

内存限制为 2 GB

解答

想要在很多整数中找到出现次数最多的数,通常的做法是使用哈希表对出现的每一个数做词频统计,哈希表的 key 是某一个整数,value 是这个数出现的次数。就本题而言,一共有 20 亿个数,哪怕只是一个数出现 20 亿次,用 32 位的整数也可以表示其出现的次数而不会产生溢出,所以哈希表的 key 需要占用 4B,value 也是 4B。那么哈希表的一条记录(key,value)需要占用 8B,当哈希表记录数为 2 亿个时,至少需要 1.6GB 的内存。

但如果 20 亿个数中不同的数超过 2亿种,最极端的情况是 20 亿个数都不相同,那么在哈希表中可能需要产生 20 亿条记录,这样内存明显不够用,所以一次性用哈希表统计 20 亿个数非常冒险。

解决的方法是把包含 20 亿个数的大文件用哈希函数分成 16 个小文件,根据哈希函数的性质,同一种数不可能被哈希到不同的小文件上,同时每个小文件中不同的数一定不会大于 2 亿种,假设哈希函数足够好。然后对每一个小文件用哈希表来统计其中每种数出现的次数,这样我们就得到了 16 个小文件中各自出现次数最多的数,还有各自的次数统计。接下来只要选出 16 个小文件各自的第一名中谁出现的次数最多即可。

3. 40 亿个非负整数中找到没出现的数

题目

32 位无符号整数的范围是 0 ~ 4294967295,现在有一个正好包含 40 亿个无符号整数的文件,所以在整个范围中必然有没出现过的数。可以使用最多 1 GB 的内存,怎么找到所有没出现过的数。

进阶

内存限制为 10 MB

解答

如果用哈希表来保存出现过的数,那么如果 40 亿个数都不同,则哈希表的记录数为 40 亿条,存一个 32 位整数需要 4B,所有最差情况下需要 40 亿 * 4B = 160 亿字节,大约需要 16 GB的空间,不符合要求。

哈希表需要占用很多空间,我们可以使用 bit map 的方式来表示数出现的情况。具体的,申请一个长度为 4294967295 的 bit 类型的数组上的每个位置只可以表示 0 或 1 状态。8 个 bit 为 1B,所以长度为 4294967295 的 bit 类型的数组占用 500 MB 空间。

进阶问题:现在只有 10 MB 的内存,但也只要求找到其中一个没出现的数即可,首先,0 ~ 4294967295 这个范围是可以平均分成 64 个区间的,每个区间是 67108864 个数。因为一共只有 40 亿个数,所以,如果统计落在每一个区间上的数有多少,肯定至少一个区间上的计数少于 67108864。利用这一点可以找出其中一个没出现的数。

具体过程如下: 第一次遍历时,先申请长度为 64 的整型数组 countArr[0…63],countArr[i] 用来统计区间 i 上的数有多少。遍历 40 亿个数,根据当前数是多少来决定哪一个区间上的计数增加。例如,如果当前数是 3422552090,3422552090 / 67108864 = 51,所以第 51 区间上的计数增加,遍历完所有数之和遍历 countArr,必然会有某一个位置上的值小于 67108864,表示第 i 区间上至少有一个数没出现过。我们肯定会至少找到一个这样的区间。此时内存使用为 64 * 4B,是非常小的。

假设我们找到第 37 区间上的计数小于 67108864,以下为第二次遍历的过程:

  1. 申请长为 67108864 的 bit map,这占用大约 8 MB 的空间。
  2. 再遍历一次 40 亿个数,此时的遍历只关注落在第 37 区间上的数。
  3. 之后的方法同普通方法类似。
  4. 遍历完 40 亿个数之后,在 bitArr 上必然存在没被设置为 1 的位置,假设第 i 个位置上的值没设置为 1,那么 67108864 * 37 + i 这个数就是一个没出现过的数。

4. 找到 100 亿个 URL 中重复的 URL 以及搜索词汇的 top K 问题

题目

有一个包含 100 亿个 URL 的大文件,假设每个 URL 占用 64 B,请找出其中所有重复的 URL。

补充题目

某搜索公司一天的用户搜索词汇是海量的,请设计一种求出每天最热 100 词汇的可行办法。

解答

解决这种问题的常规方法是,把大文件通过哈希函数分配到机器,或者通过哈希函数把大文件拆成小文件。一直进行这种划分,直到划分的结果满足机器资源的限制。

例如,将 100 亿字节的大文件通过哈希函数分配到 100 台机器上,然后每一台机器分别统计分给自己的 URL 中是否有重复的 URL,同时哈希函数的性质决定了同一条 URL 不可能分给不同的机器;或者可以在单机上将大文件通过哈希函数拆成 1000 个小文件,对每一个小文件再利用哈希表遍历,找出重复的 URL;或者在分给机器或拆完文件之后,进行排序,排序过会再看是否会有重复 URL 出现。大数据问题的处理都离不开分流要么是哈希函数把大文件的内容分配给不同的机器,要么是哈希函数把大文件拆成小文件,然后处理每一个小数量的集合。

补充题目最开始还是哈希分流的思路来处理,把包含百亿数据量的词汇文件分流到不同的机器上,具体多少台机器由题目来确定。对每一台机器来说,如果分到的数据量依然很大,可以再用哈希函数把每台机器的分流文件拆成更小的文件处理。处理每一个小文件的时候,哈希表统计每种词及其词频,哈希表记录建立完成后,再遍历哈希表,遍历哈希表的过程中使用大小为 100 的小根堆来选出每一个小文件的 top 100。每一个小文件都有自己的词频的小根堆,将小根堆的词按照词频排序,就得到了每个小文件的排序后 top 100。然后把各个小文件排序后的 top 100 进行外排序或者继续利用小根堆,就可以选出每台机器上的 top 100。不同机器之间的 top 100 再进行外排序或者继续利用小根堆,最终求出整个百亿数据量中的 top 100。对于 top k 的问题,除哈希函数分流和用哈希表做词频统计之外,还经常用堆结构和外排序的手段进行处理。

5. 40 亿个非负整数中找到出现两次的数和所有数的中位数

题目

40 亿个非负整数中找到出现两次的数和所有数的中位数

补充题目

可以使用最多 10 MB 的内存,怎么找到这 40 亿个整数的中位数

解答

可以使用 bit map 的方式来表示数出现的情况。申请一个长度为 4294967295 2 的 bit 类型的数组 bitArr,用 2 个位置表示一个数出现的词频, 1B 占用 8 个 bit,所以长度为 4294967295 2 的 bit 类型的数组占用 1 GB 空间,

遍历这 40 亿个无符号数,如果再次遇到 num, 就把 bitArr[num2 + 1] 和 bitArr[num 2] 设置为 01,如果第二次遇到 num,则设置为 10,如果第三次遇到 num,就把它设置为 11,以后再遇到 num,发现此时 bitArr[num2 + 1] 和 bitArr[num 2] 已经被设置为 11,就不再做任何设置。遍历完成后,再次遍历 bitArr,如果发现 bitArr[num2 + 1] 和 bitArr[num 2] 设置为 10,那么 i 就是出现了两次的数。

对于补充问题,用分区间的方式处理,长度为 2 MB 的无符号整型数组占用的空间为 8 MB,所以将区间的数量定为 4294967295/2M,向上取整为 2148 个区间。

申请一个长度为 2148 的无符号整型数组 arr[0…2147],arr[i]表示第 i 区间有多少个数。arr 必然小于 10 MB。然后遍历 40 亿个数,如果遍历到当前数为 num,先看 num 落在哪个区间上(num / 2M),然后将对应的进行arr[num/2M] ++ 操作,这样遍历下来,就得到了每一个区间的数的出现状况,通过累加每个区间的出现次数,如果遍历到当前数为 num,先看 num 落在哪个区间上(num / 2M),然后将对应的进行 arr[num/2M]++ 操作。这样遍历下来,就得到了每一个区间的数的出现状况,通过累加每个区间的出现次数,就可以找到 40 亿个数的中位数到底落在哪个区间。假设为第 K 区间。

接下来申请一个长度为 2MB 的无符号整型数组 countArr[0..2M-1],占用空间 8MB。然后再遍历 40 亿个数,此时只关心处在第 K 区间的数记为 numi,其他的数省略,然后将 countArr[numi-K*2M]++,也就是只对第 K 区间的数做频率统计。这次遍历完 40 亿个数之后,就得到了第 K 区间的词频统计结果 countArr,最后只在第 K 区间上找到相应的第几个数字即可。