Google 2016 面试题  去除文件中的重复行

Removeduplicatelinesofafile.Whatifthefileisverylargewhichcouldnotbeheldinthemainmemory?...

(点击上方关注九章算法，获取最新IT求职干货！)

题目Question

Remove duplicate lines of a file.

What if the file is very large which could not be held in the main memory?

解答Solution

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好了，没有太多可以讨论的。

Google 2016 面试题 & 解答：点击可阅读

Google 2016 面试题8 | 吹气球

Google 2016 面试题7 | 翻转游戏(Flip Game II)

Google 2016 面试题6 | 数组计数

Google 2016 面试题5 | 岛屿计数2

Google 2016 面试题4 | 矩阵中的最长上升路径

Google 2016 面试题3 | 摆动排序 II

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题1 | 数组补丁

关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等

也可回复“干货”，获取薪资、冷冻期、techblog、简历修改等相关资讯。

简介九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。

目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。

目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。

更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.

    关注 九章算法