海量数据处理的面试题

2019-10-23 本文已影响0人 Phoebe_Liu

1. 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

引出Bitmap
举一个小例子，有一个无序整形数组{8,4,9}，也就占用内存34=12字节，这很正常，但如果有1亿个这样的数呢？1亿4/(102410241024)=0.372G左右。如果对该数据做查找，那内存压力很大，我们想要高性能地解决这个问题，就得引出Bitmap。

Bitmap概念
一个byte占8个bit，如果每一个bit的值就是有或没有，也就是二进制的0或1。那就可用bit的0或1代表某数组值有或没有。0代表该数值没有出现过，1代表该数组值出现过。具体如下图：

bitmap.png

那1亿的数据现在所需的空间0.372G/32，一个原占32bit的数据现在只占用1bit，节省了不少内存。

应用和代码
疑问：一个数怎么快速定位它的索引，也就是说搞清楚byte[index]的索引号index是多少，位置号position是哪一位。

例子：例如add(14)。14已经超出byte[0]的映射范围，在byte[1]的范围内。那怎么快速定位它的索引号？如果找到它的索引号，又怎么找到它的位置号？Index(N)代表N的索引号，Position(N)代表N的位置号。

公式：
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 7;

例子：
add(int num)向Bitmap里add数据该怎么办?
上面已分析了，add的目的是为了将所在的位置从0变成1，其他位置不变。
（图中间，不是“作与操作”，是“作或操作”。“a|=b”表示a和b作或操作，结果赋给a。）

代码：

public void add(int num)
{
    int index=num>>3;
    int position=num&7;
    byte[index] |= 1<<position;//如图，将1左移position位，使目标位置1
}

总结： Bitmap是简单快速的数据结构，常用于空间的优化。
解题：一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位。由于2^{32=42.9+亿，那么2}32bit才能存下40亿个数，也就需要2^32=4Gb=0.5GB=512M内存。读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

2. 在2.5亿个整数找出不重复的整数，内存不足以容纳着2.5亿个整数。

2-Bitmap
每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，其他同Bitmap。

方案1：使用2-Bitmap
每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义。然后遍历修改Bitmap中的对应位，如果是00则变01，01则变10，10则保持不变。遍历修改完后，最后遍历输出对应位是01的整数。


#include <cstdio>
#include <iostream>
using namespace std;
 
unsigned char bitmap[1005];
 
//x表示一个整数，num表示bitmap中已经拥有x的个数
//由于我们只能用2个bit来存储x的个数，所以num的个数最多为3
void set(int x,int num){
    int m = x >> 2;
    int n = x & 3;
 
    //将x对于为值上的个数值先清零，但是有要保证其他位置上的数不变
    bitmap[m] &= ~((0x3<<(2*n)) & 0xFF);
    //重新对x的个数赋值
    bitmap[m] |= ((num&3)<<(2*n) & 0xFF);
}
 
void clear(int x){
    int m = x >> 2;
    int n = x & 3;
    bitmap[m] &= ~((0x3<<(2*n)) & 0xFF);
}
 
unsigned char get(int x){
    int m = x >> 2;
    int n = x & 3;
 
    return (bitmap[m] & (0x3<<(2*n))) >> (2*n);
}
 
void add(int x){
    int num = get(x);
    set(x,num+1);

方案2：分治法
先将2.5亿个数划分成 2.5亿/2 个组，每个组里2个整数，再在每个组里去掉重复的整数后进行排序，然后再进行归并，最终便可得到只出现过一次的整数。

3. top k 问题: 海量日志数据，提取出某日访问百度次数最多的那个IP。

主要问题：
IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理

解决方案：

采用映射的方法，比如模1000，把整个大文件映射为1000个小文件

再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP

4.统计最热门的10个查询串

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

主要问题：

内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。

解决方案：多路归并排序

外部排序指的是大文件的排序，当待排序的文件很大时，无法将整个文件的所有记录同时调入内存进行排序，只能将文件存放在外存，这种排称为外部排序。外部排序的过程主要是依据数据的内外存交换和“内部归并”两者结合起来实现的。

外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlgN)。排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。综合分析一下，排序的时间复杂度是O(NlgN)，而遍历的时间复杂度是O(N)

总体时间复杂度：O(N+NlgN)=O（NlgN）。

5.有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

分析：
（1）分文件（在外存中进行）

顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。

（2）文件内排序（内存中）
对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。

（3）归并
下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

6.有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

（1）读取文件，重复的合并到一个文件中

顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

（2）排序
找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。

（3）归并
对这10个文件进行归并排序（内排序与外排序相结合）。