首页 文章

存储千个电话号码的最有效方式

提问于
浏览 次
93

这是一个谷歌面试问题：

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

这样做最有效的节省空间的方法是什么？

我回答哈希表和后来的霍夫曼编码，但我的采访者说我没有朝着正确的方向前进 . 请帮帮我 .

可以使用后缀trie帮助吗？

理想情况下，1000个数字存储每个数字需要4个字节，因此总共需要4000个字节来存储1000个数字 . 从数量上讲，我希望将存储空间减少到<4000字节，这是我的采访者向我解释的内容 .

algorithm data-structures

13 回答

  • 36

    为什么不保持简单？使用结构数组 .

    所以我们可以将前5位数保存为常数，所以暂时不要忘记它们 .

    65535是最多可以存储在16位数字中，我们可以拥有的最大数字是99999，它与第17位数一致，最大值为131071 .

    使用32位数据类型是一种浪费，因为我们只需要1位额外的16位...因此，我们可以定义一个具有布尔（或字符）和16位数字的结构 .

    假设C / C.

    typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

    这个结构只占用3个字节，我们需要一个1000的数组，总共3000个字节 . 我们将总空间减少了25％！

    至于存储数字，我们可以做简单的按位数学运算

    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;

    要搜索数字，我们需要一个排序数组 . 所以当保存数字时，对数组进行排序（我会亲自选择合并排序，O（nlogn）） . 现在要搜索，我会采用合并排序方法 . 拆分数组，看看我们的数字介于哪一个之间 . 然后只在该数组上调用该函数 . 递归执行此操作直到您有匹配并返回索引，否则，它不存在并打印错误代码 . 这种搜索速度非常快，最糟糕的情况仍然比O（nlogn）更好，因为它绝对会在比合并排序更少的时间内执行（每次只复制分割的一侧，而不是双方:)），是O（nlogn） .

    回复于
  • 0

    http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

    我曾经接受过他们询问数据结构的采访 . 我忘记了“阵列” .

    回复于
  • 0

    真正的问题是存储五位数的电话号码 .

    诀窍是你需要17位来存储0..99,999的数字范围 . 但是，在传统的8字节字边界上存储17位是一件麻烦事 . 这就是为什么他们在不使用32位整数的情况下询问你是否可以在不到4k的时间内完成 .

    Question: are all number combinations possible?

    由于电话系统的性质，可能的组合可能少于65k . 我将假设 yes 因为我们正在谈论电话号码中的后五个位置，而不是区号或交换前缀 .

    Question: will this list be static or will it need to support updates?

    如果它是静态的，那么当需要填充数据库时，计算位数<50,000和位数> = 50,000 . 分配两个适当长度的 uint16 数组：一个用于低于50,000的整数，一个用于高一组 . 在较高数组中存储整数时，减去50,000，当从该数组中读取整数时，添加50,000 . 现在，您已将2,000个整数存储为2,000个8字节的单词 .

    构建电话簿将需要两次输入遍历，但查找的平均时间应该是单个阵列的一半 . 如果查找时间非常重要，你可以使用更多的数组用于较小的范围，但我认为在这些大小的情况下，你的性能限制将从内存中拉出数组，如果不在你使用这些数据的任何内容上注册空间，2k可能会隐藏到CPU缓存中天 .

    如果它是动态的，则分配一个1000左右的数组 uint16 ，并按排序顺序添加数字 . 将第一个字节设置为50,001，并将第二个字节设置为适当的空值，如NULL或65,000 . 存储数字时，请按排序顺序存储它们 . 如果数字低于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的存储空间 .

    回复于
  • 16

    这相当于存储每个小于100,000的一千个非负整数 . 我们可以使用算术编码之类的东西来做到这一点 .

    最终，数字将存储在排序列表中 . 我注意到列表中相邻数字之间的预期差异是100,000 / 1000 = 100，这可能是用7位表示 . 还有许多情况需要超过7位 . 表示这些不常见情况的一种简单方法是采用utf-8方案，其中一个字节表示7位整数，除非第一位置1，在这种情况下读取下一个字节以产生14位整数，除非它的第一个位置1，在这种情况下，读取下一个字节表示一个21位整数 .

    因此，连续整数之间的差异的至少一半可以用一个字节表示，并且几乎所有其余整数都需要两个字节 . 一些数字除以16,384之外的差异，需要三个字节，但不能超过61个 . 那么平均存储量将是每个数字大约12位，或者更少，或者最多1500个字节 .

    这种方法的缺点是检查数字的存在现在是O（n） . 但是，没有规定时间复杂性要求 .

    写完之后，我注意到ruslik已经提出了上面的差异方法，唯一的区别是编码方案 . 我的可能更简单但效率更低 .

    回复于
  • 22

    Fixed storage of 1073 bytes for 1,000 numbers:

    此存储方法的基本格式是存储前5个数字，每个组的计数以及每个组中每个数字的偏移量 .

    Prefix:
    我们的5位数前缀占用了第一个 17 bits .

    Grouping:
    接下来，我们需要找出一个适合数字的大小分组 . 设's try have about 1 number per group. Since we know there are about 1000 numbers to store, we divide 99,999 into about 1000 parts. If we chose the group size as 100, there would be wasted bits, so let'尝试组大小为128，可以用7位表示 . 这为我们提供了782个小组 .

    Counts:
    接下来，对于782个组中的每个组，我们需要存储每个组中的条目数 . 每组的7位计数将产生 7*782=5,474 bits ，这是非常低效的，因为我们选择我们的组的方式所代表的平均数约为1 .

    因此，相反，我们有一个可变大小的计数，其中一个组中的每个数字前导1后跟一个0.因此，如果我们在一个组中有 x 个数字，我们将 x 1's 后跟一个 0 来表示计数 . 例如，如果我们在一个组中有5个数字，则计数将由 111110 表示 . 使用这种方法，如果有1,000个数字，我们最终得到1000 1 's and 782 0' s，共计 1000 + 782 = 1,782 bits for the counts .

    Offset:
    最后，每个数字的格式只是每组的7位偏移量 . 例如，如果00000和00001是0-127组中的唯一数字，则该组的位将为 110 0000000 0000001 . 假设有1,000个数字，那么将会有 7,000 bits for the offsets .

    因此，我们假设1,000个数字的最终计数如下：

    17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

    现在，让我们检查一下，通过舍入到128位的组大小选择是否是组大小的最佳选择 . 选择 x 作为表示每个组的位数，大小的公式为：

    Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

    将整数值 x 的这个等式最小化得到 x=6 ，得到8,580位= 1,073 bytes . 因此，我们的理想存储如下：

    • 组大小：2 ^ 6 = 64

    • 团体数量：1,562

    • 总存储空间：

    1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

    回复于
  • 1

    这是对aix's answer的改进 . 考虑使用三个"layers"作为数据结构：第一个是前五位数（17位）的常量;所以从这里开始，每个电话号码只剩下剩下的五位数字 . 我们将这些剩余的五位数视为17位二进制整数，并使用一种方法存储这些位的k，并使用不同的方法存储17-k = m，最后确定k以最小化所需空间 .

    我们首先对电话号码进行排序（全部减少到5位小数） . 然后我们计算有多少电话号码，其中包含前m位的二进制数都是0，对于多少电话号码，前m位最多为0 ... 01，有多少电话号码是第一个m位最多为0 ... 10，等等，最多m个位为1 ... 11的电话号码数 - 最后一个计数为1000（十进制） . 有2 ^ m这样的计数，每个计数最多为1000.如果我们省略最后一个（因为我们知道它仍然是1000），我们可以将所有这些数字存储在（2 ^ m - 1）的连续块中* 10位 . （10位足以存储小于1024的数字 . ）

    所有（减少的）电话号码的最后k位连续存储在存储器中;所以如果k是，比方说，7，那么这个存储器块的前7位（位0到6）对应于第一个（减少的）电话号码的最后7位，第7位到第13位对应于最后7位第二个（减少的）电话号码，等等 . 这需要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）* 101000 * k

    对于k = 9和k = 10，或者ceil（10997/8）= 1375字节，其惊人地达到其最小值10997 .

    如果我们想知道某个电话号码是否在我们的集合中，我们首先检查前五个二进制数字是否与我们存储的五个数字相匹配 . 然后我们将剩余的五个数字分成其顶部m = 7位（也就是说，m位数M）并且其低k = 10位（数字K） . 我们现在找到前m个数字最多为M-1的减少的电话号码的数量[M-1]，以及前m个数字最多为M的减少的电话号码的数量a [M]，从第一个比特块开始 . 我们现在检查第二个存储器块中的第[M-1]个和第[M]个k位序列，看看我们是否找到K;在最坏的情况下，有1000个这样的序列，所以如果我们使用二进制搜索，我们可以完成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）的边界情况可能出现问题，但这很容易修复 .

    最后，从熵的角度来看，不可能存储10 ^ 3个正整数的子集，小于10 ^ 5，小于ceil（log [2]（二项式（10 ^ 5,10 ^ 3）） ）= 8073.包括前5个数字所需的17个，仍有10997 - 8090 = 2907位的间隙 . 这是一个有趣的挑战，看看是否有更好的解决方案，你仍然可以相对有效地访问数字！

    回复于
  • 42

    我之前听说过这个问题（但没有前5位数是相同的假设），最简单的方法是Rice Coding：

    1）由于顺序无关紧要，我们可以对它们进行排序，并保存连续值之间的差异 . 在我们的例子中，平均差异将是100.000 / 1000 = 100

    2）使用Rice代码（基数128或64）或甚至Golomb代码（基数100）对差异进行编码 .

    EDIT : 用基数128估算Rice编码（不是因为它会给出最好的结果，但因为它更容易计算）：

    我们将按原样保存第一个值（32位） .
    剩余的999个值是差异（我们希望它们很小，平均为100）将包含：

    一元值 value / 128 （可变位数1位作为终结符）
    value % 128 的二进制值（7位）

    我们必须以某种方式估计可变位数的限制（让我们称之为 VBL ）：
    下限：认为我们很幸运，没有差异大于我们的基数（在这种情况下为128） . 这意味着增加0位 .
    上限：因为所有小于base的差异都将以二进制数字编码，我们需要在一元中编码的最大数量是100000/128 = 781.25（甚至更少，因为我们不希望大多数差异为零） .

    因此，结果是32 999 *（1 7）变量（0..782）位= 1003变量（0..98）字节 .

    回复于
  • 15

    在下文中，我将数字视为整数变量（而不是字符串）：

    • 对数字排序 .

    • 将每个数字拆分为前五位数和后五位数 .

    • 前五位数字在数字上相同，因此只存储一次 . 这将需要17位存储空间 .

    • 分别存储每个数字的最后五位数字 . 这将需要每个数字17位 .

    概括：前17位是公共前缀，后续1000组17位是按升序存储的每个数字的最后5位 .

    总的来说，我们看到的是1000个数字的2128个字节，或者每10个数字电话号码的17.017个字节 .

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

    回复于
  • 5

    将此作为一个纯粹的理论问题并留下实现的帮助，最有效的方法是在巨大的索引表中索引所有可能的10000个最后数字集 . 假设您有超过1000个数字，则需要多于8000位来唯一标识当前集合 . 没有更大的压缩可能，因为那样你将有两个被识别为相同状态的集合 .

    这样做的问题是，您必须将程序中的每个2 ^ 8000集合表示为lut，而google甚至都不具备此功能 .

    查找将是O（1），打印所有数字O（n） . 插入将是O（2 ^ 8000），理论上是O（1），但实际上是不可用的 .

    在一次采访中，我只会给出这个答案，如果我确定的话，该公司正在寻找一个能够开箱即用的人 . 否则，这可能会让你看起来像一个没有现实世界关注的理论家 .

    EDIT ：好的，这是一个"implementation" .

    构建实现的步骤：

    • 取一个大小为100 000 *（1000选择100 000）位的常量数组 . 是的，我知道这个阵列会这样的事实需要比宇宙中的原子更多的空间几个数量级 .

    • 将这个大型阵列分成每个10万个块 .

    • 在每个块存储中，一个位数组用于最后五位数的一个特定组合 .

    这不是程序，而是一种元程序，它将构建一个现在可以在程序中使用的巨大LUT . 在计算空间效率时，通常不计算程序的常量，因此在进行最终计算时我们不关心这个数组 .

    以下是如何使用此LUT：

    • 当有人给你1000个号码时，你会单独存储前五个数字 .

    • 找出数组的哪个块与此集匹配 .

    • 将该组的编号存储在一个8074位编号中（调用此c） .

    这意味着存储我们只需要8091位，我们在这里证明这是最佳编码 . 然而，找到正确的块需要O（100 000 *（100 000选择1000）），根据数学规则是O（1），但实际上总是需要比宇宙时间更长的时间 .

    查找很简单：

    • 前五位数的条带（剩余数字将被称为n'） .

    • 测试它们是否匹配

    • 计算i = c * 100000 n'

    • 检查LUT中i的位是否设置为1

    打印所有数字也很简单（实际上需要O（100000）= O（1），因为你总是要检查当前块的所有位，所以我上面错误地计算了这个） .

    我不会称之为"implementation"，因为公然无视限制（宇宙的大小和宇宙所存在的时间或地球将存在） . 然而，理论上这是最佳解决方案 . 对于较小的问题，这实际上可以完成，有时也会完成 . 例如sorting networks是这种编码方式的一个例子，可以作为递归排序算法的最后一步，以获得更大的加速 .

    回复于
  • 1

    这是Bentley编程珍珠的一个众所周知的问题 .

    解决方案：从数字中删除前五位数，因为每个数字都相同 . 然后使用按位运算来表示剩余的9999可能值 . 您只需要2 ^ 17位来表示数字 . 每个位代表一个数字 . 如果该位置位，则该号码在电话簿中 .

    要打印所有数字，只需打印设置了该位的所有数字，并加上前缀 . 要搜索给定的数字，请执行必要的位运算以检查数字的按位表示 .

    您可以在O（1）中搜索数字，并且由于位表示，空间效率最大 .

    HTH Chris .

    回复于
  • 0

    只是快速询问我们不想将数字更改为基数36的原因 . 它可能不会节省太多空间，但它肯定会节省搜索时间，因为你会看到比10digts少得多的数据 . 或者我会根据每个组将它们分成文件 . 所以我会命名一个文件（111）-222.txt，然后我只存储适合该组的数字，然后让它们以数字顺序可见，这样我总是可以查看该文件是否退出 . 在我进行biger搜索之前 . 或者是正确的我将运行二进制搜索一个文件，看看它是否退出 . 和另一个关于文件内容的博物搜索

    回复于
  • 7

    我可能会考虑使用Trie的某些压缩版本（可能是@Misha建议的DAWG） .

    这将自动利用它们都具有共同前缀的事实 .

    搜索将在恒定时间内执行，并且将以线性时间执行打印 .

    回复于
  • 1

    我的解决方案：最佳情况7.025位/数，最坏情况14.193位/数，粗略平均8.551位/数 . 流编码，无随机访问 .

    甚至在阅读ruslik的答案之前，我立即想到编码每个数字之间的差异，因为它会很小并且应该相对一致，但解决方案还必须能够适应最坏的情况 . 我们有一个100000个数字的空间，只包含1000个数字 . 在完美统一的电话簿中，每个号码将比前一个号码大100：

    55555-12 3 45
    55555-12 4 45
    55555-12 5 45

    如果是这种情况，则需要零存储来编码数字之间的差异，因为它是已知常量 . 不幸的是，数字可能与100的理想步长不同 . 我会将理想增量的差值编码为100，因此如果两个相邻的数字相差103，我会编码数字3，如果两个相邻的数字相差92，我会编码-8 . 我将delta称为100的理想增量“ variance ” .

    方差范围可以从-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：

    Variance  |  Encoded Value
-----------+----------------
    0      |       0
   -1      |       1
    1      |       2
   -2      |       3
    2      |       4
   -3      |       5
    3      |       6
   ...     |      ...
  -31      |      61
   31      |      62
  -32      |      63
-----------|--------------- 6 bits
   32      |      64
  -33      |      65
   33      |      66
   ...     |      ...
  -98      |      195
   98      |      196
  -99      |      197
-----------|--------------- End of ZigZag
   100     |      198
   101     |      199
   ...     |      ...
  3996     |     4094
  3997     |     4095
-----------|--------------- 12 bits
  3998     |     4096
  3999     |     4097
   ...     |      ...
 262045    |    262143
-----------|--------------- 18 bits

    有关如何将差异编码为位的一些示例，包括用于指示其他块的标志：

    Variance  |  Encoded Bits
-----------+----------------
     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

    因此，样本电话簿的前三个数字将被编码为比特流，如下所示：

    BIN 000101001011001000100110010000011001   000110 1     010110 1 00001 0
PH#           55555-12345                 55555-12448     55555-12491
POS                1                           2               3

    Best case scenario ，电话簿在某种程度上是均匀分布的，并且没有两个电话号码的方差大于32，因此它将使用每个数字7位加上32位作为起始编号，总计为32 7 * 999 = 7025 bits .
    A mixed scenario ，其中800个电话号码的方差适合一个块（800 * 7 = 5600），180个数字分别适合两个块（180 * 2 * 7 = 2520），19个数字分别适合三个块（20 * 3 * 7） = 399），加上最初的32位，总计 8551 bits .
    Worst case scenario ，25个数字适合三个块（25 * 3 * 7 = 525位），其余974个数字适合两个块（974 * 2 * 7 = 13636位），加上第一个数字的32位总数为 14193 bits .

    Amount of encoded numbers   |
 1-chunk | 2-chunks | 3-chunks | Total bits
---------+----------+----------+------------
   999   |    0     |    0     |   7025
   800   |   180    |    19    |   8551
    0    |   974    |    25    |  14193

    我可以看到可以执行的四个额外优化，以进一步减少所需的空间：

    • 第三个块不需要全7位，它可以只是5位而没有标志位 .

    • 可以对数字进行初始传递，以计算每个块的最佳大小 . 也许对于某个电话簿，最好让第一个块具有5个1位，第二个7 1和第三个5 1.这将进一步将大小减小到最小6 * 999 32 = 6026位，再加上两个用于存储块1和2的大小的三个位组（块3的大小是所需16位的剩余部分），总共6032位！

    • 相同的初始通道可以计算出比默认值100更好的预期增量 . 也许's a phone book that starts from 55555-50000, and so it has half the number range so the expected increment should be 50. Or maybe there'是非线性分布（可能是标准偏差），可以使用其他一些最佳预期增量 . 这将减少典型的方差，并且可能允许使用甚至更小的第一块 .

    • 可以在第一遍中进行进一步分析，以允许对电话簿进行分区，每个分区都有自己的预期增量和块大小优化 . 这将允许电话簿的某些高度统一的部分（减少消耗的比特数）的较小的第一块大小和非均匀部分的较大的块大小（减少在连续标志上浪费的比特数） .

    回复于

相关问题