这是一道来自前同事腾讯一面的面试题，题面如下：
有一个 Excel 文档，只有一个 Sheet，只有一列，这一列的内容是 QQ 号，一共 40 亿行。
- 请问这个文档有多大？
- 如果是一个40亿行的 txt 文档呢？
- 请设计算法对 QQ 号码去重，相同的 QQ 号码仅保留一个，内存限制为 1G。
问题一
第一个问题其实是有坑的，Excel 是没办法存下这么大数据的，题面就是错的：
07 之前版本的 Excel 单 Sheet 最多可以有 65536 行，即 2^16
07 之后的版本单 Sheet 最多可以有 1048576 行，即 2^20
40 亿行在最新版 Excel 下需要 3815 个 Sheet 才放得下。
问题二
第二个问题，如果是 txt 文档，那文件大小和编码有关，UTF8 和 ASCII 在内容只有数字的情况下占用是一致的，每个数字八位二进制，按照现在的 QQ 号长度，每个 QQ 号最长为 11 位，最低 5 位，那么，
如果是 LF 换行编码，则大小为
$(5+1) * 2 * 4,000,000,000 <= x <= (11 + 1) * 2 * 4,000,000,000$
44.7 GB ~ 89.4 GB
如果是 CRLF 换行编码，则为
$(5+2) * 2 * 4,000,000,000 <= x <= (11 + 2) * 2 * 4,000,000,000$
52.2 GB ~ 96.9 GB
问题三
根据上个问题，这个文档最大为 100 GB 级别，限制内存为 1GB 的情况下，全部读取到内存再操作当然不可能实现，网传的正确的思路为使用 BitMap，参考这篇文章 腾讯三面：40 亿个 QQ 号码如何去重？。BitMap 的确是最为妥当的方法，但是依然存在一些问题。
字典？不行…
$2^{32} -1 = 4,294,967,295$
$\frac{1GB}{4B} = 2^{30-2} = 2^{28} = 268,435,456$
根据第一个算式，如果采用<uint32,bit>字典标记，使用无符号32位数字作为 Key，那 QQ 号的范围只能 <= 4,294,967,295 。
在这个情况下，根据第二个算式，先不考虑 value 的那一个 bit，光考虑 key，1GB 内存也只能存得下 268,435,456 个 key。
所以即使是使用 BitMap，在只有 1GB 内存的情况下，根据当前 QQ 的实际规格，也很难成立，故而只在内存中处理时，完全不够保存 key。
BitMap？一样不够
$\frac{1GB}{1bit} = 2^{33} = 8,589,934,592$
既然存不下 key，那么就只能不对 key 做储存，直接用 BitMap，优点是极大的节省了内存，缺点也有，就是最终必然得对全部数据做一次遍历。
在这种情况下，整个 BitMap 作为一个大的 bit 数组，数组下标就是 key，最大能标记的 QQ 号就是数组的长度。
根据以上算式，1GB 内存完全用来储存字节数组，一共可以建立一个长度为 8,589,934,592 的数组，即使不考虑这个长度超过了uint32最大值的数组带来的额外问题，在当下最多 11 位 QQ 号的情况下，这个十位数依然是略有不足。
结论
目前看来，在符合实际QQ号规范且完全不做限制的情况下使用BitMap也大概率无法在1G内存下解决40亿QQ的去重问题。
猜测题面缺少一些条件，当然也有可能是故意这样以测试候选人的反应，合理的补充条件是，对 QQ 号的位数做限制。
