doc/面经/问答/智力问题.md

香问题

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

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

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

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

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

取出三条绳子。

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

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

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

大数问题

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

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

1. 如何在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（常数）。