首页 文章

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

提问于
浏览 次
13

这是一个面试问题：

有10亿个手机号码，有11个数字，它们随机存储在一个文件中，例如12345678910，第一个数字必须是1.通过这些数字查看是否有一个有重复，只看看是否有重复存在，如果找到重复，则返回True，或返回False . 只允许10 MB内存 .

这是我的解决方案：

使用 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 作为哈希表 .

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

谢谢 .

FOLLOW UP:

如果这10亿个电话号码中没有重复项，给定一个电话号码，如何查找给定的电话号码是否在这10亿个号码中？使用尽可能少的内存 .

我想出了两个解决方案，

  • 电话号码可以使用5B表示，如上所述，扫描文件，一次读取一个数字， xor the given number with the one read from the file ，如果结果是 0 ，那么给定的一个在文件中，它将需要 O(n) 时间，对？

  • Partition 这些数字到 2 small files 根据 leading bit ，这意味着，这些数字与 leading 1-bit 去到一个文件中， leading 0-bit 去到另一个文件，同时指望有多少数量的每一个文件，如果给定数落入1位文件根据 secondary leading-bit ，1位文件的 count 是 not full ，然后 again partition 是1位文件，并递归检查给定的数字;如果1位文件 is full ，那么给定的数字必须在文件中，它将需要 O(logn) 时间，对吧？

algorithm large-data

6 回答

  • 2

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

    # 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）是否满足内存使用约束，例如：

    回复于
  • 0

    散列后，我得到了1000个小文件，每个文件最多包含100万个数字，对

    不是这样，在极端情况下，一个文件可能包含所有数字 .

    根据数字的第一个或最后一个x位创建文件（忽略起始1） . 创建这些文件时，您实际上可以将这些数字切掉，因为它们在文件中是相同的 . 这比哈希要好得多，因为虽然所有数字仍然可以在一个文件中结束，但现在这些数字的范围是有限的，所以你可以将它装入10MB .

    每个数字都可以通过一个简单的位来表示，因为您需要的唯一信息是先前是否出现过这个数字 . 您不必存储实际数字，该位的地址是数字 . 在10MB中你可以存储80M位，所以你需要1G / 80M = 12.5个文件，但请记住，这些数字必须不同，所以实际上你需要100个文件（x = 2） .

    最后，您不必创建这些文件，也可以多次扫描整个文件 . 在这种情况下，您可以在内存中有多个位图，因为一个不占用10MB .

    我强烈建议您阅读本书，它以一个几乎相同的例子开头：http://www.amazon.co.uk/Programming-Pearls-ACM-Press-Bentley/dp/0201657880

    回复于
  • 0

    不需要散列，10M = 83886080位，将每个数字放入[0,83886080]，[83886080,83886080 * 2] ...... [xx，9999999999）（不考虑第一位数字），约999999999/83886080 = 120文件，然后构建 bit set ，它完全需要O（n） .

    回复于
  • 8

    您可以遵循bitset技术 . 请参阅此问题和答案：Find an integer not among four billion given ones

    回复于
  • 14

    面试问题仅限制使用的记忆，而不是提供答案所需的时间 .

    因此，如此实施这个问题是合理的：

    take the first number
compare it to all numbers following it
take the second number
compare it to all numbers following it
...

    这需要花费大量时间来处理十亿个数字（O（n ^ 2）），但不会占用超过10MB的内存空间 .

    回复于
  • 5

    您可以使用包含m的Bloom过滤器位数组并使用k个散列函数 . 虽然我不确定您可能需要多少哈希函数 .

    回复于

相关问题