最有效的方式来存储一千个电话号码
这是一个谷歌面试问题：
有大约一千个电话号码被存储，每个有10个数字。 你可以假设每个数字的前5位数字是相同的。 您必须执行以下操作：a。 search给定的号码是否存在。 湾 打印所有的号码
什么是最有效的节省空间的方式来做到这一点？
我回答了哈希表和后来的哈夫曼编码，但是我的采访者说我没有正确的方向。 请帮我这里。
可以使用后缀特里助理？
理想情况下，存储1000个数字需要每个数字4个字节，因此总共需要4000个字节来存储1000个数字。 在数量上，我希望将存储空间减less到<4000字节，这就是我的采访者向我解释的。
这是对艾克斯答案的一个改进。 考虑使用三个“层”作为数据结构：第一个是前五个数字（17位）的常量; 所以从这里开始，每个电话号码只剩下剩余的五位数字。 我们将剩下的5位数字视为17位二进制整数，并使用一种方法存储k位这些位，用不同的方法存储17位k = m ，最后确定k以最小化所需的空间。
我们首先对电话号码进行sorting（全部缩减为5个十进制数字）。 然后我们计算出有多less电话号码，其中前m位的二进制数全部为0，前m位最多为0 … 01的电话号码，第一个m的电话号码位最多为0 … 10，等等，前m位为1 … 11 – 最后一个计数为1000（十进制）的电话号码数。 如果我们省略最后一个（因为我们知道它是1000），我们可以将这些数字全部存储在（2 ^ m -1）个连续的块中， * 10位。 （10位足以存储小于1024的数字）。
所有（缩小的）电话号码的最后k位连续地存储在存储器中; 所以如果k是7，那么这块存储器的前7位（0到6位）对应于第一个（减less的）电话号码的最后7位，第7到13位对应于最后的7位（减less的）电话号码等等。 这需要1000 * k比特，总共为17 +（2 ^（17- k ）-1）* 10 + 1000 * k ，当k = 10时达到其最小值11287。因此，我们可以将所有电话号码存储在ceil 11287/8）= 1411字节。
通过观察我们所有的数字都不能以1111111（二进制）开始，因为最小的数字以130048开头，我们只有五位小数位，所以可以节省额外的空间。 这使我们可以从第一块内存刮掉一些内存：而不是2 ^ m -1计数，我们只需要ceil（99999/2 ^ k ）。 这意味着公式就变成了
17 + ceil（99999/2 ^ k ）* 10 + 1000 * k
对于k = 9和k = 10，或者ceil（10997/8）= 1375个字节，这足够惊人地达到其最小值10997。
如果我们想知道某个电话号码是否在我们的设置中，我们首先检查前五位二进制数字是否与我们存储的五位数字匹配。 然后我们将剩下的五位数字分割成最高的m = 7位（也就是m位数M ）和较低的k = 10位（数字K ）。 我们现在find前m位至多为M-1的缩小电话号码的号码[M-1]和前m位至多为M的缩位电话号码的号码a [M]从第一块比特。 我们现在检查第二块存储器中的第[M-1]和第[M]个k位序列，看看我们是否findK ; 在最坏的情况下，有1000个这样的序列，所以如果我们使用二进制search，我们可以完成O（log 1000）操作。
伪代码用于打印全部1000个数字，其中我访问第一个存储器块的第K个第k位条目作为[K]，第二个存储器块的第M个第m个位条目作为b [M] （这两个操作都需要一些繁琐的操作）。 前五位数字在数字c 。
i := 0; for K from 0 to ceil(99999 / 2^k) do while i < a[K] do print(c * 10^5 + K * 2^k + b[i]); i := i + 1; end do; end do; 也许K = ceil（99999/2 ^ k ）的边界情况出了问题，但这很容易解决。
最后，从熵的angular度来看，不能存储小于10 ^ 5的10 ^ 3个正整数的子集（log [2]（二项式（10 ^ 5,10 ^ 3）） ）= 8073。包括前5位数字所需的17位，仍然有10997 – 8090 = 2907位的差距。 查看是否有更好的解决scheme，您仍然可以相对有效地访问数字，这是一个有趣的挑战！
在下面，我把数字看作整数variables（而不是string）：
- sorting数字。
- 将每个数字拆分成前五位数字和后五位数字。
- 前五位数字在数字上是相同的，所以只需存储一次。 这将需要17位的存储空间。
- 分别存储每个号码的最后五位数字。 这将需要每个数字17位。
回顾一下：前17位是通用前缀，随后的1000组17位是按升序存储的每个数字的最后5位。
总的来说，我们正在考虑1000个数字中的2128个字节，或者每个10位数字电话号码中的17.017个比特。
search是O(log n) （二进制search），完全枚举是O(n) 。
http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton
我曾经接受过一次关于数据结构的访问。 我忘了“arrays”。
我可能会考虑使用一些Trie的压缩版本（可能是由@Mishabuild议的DAWG ）。
这将自动利用这一事实，即他们都有一个共同的前缀。
search将在一定时间内执行，打印将以线性时间执行。
我之前听说过这个问题（但是没有前5位数字是相同的假设），最简单的方法就是赖斯编码 ：
1）由于顺序无关紧要，我们可以对它们进行sorting，并且只保存连续值之间的差异。 在我们的情况下，平均差异是100.000 / 1000 = 100
2）使用赖斯码（基128或64）甚至哥伦布码（基100）编码差异。
编辑：水稻编码基地128（不是因为它会给最好的结果，但因为它更容易计算）的估计：
我们将保存第一个值（32位）。
其余的999个值是不同的（我们预计它们很小，平均为100个）将包含：
一元值value / 128 （可变比特数+ 1比特作为终止符）
value % 128二进制值（7位）
我们必须以某种方式估计可变位数的限制（让我们称之为VBL ）：
下限：考虑到我们是幸运的，没有什么区别比我们的基础更大（在这种情况下是128）。 这将意味着给0个额外的位。
高限：因为所有小于基数的差值都将被编码成二进制数字部分，所以我们需要在一元中编码的最大数目是100000/128 = 781.25（甚至更less，因为我们并不期望大多数差异为零）。
所以，结果是32 + 999 *（1 + 7）+variables（0..782）位= 1003 +variables（0..98）字节。
这是宾利编程珍珠的一个很好的问题。
解决scheme：从数字中删除前五位数字，因为每个数字都相同。 然后使用按位操作来表示剩余的9999个可能的值。 你只需要2 ^ 17位来表示数字。 每个位代表一个数字。 如果该位被设置，则该号码在电话簿中。
要打印所有数字，只需打印所有与前缀连接的数字。 要search给定的数字，请执行必要的位运算来检查数字的按位表示。
您可以在O（1）中search一个数字，由于代表比特位，空间效率是最大的。
HTH克里斯。
为1,000个数字固定存储1073个字节：
这种存储方法的基本格式是存储前5位数，每个组的计数和每个组中每个数的偏移量。
字首：
我们的5位前缀占据了前17位 。
分组：
接下来，我们需要弄清楚数字的大小分组。 让我们尝试每组约1个数字。 由于我们知道有大约1000个数字要存储，所以我们将99999分为大约1000个部分。 如果我们select组大小为100，就会有浪费的比特，所以让我们尝试128组大小，可以用7比特来表示。 这给了我们782个小组。
计数：
接下来，对于782个组中的每个组，我们需要存储每个组中的条目数量。 每个组的7位计数将产生7*782=5,474 bits ，这是非常低效的，因为由于我们如何select我们的组，所表示的平均数是大约1。
因此，相反，我们有一个可变大小的计数，其中一个组中的每个数字都是前导1，然后是0.因此，如果我们在一个组中有x数字，那么我们将有x 1's和0代表计数。 例如，如果我们在一个组中有5个数字，则计数将由111110表示。 用这种方法，如果有1000个数字，我们最终得到1000个1和782个0，总计为1000 + 782 = 1782个比特 。
抵消：
最后，每个数字的格式将只是每个组的7位偏移量。 例如，如果00000和00001是0-127组中唯一的数字，则该组的位数将为110 0000000 0000001 。 假设有1,000个数字， 偏移量将会有7000个位 。
因此，我们假定1,000个数字的最终计数如下：
17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes
现在，我们来看看我们的组大小的select是通过舍入到128位来select组大小的最佳select。 selectx作为表示每个组的位数，大小公式为：
Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000
对x整数值最小化该公式给出x=6 ，这产生8,580位= 1,073字节 。 因此，我们理想的存储如下：
- 组大小：2 ^ 6 = 64
- 组数：1,562
-
总存储量：
1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes
以此作为一个纯粹的理论问题并留下实现的佐证，单一的最有效的方法就是在一个巨大的索引表中索引所有可能的10000个最后的数字集合。 假设你有1000个数字，你需要多于8000个比特来唯一标识当前组。 没有更大的压缩可能，因为那么你将有两个集合被识别为相同的状态。
问题在于，你将不得不在你的程序中将每个2 ^ 8000集合表示为一个lut，甚至谷歌也不能远程执行这个操作。
查找将是O（1），打印所有数字O（n）。 插入将是O（2 ^ 8000），这在理论上是O（1），但在实践中是不可用的。
在一次采访中，如果我确定的话，我只会给出这个答案，即公司正在寻找一个能够从盒子里思考的人。 否则，这可能会让你看起来像一个没有真正的世界关注的理论家。
编辑 ：好的，这是一个“实施”。
步骤来构build实施：
- 采取恒定的大小100 000 *（1000select100 000）位数组。 是的，我意识到这个arrays比宇宙中的primefaces需要更多的空间几个量级。
- 将这个大arrays分成10万个大块。
- 在每个块存储中为最后五位的一个特定组合的位数组。
这不是程序，而是一种元程序，它将构build一个现在可以在程序中使用的巨大的LUT。 在计算空间效率时，通常不会计算程序的常量，因此在进行最终计算时我们不关心这个数组。
这里是如何使用这个LUT：
- 当有人给你1000个号码，你分别存储前五位数字。
- 找出你的数组块中的哪一块匹配这个集合。
- 将该组号码存储在一个单一的8074位数字中（称为c）。
这意味着存储我们只需要8091位，我们已经certificate这里是最佳的编码。 然而，find正确的块需要O（100 000 *（100 000select1000）），根据math规则是O（1），但在实践中总是需要比宇宙时间更长的时间。
查找虽然简单，
- 前五位数字（剩下的数字将被称为n'）。
- testing它们是否匹配
- 计算i = c * 100000 + n'
- 检查LUT中我的位是否被设置为1
打印所有的数字也很简单（并且实际上需要O（100000）= O（1），因为你总是需要检查当前块的所有位，所以我错误地计算了这个）。
我不会把这称为“实现”，因为公然无视这个限制（这个宇宙的大小和时间，或者这个宇宙的存在时间）。 但理论上这是最佳的解决scheme。 对于较小的问题，这实际上可以完成，有时会完成。 例如， sortingnetworking就是这种编码方式的一个例子，可以作为recursionsortingalgorithm的最后一步，以获得大的加速。
这相当于存储每个小于10万的一千个非负整数。 我们可以使用像算术编码这样的东西。
最终，这些数字将被存储在一个sorting列表中。 我注意到列表中相邻数字之间的预期差异是100,000 / 1000 = 100，可以用7位表示。 还有很多情况下需要超过7位。 表示这些不太常见的情况的简单方法是采用utf-8scheme，其中一个字节表示7位整数，除非第一位被设置，在这种情况下读取下一个字节以产生14位整数，除非其第一位被设置，在这种情况下，下一个字节被读取以表示21位整数。
所以连续整数之间至less有一半的差值可以用一个字节来表示，其余几乎全部需要两个字节。 less数数字与16,384之间的差异较大，需要三个字节，但不能超过61个。 那么平均存储量将大约为每个数字12位，或者less一点，或者至多1500个字节。
这种方法的缺点是检查数字的存在现在是O（n）。 但是，没有规定时间复杂度要求。
写完之后，我注意到ruslik已经提出了上面的区别方法，唯一的区别就是编码scheme。 矿可能更简单，但效率较低。
只是为了快速询问任何我们不希望将数字改为基数的理由36.它可能不会节省太多的空间，但它肯定会节省search时间，因为您将会看到less于10d的数字。 或者我会根据每个组把它们分成文件。 所以我会命名一个文件（111）-222.txt，然后我只会存储适合该组的数字，然后让它们以数字顺序seearchable，这样我总是可以查看文件是否退出。 在我运行一个bigersearch之前。 或者是正确的，我会运行二进制search一个文件，看看它是否退出。 还有另外一个关于文件内容的Bonarysearch
为什么不保持简单？ 使用一个结构数组。
所以我们可以把前5位数字保存为一个常量，所以现在就忘记了。
65535是可以存储在16位数字中的最多的数字，最大可以是99999，最大可以是131071。
使用32位数据types是一种浪费，因为我们只需要1位额外的16位…因此，我们可以定义一个具有布尔（或字符）和16位数的结构。
假设C / C ++
typedef struct _number { uint16_t number; bool overflow; }Number;
这个结构只占用3个字节，我们需要1000个数组，所以3000个字节总数。 我们已经把总空间减less了25％！
至于存储的数字，我们可以做简单的按位math
overflow = (number5digits & 0x10000) >> 4; number = number5digits & 0x1111;
和逆
//Something like this should work number5digits = number | (overflow << 4);
要打印所有这些，我们可以在数组上使用一个简单的循环。 检索一个特定的数字发生在固定的时间当然，因为它是一个数组。
for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;
要search一个数字，我们需要一个sorting的数组。 所以当数字保存时，sorting数组（我会select个人合并sorting，O（nlogn））。 现在search，我会去一个合并sorting的方法。 拆分数组，看看我们的数字在哪一个之间。 然后只调用该数组上的函数。 recursion执行此操作直到您有一个匹配并返回索引，否则它不存在并打印一个错误代码。 这个search会很快，最差的情况比O（nlogn）还要好，因为它绝对会比合并sorting更less的执行时间（每次只是recursion分割的一边，而不是两边:)），是O（nlogn）。
我的解决scheme：最好的情况下7.025位/数，最坏的情况下14.193位/数，粗略平均8.551位/数。 stream编码，不随机访问。
即使在阅读ruslik的答案之前，我立即想到了编码每个数字之间的差异，因为它会很小，应该是相对一致的，但解决scheme也必须能够适应最坏的情况。 我们有一个包含1000个数字的100000个数字的空间。 在一个完全统一的电话簿中，每个数字将比以前的数字大100：
55555-12 3 45
55555-12 4 45
55555-12 5 45
如果是这样的话，它将需要零存储来编码数字之间的差异，因为这是一个已知的常数。 不幸的是，数字可能与100的理想步数有所不同。我将编码与100的理想增量的差值，以便如果两个相邻数字相差103，我将编码数字3，如果两个相邻数字相差92，I会编码-8。 我称之为“ 方差 ”的理想增量。
方差的范围可以从-99（即两个连续的数字）到99000（整个电话簿由数字00000 … 00999和最远的数字99999组成），这是99100个可能值的范围。
我的目标是分配一个最小的存储来编码最常见的差异，并扩大存储，如果我遇到更大的差异（如ProtoBuf的varint ）。 我将使用七位数据块，六位数据作为存储数据，另外还有一个额外的标志位表示这个数据在当前数据块之后存储了一个额外的数据块，最多可以存储三个数据块（最多可以提供三个数据块3 * 6 = 18位的存储空间，它是262144的可能值，大于可能的差异数量（99100）。每个附加的高位标志后面的块都有更高的位，所以第一个块总是有0-在图5中，可选的第二组块具有位6-11，并且可选的第三组块具有位12-17。
一个块提供了可以容纳64个值的六个存储位。 我想映射64个最小的差异，以适应单个块（即-32到+31的差异），所以我将使用ProtoBuf ZigZag编码，直到-99到+98的差异（因为没有必要对于超出-99的负方差），此时我将切换到常规编码，偏移98：
差异| 编码值
----------- + ----------------
0 | 0
-1 | 1
1 | 2
-2 | 3
2 | 4
-3 | 五
3 | 6
... | ...
-31 | 61
31 | 62
-32 | 63
----------- | --------------- 6位
32 | 64
-33 | 65
33 | 66
... | ...
-98 | 195
98 | 196
-99 | 197
----------- | ---------------锯齿结束
100 | 198
101 | 199
... | ...
3996 | 4094
3997 | 4095
----------- | --------------- 12位
3998 | 4096
3999 | 4097
... | ...
262045 | 262143
----------- | --------------- 18位
一些如何将差异编码为位的示例，包括用于指示附加块的标志：
差异| 编码位
----------- + ----------------
0 | 000000 0
5 | 001010 0
-8 | 001111 0
-32 | 111111 0
32 | 000000 1 000001 0
-99 | 000101 1 000011 0
177 | 010011 1 000100 0
14444 | 001110 1 100011 1 000011 0
因此，电话簿样本的前三个数字将被编码为如下的位stream：
BIN 000101001011001000100110010000011001 000110 1 010110 1 00001 0 PH＃55555-12345 55555-12448 55555-12491 POS 1 2 3
最好的情况下 ，电话簿有点均匀分布，并且没有两个电话号码的差异大于32，所以它将使用7位每个数字加32位起始号码，总共32 + 7 * 999 = 7025比特 。
一个混合的情况 ，其中800个电话号码差异适合一个块（800 * 7 = 5600），180个数字适合两个块（180 * 2 * 7 = 2520），19个数字适合三个块（20 * 3 * 7 = 399）加上最初的32位，总计8551位 。
最糟糕的情况是 ，25个数字适合三个数据块（25 * 3 * 7 = 525位），剩余的974个数字适合两个数据块（974 * 2 * 7 = 13636位），另外还有32位总共14193比特 。
编码数量|
1块| 2块| 3块| 总比特数
--------- + ---------- + ---------- + ------------
999 | 0 | 0 | 7025
800 | 180 | 19 | 8551
0 | 974 | 25 | 14193
我可以看到四个额外的优化，可以进一步减less所需的空间：
- 第三块不需要全部七位，它可以只有五位，没有标志位。
- 可以通过数字的最初传递来计算每个块的最佳大小。 也许对于某个电话簿，第一个块有5 + 1个比特，第二个7 + 1和第三个5 + 1是最佳的。 这将进一步将大小减小到6 * 999 + 32 = 6026位的最小值，再加上两组三位来存储组块1和组块2的大小（组块3的大小是所需的16位的剩余部分） 6032位！
- 相同的初始传递可以计算一个比默认值100更好的期望增量。也许有一个电话簿从55555-50000开始，所以它有一半的数字范围，所以期望的增量应该是50.或者也许有一个非线性可以使用分布（标准偏差）和其他一些最佳期望增量。 这将减less典型的差异，并可能允许使用更小的第一块。
- 可以在第一遍中进行进一步的分析以允许对电话簿进行分区，每个分区具有其自己的预期增量和块大小优化。 这将允许对于电话簿的某些高度统一的部分（减less消耗的比特数量）和较大的块大小（对于不均匀的部分来说，减less了在连续标志上浪费的比特数），允许较小的第一块大小。
真正的问题是存储五位数电话号码。
诀窍是你需要17位来存储从0到99,999的数字范围。 但是，在常规的8字节字边界上存储17位是一件麻烦事。 这就是为什么他们问你是否可以在不到4k的时候使用32位整数。
问题：所有数字组合都可能吗？
由于电话系统的性质，可能的组合可能less于65k。 我会假设是的，因为我们正在谈论电话号码中的后五个位置，而不是区号或交换前缀。
问题：此列表是静态还是需要支持更新？
如果它是静态的 ，那么当填充数据库时，计数小于50,000的位数和小于等于50,000的位数。 分配两个适当长度的uint16 数组 ：一个用于50,000以下的整数，另一个用于较高的集。 当在较高数组中存储整数时，减去50,000，当从数组中读取整数时，加上50,000。 现在，您已经将您的1,000个整数存储为2,000个8字节的字。
构build电话簿将需要两次input遍历，但平均而言，查找应该比单个数组的查找时间缩短一半。 如果查找时间是非常重要的，你可以使用更多的数组来更小的范围，但我认为在这些大小你的性能限制将从内存拉动数组，2k可能会隐藏到CPU高速caching，如果没有注册任何空间你会使用这些天。
如果是dynamic的 ，则分配一个 1000左右的数组 ，并按照sorting顺序添加数字。 将第一个字节设置为50,001，并将第二个字节设置为适当的空值，如NULL或65,000。 存储号码时，请按照sorting顺序存储。 如果一个数字低于50,001，则将其存储在 50,001标记之前 。 如果一个数字是50,001或更大，则将其存储在 50,001标记之后，但是从存储的值中减去50,000。
你的数组看起来像这样：
00001 = 00001 12345 = 12345 50001 = reserved 00001 = 50001 12345 = 62345 65000 = end-of-list
所以，当你在电话簿中查找一个数字时，你将遍历数组，如果你已经达到了50,001的值，那么你就开始在数组中添加50,000。
这使插入非常昂贵，但查找很容易，你不会花费超过2K的存储空间。
