pri*_*sia 93 algorithm data-structures
这是一个谷歌面试问题:
存储有大约一千个电话号码,每个电话号码具有10个数字.您可以假设每个数字的前5位数相同.您必须执行以下操作:搜索是否存在给定数字.湾 打印所有号码
这样做最有效的节省空间的方法是什么？
我回答哈希表和后来的霍夫曼编码,但我的采访者说我没有朝着正确的方向前进.请帮帮我.
可以使用后缀trie帮助吗？
理想情况下,1000个数字存储每个数字需要4个字节,因此总共需要4000个字节来存储1000个数字.在数量上,我希望将存储空间减少到<4000字节,这是我的采访者向我解释的内容.
NPE*_*NPE 43
在下文中,我将数字视为整数变量(而不是字符串):
总结一下:前17位是公共前缀,后续1000组17位是按升序存储的每个数字的后五位数.
我们总共看1000个数字的2128个字节,或者每10个数字电话号码17.017个字节.
搜索是O(log n)(二进制搜索)和完整枚举O(n).
Eri*_* P. 36
这是对aix答案的改进.考虑为数据结构使用三个"层":第一个是前五位数(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)*10 + 1000*k
对于k = 9和k = 10,或者ceil(10997/8)= 1375字节,其惊人地达到其最小值10997 .
如果我们想知道某个电话号码是否在我们的集合中,我们首先检查前五个二进制数字是否与我们存储的五位数字相匹配.然后我们将剩余的五个数字分成其顶部m = 7位(也就是说,m位数M)和其低k = 10位(数字K).我们现在发现的数量一 [M-1]的降低电话号码,第一米的数字是最多中号 - 1,数一减少电话号码其中第[M] 米的数字是最多中号,从第一个比特块开始.现在我们之间检查一个 [M-1]和第一个 [M]次的序列ķ在存储器的第二块的比特,以查看是否发现ķ ; 在最坏的情况下,有1000个这样的序列,所以如果我们使用二进制搜索,我们可以完成O(log 1000)操作.
伪代码用于打印所有1000个号码如下,其中我访问ķ "日ķ的存储器的第一个块作为位输入一个 [K]和中号 "第米的存储器中的第二块的比特的条目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位的间隙.这是一个有趣的挑战,看看是否有更好的解决方案,你仍然可以相对有效地访问数字!
Mik*_*ail 22
http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton
我曾经接受过他们询问数据结构的采访.我忘记了"阵列".
rus*_*lik 15
我之前听说过这个问题(但没有前5位数是相同的假设),最简单的方法就是Rice编码:
1)由于顺序无关紧要,我们可以对它们进行排序,并保存连续值之间的差异.在我们的例子中,平均差异将是100.000/1000 = 100
2)使用Rice代码(基数128或64)或甚至Golomb代码(基数100)对差异进行编码.
编辑:对基数为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)字节.
这是Bentley编程珍珠的一个众所周知的问题.
解决方案:从数字中删除前五位数,因为每个数字都相同.然后使用按位运算来表示剩余的9999可能值.您只需要2 ^ 17位来表示数字.每个位代表一个数字.如果该位置位,则该号码在电话簿中.
要打印所有数字,只需打印设置了该位的所有数字,并加上前缀.要搜索给定的数字,请执行必要的位运算以检查数字的按位表示.
您可以在O(1)中搜索数字,并且由于位表示,空间效率最大.
HTH Chris.
固定存储1073个字节,用于1,000个数字:
此存储方法的基本格式是存储前5个数字,每个组的计数以及每个组中每个数字的偏移量.
前缀:
我们的5位前缀占用前17位.
分组:
接下来,我们需要找出一个适合数字的大小分组.让我们尝试每组约1个数字.由于我们知道存储了大约1000个数字,因此我们将99,999分成大约1000个部分.如果我们选择组大小为100,则会有浪费的比特,所以让我们尝试128的组大小,可以用7位表示.这为我们提供了782个小组.
计数:
接下来,对于782个组中的每个组,我们需要存储每个组中的条目数.每组的7位计数会产生7*782=5,474 bits,这是非常低效的,因为我们选择我们的组的方式所代表的平均数约为1.
因此,相反,我们有一个可变大小的计数,一组中每个数字的前导1,后跟一个0.因此,如果我们x在一个组中有数字,我们x 1's后面跟着一个0来表示计数.例如,如果我们在一个组中有5个数字,则计数将由111110.使用这种方法,如果有1,000个数字,我们最终得到1000个1和782个0,总计1000 + 782 = 1,782位计数.
偏移:
最后,每个数字的格式只是每组的7位偏移量.例如,如果00000和00001是0-127组中的唯一数字,则该组的位将为110 0000000 0000001.假设有1,000个数字,则偏移量将为7,000位.
因此,我们假设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,其产生8580个比特= 1073个字节.因此,我们的理想存储如下:
总存储量:
1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes