场景题面试题——第一篇

1. 什么是海量数据处理，有哪些方法

海量数据处理 是指基于海量数据的存储、处理和操作。正因为数据量太大，所以导致要么无法在短时间内迅速解决，要么无法一次性装入内存。
对于 时间问题，可以采用巧妙的算法搭配合适的数据结构（如 布隆过滤器、哈希、位图、堆、数据库、倒排索引、Trie树 ）来解决。
对于 空间问题，可以采用分而治之（哈希映射）的方法，也就是说，把规模大的数据转化为规模小的，从而各个击破。
此外，还有常说的单机及集群问题：

• 单机指处理装载数据的机器有限（只要考虑CPU、内存、硬盘之间的数据交互）
• 集群指机器有多台，适合分布式处理或者并行计算，更多考虑节点与节点之间的数据交互。

处理海量数据问题，有10种典型方法

• 哈希分治
• simhash算法
• 外排序
• MapReduce
• 多层划分
• 位图
• 布隆过滤器
• Trie树
• 数据库
• 倒排索引

2. 什么是哈希分治

对于海量数据而言，由于无法一次性装进内存处理，不得不把海量的数据通过hash映射的方法分割成相应的小块数据，然后在针对各个小块数据通过hash_map进行统计或者操作。
hash映射，简单来说，就是为了便于计算机在有限的内存中处理大数据，我们通过一种映射散列的方式让数据均匀分布在对应的内存位置（如大数据通过取余的方式映射成小数据存放在内存中，大文件映射成多个小文件），这种散列的方式便是我们通常所说的hash函数，好的hash函数能让数据均匀分布而减少冲突。

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

• 思路
  如果想一次性把所有IP数据装进内存处理，则内存容量通常不够，故 针对数据太大，内存受限的情况，可以把大文件转换成小文件，逐个处理。即，先映射，而后统计，最后排序。
• 步骤
  1. 先映射：首先将该日访问百度的所有IP从访问日志中提取出来，然后逐个写入到一个大文件中，接着采取hash映射的方法（比如hash(IP) % 1000）,把整个大文件的数据映射到1000个小文件中。
  2. 统计：当大文件转化成了小文件，那么我们便可以采用map(ip,count)来分别对1000个小文件中的IP进行频率统计，找出每个小文件中出现频率最大的IP，总共1000个ip。
  3. 堆排序/快速排序 统计出1000个频率最大的IP后，依据它们各自频率大小进行排序，找出那个出现频率最大的IP，即为所求。

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

• 思路
  内存大小只有1M，而文件却有1GB，所以必须将该大文件切分为多个小于1M的小文件。
• 步骤：
  1. 哈希映射：按先后顺序读取文件，对于每个词x，执行hash(x)%5000，然后将该值存到5000个小文件中，如此每个文件大小大概是200k左右，当然，如果其中有的小文件超过了1MB大小，则可以按照类似的方法继续往下分，直到分解到每个小文件的大小都不超过1M。
  2. 统计：对于每个小文件中出现的词进行频率统计。将每个词出现的频率写入小文件中。
  3. 堆排序/归并排序：对5000个小文件中出现的词频率进行归并排序，取出前100。

5. 给定a、b两个文件，各存放50亿个URL，每个URL各占64字节，内存限制是4G，请找出a、b文件共同的URL。

• 思路：可以估计每个文件的大小为5G*64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。
• 步骤
1. 哈希映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为a1、a2、a3、a4）中，这样每个小文件的大小约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000个小文件中（记为b1、b2、b3、b4）。这样处理后，所有可能相同的url都在对应的小文件url。然后我们只需要求出1000对小文件中相同的url即可。
2. 统计： 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hashset中，然后遍历另一个小文件的每个url，看是否在刚构建的hashset中，如果是，那么就是共同的url，存到文件里面即可。

6. 什么是位图

位图就是用一个bit位来标记某个元素对应的value，而key即是该元素。由于采用了bit为单位来存储数据，因此在存储空间方面，可以大大节省。
位图通过使用bit数组来表示某些元素是否存在，可进行数据的快速查找、判重、删除，一般来说数据范围是int的10倍以下。
例如，要对{4,7,2,5,3}进行排序，可以设置一个范围为0～8的比特数组，读入数据之后将比特数组第2、3、4、5、7位置设置为1，最后从头遍历比特数组，将比特数组值为1的数据读出得到{2,3,4,5,7}这个已排序的数据。

7. 如何在2.5亿个整数中找出不重复的整数（内存不足以容纳2.5亿个整数）

分析：采用2-Bitmap（即每个整数分配2bit：00表示不存在，01表示出现一次，10表示多次，11表示无意义）。这样，所占内存2^32*2bit=1Gb.
步骤：

1. 扫描：扫描这2.5亿个整数，查看BitMap中相应位，如果是00变为01，01变10，10保持不变。
2. 输出：查看对应位为01的整数，输出即可。

8. 如何在40亿个不重复且没排过序的整数中，快速判断某个数是否在其中

分析：使用位图分析方法，40 * 10 ^ 8 = 4 * 10 ^ 9 bit=500M,所以可以申请512M内存
步骤：读入40亿个数，设置相应的bit位，读入要查询的数，查看相应的bit位是否位1，为1表示存在，为0表示不存在。

9 . 什么是布隆过滤器

布隆过滤器 是一种空间效率很高的随机数据结构，可以看做是对位图的扩展。
原理：当一个元素被加入集合时，通过K个hash函数将这个元素映射成一个位阵列中的K个点，并将他们设置为1.在检索一个元素是否在一个集合中时，只要看看这些点是不是都为1就能判断出集合中有么有他了。如果这些点有任何一个0，则被检索元素一定不在，如果都是1，则被检索元素很可能存在集合中（因为哈希函数的特点，两个不同的数通过哈希函数得到的值可能相同）。
布隆过滤器有一定的误判率：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，他 不适合那些零错误的应用场合，而在能容忍低错误率的应用场合下，布隆过滤器通过极少的错误换取了存储空间的极大节省。

10. A、B两个文件各存放50亿条URL，每条URL占用64字节，内存限制是4G，如何找出A、B文件共同的URL

分析：如果允许有一定的错误率，可以使用布隆过滤器，4G内存大概是320亿bit。
步骤：将其中一个文件中的url使用布隆过滤器映射为这320亿个bit，然后读取另外一个文件的url，使用布隆过滤器进行判重，如果是重复的，那么该url就是共同的url（允许有一定的错误率的情况）。