algorithm - 检查 10 亿个手机号码是否重复

Question

这是一道面试题:

There are 1 billion cell-phone numbers which has 11 digits, they are stored randomly in a file, for example 12345678910, the first digit gotta be 1. Go through these numbers to see whether there is one with duplicate, just see if duplicate exists, if duplicate found, return True, or return False. Only 10 MB memory allowed.

这是我的解决方案:

使用 hash(num)%1000 将所有这些数字散列到 1000 个文件中，然后重复项应落入同一个文件中。

散列之后，我得到了1000个小文件，每个文件都包含 1 million 数字 at most ，对吧？我不确定这一点，我只是这样做 1 billion / 1000 = 1 million 。

然后为每个文件建立一个哈希表来存储每个数字和一个表示它出现的 flag。

我猜，会用5 B来表示数字，4 B代表下层的8 digits，1 B代表上层的3 digits；实际上 1 bit 就足够了 flag ，因为我只需要找出重复项是否存在，只需要多少次。但是我怎样才能将 1 bit 标志应用到每个数字呢？我迷路了，所以我选择bool作为标志，1 B被拿走了。 所以最后，哈希表中的每个数字都会取 5B<for number> + 1B<for flag> + 4B<for the next-pointer> = 10B ，然后每个文件都会为哈希表取 10M 。

这是我的愚蠢解决方案，请给我一个更好的解决方案。

谢谢。

跟进:

If there are no duplicates in these 1 billion phone numbers, given one phone number, how to find out the given one is or is not in these 1 billion numbers? Use as few memory as possible.

我想出了两个解决方案，

1. 电话号码可以用我上面说的 5B 表示，扫描文件，一次读取一个数字，然后 xor the given number with the one read from the file ，如果结果是 0 ，那么给定的一个在文件中，它'会花 O(n) 时间，对吧？

2. Partition 根据2 small files将这些数字编码成leading bit，也就是说，带leading 1-bit的数字进入一个文件，leading 0-bit进入另一个文件，同时统计每个文件中有多少个数字，如果给定的数字落入1-bit文件，1-bit文件的count为not full，然后根据again partition对1-bit文件进行secondary leading-bit，递归校验给定的数；如果 1 位文件 is full ，那么给定的数字必须在文件中，它会花费 O(logn) 时间，对吧？

Answer 1

最快的解决方案(也是在程序员开销方面:)

# Generate some 'phones'
yes 1 | perl -wne 'chomp; ++$a; print $_."$a\n";' > phones.txt

# Split phones.txt in 10MB chunks
split -C 10000000 phones.txt

# Sort each 10MB chunk with 10MB of memory
for i in x??; do sort -S 10M $i > $i.srt; echo -ne "$i.srt\0" >> merge.txt; done

# Merge the shorted chunks with 10MB of memory
sort -S 10M --files0-from=merge.txt -m > sorted.txt

# See if there is any duplicates
test -z $(uniq -d merge.txt)

例如使用 pmap $(pidof sort) 检查内存使用限制是否满足: