## 香问题

1. 两根可以烧一小时的香, 如何确定15分钟时间？

第一根香点燃一端，
第二根香点燃两端。
当第二根香燃尽时，过去了半小时，因此第一根香总长度剩下半小时。
此时若点燃第一根香的两端，直到燃尽就是15分钟了。

2. 一根可以烧一小时的香, 如何确定15分钟时间

点燃香的两端，同时任意点燃香中间的一个点（此时香会变成长度不等的两段，没关系），
这样可以使得香以四倍速度燃烧，
在短的一段燃尽的瞬间，再在另一段中间随便点燃一个点，使得香保持四倍燃烧速度即可。
香全部燃尽时就是15分钟。

3. 三根不均匀的绳子，全部烧完需要1个小时，问怎样烧能计时1个小时15分钟

1、同时点燃“第一根的两头”和“第二根的一头”，第一根烧完时间过了“30分钟”；

2、第一根烧完后马上点燃第二根的另一头，到第二根烧完时间又过了“15分钟”；

3、第二根烧完后马上点燃第三根绳子的两头，当第三根烧完时间又用了“30分钟”。加起来总共=30+15+30=75分钟=一个小时十五分钟。

4. 两个不均匀的绳子，全部烧完需要1个小时，问怎样烧能计时1个小时15分钟

1、同时点燃“第一根的两头”和“第二根的一头”，第一根烧完时间过了“30分钟”；

2、第一根烧完后马上点燃第二根的另一头，到第二根烧完时间又过了“15分钟”；

## 大数问题

1. 在100G文件中找出出现次数最多的100个IP

针对top k类问题，通常比较好的方案是【分治+trie树/[hash](https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020)+小顶堆】，即先将数据集按照hash方法分解成多个小数据集，然后使用trie树或者hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出频率最高的前K个数，最后在所有top K中求出最终的top K。

2. 如何在1亿个数中找出最大的100个数（top K问题）

**第一种方法**：直接排序，放弃

 **第二种方法为局部淘汰法**，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。

 **第三种方法是分治法**，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB，一共需要101次这样的比较。*

 **第四种方法是Hash法**。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。

 **第五种方法采用最小堆**。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。

## 给定100亿个无符号的乱序的整数序列，如何求出这100亿个数的中位数（中位数指的是排序后最中间那个数），内存只有**512M**。

中位数问题可以看做一个统计问题，而不是排序问题，无符号整数大小为4B，则能表示的数的范围为为0 ~ 2^32 - 1（40亿），如果没有限制内存大小，则可以用一个2^32（4GB）大小的数组（也叫做桶）来保存100亿个数中每个无符号数出现的次数。遍历这100亿个数，当元素值等于桶元素索引时，桶元素的值加1。当统计完100亿个数以后，则从索引为0的值开始累加桶的元素值，当累加值等于50亿时，这个值对应的索引为中位数。时间复杂度为O(n)。

但是由于内存只有512M，所以上述方法不合适。

如果100亿个数字保存在一个大文件中，可以依次读一部分文件到内存(不超过内存限制)，将每个数字用二进制表示，比较二进制的最高位(第32位，符号位，0是正，1是负)。

如果数字的最高位为0，则将这个数字写入 file_0文件中；如果最高位为 1，则将该数字写入file_1文件中。 从而将100亿个数字分成了两个文件。

假设 file_0文件中有 60亿 个数字，file_1文件中有 40亿 个数字。那么中位数就在 file_0 文件中，并且是 file_0 文件中所有数字排序之后的第 10亿 个数字。因为file_1中的数都是负数，file_0中的数都是正数，也即这里一共只有40亿个负数，那么排序之后的第50亿个数一定位于file_0中。

现在，我们只需要处理 file_0 文件了，不需要再考虑file_1文件。对于 file_0 文件，同样采取上面的措施处理：将file_0文件依次读一部分到内存(不超过内存限制)，将每个数字用二进制表示，比较二进制的 次高位（第31位），如果数字的次高位为0，写入file_0_0文件中；如果次高位为1，写入file_0_1文件 中。

现假设 file_0_0文件中有30亿个数字，file_0_1中也有30亿个数字，则中位数就是：file_0_0文件中的数字从小到大排序之后的第10亿个数字。

抛弃file_0_1文件，继续对 file_0_0文件 根据 次次高位(第30位) 划分，假设此次划分的两个文件为：file_0_0_0中有5亿个数字，file_0_0_1中有25亿个数字，那么中位数就是 file_0_0_1文件中的所有数字排序之后的 第 5亿 个数。

按照上述思路，直到划分的文件可直接加载进内存时，就可以直接对数字进行快速排序，找出中位数了。

## 统计不同号码的个数

## 题目描述

**已知某个文件内包含大量电话号码，每个号码为8位数字，如何统计不同号码的个数？内存限制100M**

## 思路分析

这类题目其实是求解数据重复的问题。对于这类问题，可以使用**位图法**处理

8位电话号码可以表示的范围为00000000～99999999。如果用 bit表示一个号码，那么总共需要1亿个bit，总共需要大约**10MB**的内存。

申请一个位图并初始化为0，然后遍历所有电话号码，**把遍历到的电话号码对应的位图中的bit设置为1**。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。

最后这个**位图中bit值为1的数量**就是不同电话号码的个数了。

那么如何确定电话号码对应的是位图中的哪一位呢？

可以使用下面的方法来做**电话号码和位图的映射**。

```java
00000000 对应位图最后一位：0×0000…000001。
00000001 对应位图倒数第二位：0×0000…0000010（1 向左移 1 位）。
00000002 对应位图倒数第三位：0×0000…0000100（1 向左移 2 位）。
……
00000012 对应位图的倒数第十三位：0×0000…0001 0000 0000 0000（1 向左移 12 位）。
```

也就是说，电话号码就是1这个数字左移的次数。

## 出现频率最高的100个词

### 题目描述

假如有一个**1G**大小的文件，文件里每一行是一个词，每个词的大小不超过**16byte**，要求返回出现频率最高的100个词。内存大小限制是**10M**

### 解法1

由于内存限制，我们无法直接将大文件的所有词一次性读到内存中。

可以采用**分治策略**，把一个大文件分解成多个小文件，保证每个文件的大小小于10M，进而直接将单个小文件读取到内存中进行处理。

**第一步**，首先遍历大文件，对遍历到的每个词x，执行 `hash(x) % 500`，将结果为i的词存放到文件f(i)中，遍历结束后，可以得到500个小文件，每个小文件的大小为2M左右；

**第二步**，接着统计每个小文件中出现频数最高的100个词。可以使用HashMap来实现，其中key为词，value为该词出现的频率。

对于遍历到的词x，如果在map中不存在，则执行 `map.put(x, 1)。`

若存在，则执行 `map.put(x, map.get(x)+1)`，将该词出现的次数加1。

**第三步**，在第二步中找出了每个文件出现频率最高的100个词之后，通过维护一个**小顶堆**来找出所有小文件中出现频率最高的100个词。

具体方法是，遍历第一个文件，把第一个文件中出现频率最高的100个词构建成一个小顶堆。

如果第一个文件中词的个数小于100，可以继续遍历第二个文件，直到构建好有100个结点的小顶堆为止。

继续遍历其他小文件，如果遍历到的词的出现次数大于堆顶上词的出现次数，可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。

当遍历完所有小文件后，这个小顶堆中的词就是出现频率最高的100个词。

总结一下，这种解法的主要思路如下：

1. 采用**分治**的思想，进行哈希取余
2. 使用**HashMap**统计每个小文件单词出现的次数
3. 使用**小顶堆**，遍历步骤2中的小文件，找出词频top100的单词

但是很容易可以发现问题，在第二步中，如果这个1G的大文件中有某个词词频过高，可能导致小文件大小超过10m。这种情况下该怎么处理呢？

接下来看另外一种解法。

### 解法2

**第一步**：

使用多路归并排序对大文件进行排序，这样相同的单词肯定是紧挨着的

多路归并排序对大文件进行排序的步骤如下：

① 将文件按照顺序切分成大小不超过2m的小文件，总共500个小文件

② 使用10MB内存**分别**对 500 个小文件中的单词进行**排序**

③ 使用一个大小为500大小的堆，对500个小文件进行**多路排序**，结果写到一个大文件中

其中第三步，对500个小文件进行多路排序的思路如下：

- 初始化一个最小堆，大小就是有序小文件的个数500。堆中的每个节点存放每个有序小文件对应的输入流。
- 按照每个有序文件中的下一行数据对所有文件输入流进行排序，单词小的输入文件流放在堆顶。
- 拿出堆顶的输入流，并其下一行数据写入到最终排序的文件中，如果拿出来的输入流中还有数据的话，那么将这个输入流再一次添加到栈中。否则说明该文件输入流中没有数据了，那么可以关闭这个流。
- 循环这个过程，直到所有文件输入流都没有数据为止。

**第二步**：

① 初始化一个100个节点的**小顶堆**，用于保存100个出现频率最多的单词

② 遍历整个文件，一个单词一个单词的从文件中取出来，并计数

③ 等到遍历的单词和上一个单词不同的话，那么上一个单词及其频率如果大于堆顶的词的频率，那么放在堆中，否则不放

最终，小顶堆中就是出现频率前100的单词了。

解法2相对解法1，更加严谨，如果某个词词频过高或者整个文件都是同一个词的话，解法1不适用。

## 查找两个大文件共同的URL

### 题目

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

### 分析

每个 URL 占 64B，那么 50 亿个 URL占用的空间大小约为 320GB。

5,000,000,000 * 64B ≈ 320GB

由于内存大小只有 4G，因此，不可能一次性把所有 URL 加载到内存中处理。

可以采用分治策略，也就是把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。

首先遍历文件a，对遍历到的 URL 进行哈希取余 `hash(URL) % 1000`，根据计算结果把遍历到的 URL 存储到 a0, a1,a2, ..., a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, ..., a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( `i∈[0,999]`)，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

## 如何找出排名前 500 的数？

### 题目描述

有 1w 个数组，每个数组有 500 个元素，并且有序排列。如何在这 10000*500 个数中找出前 500 的数？

### 分析

* 方法一：

对于这种topk问题，更常用的方法是使用**堆排序**。

对本题而言，假设数组降序排列，可以采用以下方法：

首先建立大顶堆，堆的大小为数组的个数，即为10000 ，把每个数组最大的值存到堆中。

接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。

重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。

* 方法二

类似map/reduce，找出10台机器上top500，然后再top500，可以使用快排序，堆排序

* 方法三

如果全是正数，使用bit数组，统计下标+1，最后计算count == 500

## 50万个TCP一台机器能否保证

通过以下几个方面分析

1. 能否使用nginx代理
2. 能否使用多个网卡
3. 文件描述符大小更改
4. 内存大小更改
5. 磁盘空间更改
6. 最大的流量