algorithm - 存储千电话号码的最有效方法

Question

这是一个谷歌面试问题:

要存储大约一千个电话号码，每个号码有 10 位数字。您可以假设每个数字的前 5 位在千位数字中是相同的。您必须执行以下操作:A。搜索给定号码是否存在。b.打印所有数字

执行此操作最有效的节省空间的方法是什么？

我回答了哈希表和后来的哈夫曼编码，但我的面试官说我没有朝着正确的方向前进。请在这里帮助我。

使用后缀 trie 有帮助吗？

理想情况下，存储 1000 个数字每个数字需要 4 个字节，因此总共需要 4000 个字节来存储 1000 个数字。从数量上讲，我希望将存储减少到 < 4000 字节，这是我的面试官向我解释的。

Answer 1

在下文中，我将数字视为整数变量(而不是字符串):

1. 对数字进行排序。
2. 将每个数字分成前五位和后五位。
3. 前五位数字在不同数字中是相同的，因此只存储一次。这将需要 17 位存储空间。
4. 分别存储每个数字的最后五位数字。这将需要每个数字 17 位。

回顾一下:前17位是公共(public)前缀，后面的1000组17位是每个数字的后五位，按升序存储。

我们总共查看 1000 个号码的 2128 字节，或者每个 10 位电话号码 17.017 位。

搜索是 O(log n)(二进制搜索)，完整枚举是 O(n)。