大数据面试题

先来把网上搜到的大数据面试题归类列出来，然后聊聊方法、总结和方法论。

题目汇总

频率类

• 海量1T日志数据，找出某日访问次数最多的那个IP。
• 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节，找出最多的 query。
• 怎么在海量数据中找出重复次数最多的一个？

Top K

• 1G个数中找出最大的100个数。
• 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
• 海量1T数据分布在多台电脑（可以假设数据为字符串），想个办法高效统计出这批数据的TOP10。
• 上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
• 100G 个 int64 中找出第 K 大的数，1G 内存

排序类

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

判重类

• 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
• 在10亿个 int 中找出不重复的整数，1G 内存。
• 给40亿个单词，没排过序的，然后再给一组 query 词，如何快速query 是否在那40亿个单词中？

瞎搞类

• 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中位数。

背景知识

内存空间计算方法

单位大小

Symbol	Prefix	SI Meaning	Binary meaning	Size difference
k	kilo	10^3 = 1000^1	2^10 = 1024^1	2.40%
M	mega	10^6 = 1000^2	2^20 = 1024^2	4.86%
G	giga	10^9 = 1000^3	2^30 = 1024^3	7.37%
T	tera	10^12 = 1000^4	2^40 = 1024^4	9.95%
P	peta	10^15 = 1000^5	2^50 = 1024^5	12.59%
E	exa	10^18 = 1000^6	2^60 = 1024^6	15.29%
Z	zetta	10^21 = 1000^7	2^70 = 1024^7	18.06%
Y	yotta	10^24 = 1000^8	2^80 = 1024^8	20.89%

• 程序里的内存默认是指上面表的Binary meaning，而硬盘内存大小一般是指SI Meaning。
• 1 bit：基本单元，只能表示0或1
• 1 byte：也是 1B，字节，8个bit，表示[0,256)的一个数字。
• 一般来说算法只关注复杂度，所以会忽视 size difference，绝大多数时候为了方便都是默认转换使用 10^n 这种形式，更加直观。

程序语言常用类型大小

char ：1个字节
short int : 2个字节
int：  4个字节
unsigned int : 4个字节
float:  4个字节
double:   8个字节
long:   4个字节
long long:  8个字节
unsigned long:  4个字节
需要特殊注意的是：
char*（指针变量）: 4个字节（32位的寻址空间是2^32, 即32个bit，也就是4个字节。同理64位编译器是8个字节）

数据结构知识背景

• 面试嘛，最难不过二叉树，知乎搜到了一个问题，直接看看吧，有一个大致的介绍数据结构与算法中，树一般会应用在哪些方面？为什么？
• 重点，不懂的可以多查查关键词：
  • 基础的，栈，队列，链表。
  • Heap，堆
    • 快速查询 Top 1 类问题，可以快速增删元素。
  • TRIE，字典树，可以快速查询字符串类的映射，处理前缀问题。
    • 加强版，AC 自动机。
  • Treap，同时维护一个排序树Tree和一个堆Heap。
    • 典型的双权树还有 AVL，Splay。
  • 块状链表，神器级别的乱搞大法。
    • 普通的线性结构增删改查必有一个或者多个慢，但是它能在 O(sqrt(n))时间复杂度完成多种操作。加强版，莫队算法。
  • B, B+, B-。
    • 最好了解下他们的区别，设计上的区别带来的影响是什么。
  • KD-tree，用来解决高维度查询问题
    • 典型的是查询平面最近点距离。
  • 抽样哈希算法，可以用来校验完整性，用于对象选桶，可以保证分布均匀，同一个对象每次算出来是一样的值。
    • 字符串哈希 & MD5

业内常用解决方案思路

虽然一般不会直接问，但是业内的方案可以用来开拓思路。

• Redis 内部5种数据结构的实现方式。
• MapReduce 的基本原理和例子。
• MySQL 如何做到增删改查的复杂度都是O(log n)
  • 具体可以研究下这个例子，尤其要体会一下批量更新懒标记：如何在关系型数据库存树
• 各种语言的类似 Map，HashMap，OrderedMap，Set的实现方式
  • 抽象概念是如何增删改查 k-v 对。
  • 无序列表的实现方式，重点是哈希表。O(1)
  • 有序列表的实现方式，重点是平衡树。O(log n)
  • 需要仔细了解每个结构的基本节点占用多少地址空间
• 全文索引技术
  • 倒排索引，介绍。

题目解答

频率类

• 海量1T日志数据，1G内存，找出某日访问百度次数最多的那个IP。
• 搜索引擎会通过 1T 日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节，找出最多的那个query。
• 怎么在1T数据中找出重复次数最多的行。

分析方法

问题本质：原始数据无序，需要实现一个内存无法完全装下的 Map，key 为查询，value 为频率。

方法论：把需要统计的东西无依赖分块，处理每个块的时候让Map可以装下。

基本思路：

1. 先扫一遍整个文件，将其分块写入 M 个文件/块，确保每个块对应的 key 集内存能装下。
2. 对每个块进行处理，每次处理分别得到一个 Map。
3. 记录每次 Map 对应的最大值即可。

答案

问题一：

1. IP 地址本质可以表示为一个 unsigned int，32bit，按 IP 取模 M 的值将它们写入到 M 个文件，这样同一个 IP 一定会被写到同一个文件内，确保每个块对应的 IP 集内存能装下。
2. 1T 的数据说明答案需要使用 int64来装；基于哈希表的 Map 基本单元一个额外链表的地址空间和 O(n) 级别的链表头；如果是64位操作系统，地址空间会占用 int64，链表头一个 int64，加起来是 8B+8B*2，表头为什么需要和哈希基本单元数量差不多可以仔细想一想。一个合适的选择是 2 * 10^7（对应的M为216），会占用 24 * 2 *10^7 B 地址，这样可以把内存压榨到一个比较极限（略超一半）的情况。
3. 遍历第2.步的 Map，记录一个最大值，M 个最大值的答案就是最终答案。

问题二：
几乎和问题一一摸一样。
把记录答案的 int64 的 8B 换成长度 256B 的字符串即可。

问题三：
1.和2.的步骤完全一样，3.步骤做一个变换，使用多路归并排序即可，然后就是读文件的时候可以每次读 内存总量/路数 大小的 block。

Top K

• 1G个数中找出最大的100个数。
• 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
• 海量1T数据分布在多台电脑（可以假设数据为字符串），想个办法高效统计出这批数据的TOP10。
• 上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。

分析方法

问题本质：局部排序。

方法论：Top K 数字大小问题的经典解法有几种，

• 求前 K 大的数，维护一个有 K 个元素的小根堆。（内存必须能装下整个堆）
• 类似快速排序的快速分区法，可以很快得到前 K 大的元素。
• 多路归并排序。
• 求Ranking K加一种分块的方法，将 N 个数字可能存在的范围分成 M 个区间，分别统计数字频次，然后对子区间进行递归处理。如数据1...9九个数字求第5大数字，可以分成3个区块，统计[1...3,4...6,7...9]在区间内出现的频率分别为[3,3,3]，然后子问题转换为：求[4...6]这个区间的第 2 大数字。需要扫描O(log(N)/log(M))次文件。

基本思路：

1. 如果 K 不大，内存足够装下，直接使用堆（也可以是其他可以维护有序的数据结构）维护，结构里面始终保持 K 个元素即可。
2. 如果 K 很大，先进行分块写入到 M 个文件中，确保内存足够单个文件排序。然后使用多路归并排序合并若干块。在操作的时候不要一次读一行，而是一次从一个文件读取多行。甚至可以在文件剩余元素不多的时候提前预读。(请确保 每次读取行数* 行的大小 * 归并路数 < 内存)

答案

问题一：
维护一个有 K 个元素的小根堆。

问题二：
0. 最坏情况所有词都不相同，一共拥有约 6.3 * 10^7 个单词。

1. 同之前频率类的算法，64位机器的哈希基本单元需要空间(16B+8B*2)，1M 内存大约可以装 3 * 10^4 个单词，所以将单词写到大约2500个(6.3 * 10^7 / 3 * 10^4)文件内。
2. 每个文件使用 Map 分别做词频统计，此时每个文件对应一组 Map（K 为单词，V 为词频），将2500组的 Top 100 词频 KV 对写入到一个新的文件。
3. 此时，问题已经转换为问题一，求最大的 100 个 V 对应的取值。

问题三：
0. 唯一的区别在于多台电脑，场景非常像 Hadoop 对应的 MapReduce。

1. 使用一个均匀的哈希，将每个字符串发送到唯一的电脑上。
2. 每台电脑统计自己的 Top 10.
3. 汇总到一台机器，此时转换为问题一。

问题四：
0. 区别在于 N 没有给范围，可能很大。

1. 操作和问题二几乎一样。
2. 将用于统计的 Map 完整的 K-V 按照降序对写到一个文件。
3. 使用多路归并排序，归并之后的前 N 个元素就是答案。

问题五：

1. int64范围大约有 2 * 10^19个数字，我们可以选择方法论中的分块法，分成10^7个块即可。
2. 之所以不用上面的方法，是因为这个方法可以不需要写入任何内容到磁盘，只需要读三次这个文件。

排序类

偷个懒，直接去看别人的文章吧

• 视觉直观感受 7 种常用的排序算法
• 怎样给一个磁盘文件排序
• 常见的内排序和外排序算法
• 补充一个黑科技，Python 实现 sort 的 TimSort，复杂度小于 n log n 的稳定排序算法

判重类

• 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
• 在10亿个 int 中找出不重复的整数，1G 内存。
• 给40亿个单词，没排过序的，然后再给一组 query 词，如何尽可能快的判断一个query是否在那40亿个单词中？

分析方法

问题本质： 离在线问题，理应把各种操作抽象成某种数据结构的增删改查。

基本思路：

1. 类似词频的分块统计。使用哈希将数据分布到小文件，直接使用 Map 查询。
2. 充分利用内存空间，直接打01标记，分别表示是否出现过。
3. 字符串特定结构，TRIE字典树，压缩查询路径的字典树，AC 自动机。

答案

问题一：

1. 将 A 和 B 分别拆成 M 个小文件A1…Am，B1…Bm，必须使用同一个哈希函数来确保 同一个 url 被分配到同一编号的小文件 Ax 和 Bx 中，请确保每个文件的 url 能在内存中装下。
2. 对于每一组文件 Ax 和 Bx，使用一个 Set，将 Ax 中的所有 url 加入 Set，然后一次判断 Bx 中的 url 是否在 Set 中。
3. 将所有答案汇总写到一个文件里。

问题二：
0. 先考虑一个简化版本：在10亿个 int 中找出出现的整数，1G 内存。我们假设可以使用01标记来表示是否出现，计算一下需要的位置有多少，对应的内存是多少，int 对应的数字有 2^32 个 bit 位，除以8之后，也就是需要2^29B 大小，对应的空间约 500M。

1. 此时回头思考这个问题，可以有一个做法，2bit，表示一个数字是否出现过，一个位置表示是否出现过，另一个位置表示是否出现了重复。
   • 另数字初始值全部为0
   • 一个数如果没有出现过，则把它的第一个标记为打成1
   • 如果发现一个数已经出现过，则把它的第二个标记为打成1
   • 统计一遍第一个标记位为1，第二个标记位为0的数字。
2. 上面的思路是很好的思路，但是严格来说是不对的。为什么？我们计算一下空间使用，int 对应的数字有 2^33 个 bit 位，除以8之后，也就是需要2^20B 大小，对应的空间约 1G。但是！但是！但是！1G 不等于2^30B，查看我前面给的表吧。
3. 加思路。事实上，信息是足够多且有浪费的，第二个标记的初始值是没有意义的。一个位置 Zi，初始为0，如果有数字出现，给它标记为，如果它已经是2，不进行操作。一个 int 有32个位，我们计算一下需要的空间极限，(log 3/log 2)* 2^32 bit，这个值小于1G。没想清楚？每一个数字三种状态，总状态数其实只有 3 * 2^32。举个例子，按上一个方案存储3个数字的信息需要6bit，事实上状态只有3^3个，只需要 ln(3^3)/ln(2) = 3.296/0.693 < 5，也就是5个 bit 的信息足够表示这个状态。

问题三：
给两种复杂度是O(length)的方法
直接试用哈希，然后对哈希值进行比较，哈希值相同认为字符串相同，否则认为不同。数学论证
建一个 TRIE，字典树可以依次去按照字符串的第0，1，2，3…个字符依次查询子集，几乎只有单纯的寻址工作，效率非常高。

另外，然后倒排索引也是一种答案，在生产环境应该是效率非常高的，因为网站的80%的流量会落在20%的 query 上，但是十分不严谨。

瞎搞类

• 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中位数。

基本思路

有一部分题目是几种模型的结合或者没有什么特别的模型，但是只要用好分类的思想，让它形成可以分治的计算任务就可以做

答案

问题一：这个题目网上有很多人抄某个哥们的解答，但是那个解答有问题，一个是不通用算法，一个太慢了。另外，N 台机器跑 O(log N)的算法，复杂度还是O(log N)，很多答案都没有充分利用这点。
方法1，转换为上面的第 K 大问题，每台机器先自己排序O(N*log(N))，然后直接多路并归排序，找到第 N*N/2 大的数字就是答案。O(N*N*log(N*N))
方法2，先每台机器数据排升序O(N*log(N))，接下来二分中位数的大小O(log(MaxNumber))。分别查询每一台机器查询小于中位值的数字个数，如果个数小于N*N/2，拉高下界，否则拉低上限，直到数字个数和刚好等于N*N/2，由于每台机器去查询。复杂度O(N*log(N))+O(log(MaxNumber))*(O(log N) + O(N))后面的三个 O 实际意义分别是二分中位数复杂度，二分查找数字复杂度，数组并发求和复杂度，总复杂度应该是O(N*log(max(N,MaxNumber)))

总结

欢迎大家给我补充相关的题目，以及讨论有没有更好的做法。
做完这些题目，我的感觉是应该就能理解为什么要有 MapReduce 这种框架了，将数据计算过程拆成 Map 和 Reduce 确实是一种很巧妙的设计。