9、1000 万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
这题用 trie 树比较合适，hash_map 也应该能行。
10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析。
这题是考虑时间效率。用 trie 树统计每个词出现的次数，时间复杂度是 O(n le)（le 表示单词的平准长度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是 O(nlg10)。所以总的时间复杂度，是 O(n le) 与 O(nlg10) 中较大的哪一个。
11、一个文本文件，找出前 10 个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。
首先根据用 hash 并求模，将文件分解为多个小文件，对于单个文件利用上题的方法求出每个文件件中 10 个最常出现的词。然后再进行归并处理，找出最终的 10 个最常出现的词。
12、100w 个数中找出最大的 100 个数。
方案 1： 在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为 O(100w lg100)。
方案 2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w100)。
方案 3： 采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，知道扫描了所有的元素。复杂度为 O(100w 100)。
13、寻找热门查询：
搜索引擎 会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是 1 千万，但是如果去除重复和，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。
(1) 请描述你解决这个问题的思路；
(2) 请给出主要的处理流程，算法，以及算法的复杂度。
采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 10 个元素的最小推来对出现频率进行排序。
14、一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N) 个数并对它们操作。如何找到 个数中的中数？
方案 1： 先大体估计一下这些数的范围，比如这里假设这些数都是 32 位无符号整数（共有 个）。我们把 0 到 的整数划分为 N 个范围段，每个段包含 个整数。比如，第一个段位 0 到 ，第二段为 到 ，…，第 N 个段为 到 。然后，扫描每个机器上的 N 个数，把属于第一个区段的数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第 N 个区段的数放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N) 的。下面我们依次统计每个机器上数的个数，一次累加，直到找到第 k 个机器，在该机器上累加的数大于或等于 ，而在第 k-1 个机器上的累加数小于 ，并把这个数记为 x。那么我们要找的中位数在第 k 个机器中，排在第 位。然后我们对第 k 个机器的数排序，并找出第 个数，即为所求的中位数。复杂度是 的。
方案 2： 先对每台机器上的数进行排序。排好序后，我们采用归并排序的思想，将这 N 个机器上的数归并起来得到最终的排序。找到第 个便是所求。复杂度是 的。
15、最大间隙问题。
给定 n 个实数 ，求着 n 个实数在实轴上向量 2 个数之间的最大差值，要求线性的时间算法。
最先想到的方法就是先对这 n 个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：
1) 找到 n 个数据中最大和最小数据 max 和 min。
2)用 n-2 个点等分区间 [min,max]，即将[min, max] 等分为 n-1 个区间（前闭后开区间），将这些区间看作桶，编号为 ，且桶 的上界和桶 i+1 的下届相同，即每个桶的大小相同。每个桶的大小为： 。实际上，这些桶的边界构成了一个等差数列（首项为 min，公差为 ），且认为将 min 放入第一个桶，将 max 放入第 n-1 个桶。
3) 将 n 个数放入 n-1 个桶中：将每个元素 分配到某个桶（编号为 index），其中 ，并求出分到每个桶的最大最小数据。
4) 最大间隙：除最大最小数据 max 和 min 以外的 n-2 个数据放入 n-1 个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶（即便好在该连个便好之间的桶）一定是空桶。也就是说，最大间隙在桶 i 的上界和桶 j 的下界之间产生 ，一遍扫描即可完成。
16、将多个集合合并成没有交集的集合：给定一个字符串的集合，格式如：
。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出 。
(1) 请描述你解决这个问题的思路；
(2) 给出主要的处理流程，算法，以及算法的复杂度；
(3) 请描述可能的改进。
采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于 ，首先查看 aaa 和 bbb 是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看 bbb 和 ccc 是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是 O(NlgN) 的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。
17、最大子序列与最大子矩阵问题
数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。
方案 1： 这个问题可以动态规划的思想解决。设 表示以第 i 个元素 结尾的最大子序列，那么显然 。基于这一点可以很快用代码实现。最大子矩阵问题：给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。
方案 2： 可以采用与最大子序列类似的思想来解决。如果我们确定了选择第 i 列和第 j 列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第 i 列和第 j 列可以词用暴搜的方法进行。
标签： 间隙、并查、扫描、复杂度、集合、面试
