在文件中找到两行相同的行

Question

我在亚马逊的采访中被问到这个问题.

你有一个包含许多行的文件,但其中两行是相同的.找到这两行.我给出了在N ^ 2时间内运行的明显答案.然后我想出了一个使用哈希表的答案,但是他们不喜欢这个答案,因为他们说如果文件是千兆字节就不行.我想出的另一个答案是,不是将哈希结果存储在内存中,而是创建一个与哈希值同名的文件,并在文件中存储具有相同哈希值的行.要么他们无法理解我的解决方案,要么他们不喜欢它.

有什么想法吗？

谢谢

Answer 1

我可以想到解决这个问题的两类基本解决方案：

1. 概率内存解决方案。 您可以尝试通过在主内存中存储文件行的摘要来解决此问题。然后，您可以在主内存中进行计算以识别可能的重复项，然后通过查看磁盘来检查每个可能的重复项。这些解决方案可能是最好的，因为它们内存使用率低、效率高并且最大限度地减少磁盘访问。此类别中的解决方案包括

   1. 计算文件每一行的哈希值，然后存储哈希值。任何具有哈希冲突的行都代表可能发生冲突的一对可能的行，并且只能探索这些行。
   2. 使用布隆过滤器存储文件的所有行，然后仅检查在布隆过滤器中发生冲突的行。这本质上是 (1) 的变体，更节省空间。

2. 确定性磁盘解决方案。您可以尝试使用磁盘上的整个数据集进行计算，使用主内存作为临时暂存空间。这可以让您获得准确的答案，而不必将整个文件保存在内存中，但可能会比较慢，除非您要进行一些后续处理并且可以从重组数据中受益。此类别中的解决方案包括

   1. 使用外部排序算法（外部快速排序、外基数排序等）对文件进行排序，然后线性搜索一对重复元素。
   2. 构建一个磁盘数据结构，例如保存所有字符串的 B 树，然后查询 B 树。这需要大量的预处理时间，但会使以后对文件的操作速度更快。
   3. 将所有内容放入数据库并查询数据库。

希望这可以帮助！