33,010
社区成员
发帖
与我相关
我的任务
分享[面试题][急等]大文件重复行问题
有一个文件长度大如16G的文件，每行都是16个大写字母组成的乱序字符串，总共有多少行不知道，文件内容太大不能全部读入内存，只能一次读入一部分，要判断文件中哪些行是一样的，输出重复的行是哪些。
这个问题有些东西是我们能看得清楚的：
1、必须用O(N)的时间长度去顺序读取文件。
2、不能用O(N)的空间的内存，不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。
3、不能修改文件、创建文件。
4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。
这个问题有些东西是我们能看得清楚的：
1、必须用O(N)的时间长度去顺序读取文件。
2、不能用O(N)的空间的内存，不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。
3、不能修改文件、创建文件。
4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。
...全文
请发表友善的回复…
发表回复
FancyMouse 2012-08-11
- 打赏
- 举报
26^16这么大。安心hash了。
HimeTale 2012-08-10
- 打赏
- 举报
按开头字母分到16个文件中
HimeTale 2012-08-10
- 打赏
- 举报
排序分治啊
分到能装进内存为止。
分到能装进内存为止。
titer1 2012-08-10
- 打赏
- 举报
[Quote=引用 1 楼 的回复:]
16个大写字母组成的乱序字符串 = 2^(4*26) 用bit存状态, 2^(4*26)/8 = 2^26 byte, 即64M。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。
[/Quote]
++
原以为题是 topK,细看是输出重复的，
位图放在这里不为过。
就是这样。
不过，这里 2^(4*26) 用bit存状态 没有看懂。
16个大写字母组成的乱序字符串 = 2^(4*26) 用bit存状态, 2^(4*26)/8 = 2^26 byte, 即64M。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。
[/Quote]
++
原以为题是 topK,细看是输出重复的，
位图放在这里不为过。
就是这样。
不过，这里 2^(4*26) 用bit存状态 没有看懂。
titer1 2012-08-10
- 打赏
- 举报
2、不能用O(N)的空间的内存，
不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。
问一下：这个意思说树就不能用了。对了大内存的数据结构 大于o(n)可以吗
4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。
问一下：能解释下，何种双重循环？
不论是文件数据、哈希表、哈夫曼编码，还是平衡二叉树。
问一下：这个意思说树就不能用了。对了大内存的数据结构 大于o(n)可以吗
4、存在一种简单的方法，双重循环，O(N2)，但是人家希望找到更好的方法。
问一下：能解释下，何种双重循环？
HeLiang7 2012-08-10
- 打赏
- 举报
16个大写字母组成的乱序字符串 = 2^(4*26) 用bit存状态, 2^(4*26)/8 = 2^26 byte, 即64M。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。
用自然顺序，每读取一个，如果对应位置没有改变，则改变对应位置的bit状态，否则重复，输出之。
