Google 2016 面试题 | 去除文件中的重复行
Remove duplicate lines of a file.
What if the file is very large which could not be held in the main memory?
Read full article from Google 2016 面试题 | 去除文件中的重复行
Remove duplicate lines of a file.
What if the file is very large which could not be held in the main memory?
New Grad Level 解法: 用HashMap，每行都放进HashMap。就能找出不重复的行。缺点是内存放不下。
Entry Level 解法: 先把文件Split成若干个小文件。Split的方法是，对每一行的字符串算一个hashcode然后对n取%来选择放到哪个文件里。n取决于内存大小和文件大小之间的比例。缺点是可能存在某个子文件特别大。因为%n之后未必均匀分布。
Senior Level 解法: 采用类似外排序的思路，先顺序遍历文件，把每一行放到HashMap里，如果发现内存快满了，就把HashMap导出到Disk上，形成一个文件，然后继续重复上述操作。这样得到的文件的个数是有限，接着再通过Entry Level的方法，按照hashcode % n的方法Split这若干个文件，把 %n 相同的放在一个文件内，每个文件单独进行去重，然后再归并到一起。
另外还有一些可行的方法是，不用HashMap用BloomFilter，你可以认为BloomFilter是一种省内存的HashMap，但是可能会造成False Positive。这种方法面试官即便认可但是也还会让你继续设计上面提到的方法，因为这种方法毕竟是有缺陷的。但是实际操作的时候，如果内存和文件大小差距不是特别大的话，BF是一个很好的解决方案。
以上答案基于单机的情况，如果是多机的话，直接Map Reduce好了，没有太多可以讨论的。
