不久前我有一次有趣的工作面试经历。问题一开始就很简单:
Q1:我们有一个袋子,里面装着编号
1
,2
,3
,…,100
。每个数字只显示一次,因此有100个数字。现在,从袋子中随机抽取一个数字。找到丢失的号码
当然,我以前听过这个面试问题,所以我很快回答了以下问题:
A1:嗯,数字的总和
1+2+3+…+N
是(N+1)(N/2)
(参见维基百科:算术级数之和)。对于N=100
,总和为5050
因此,如果包中有所有数字,则总和将正好为
5050
。因为缺少一个数字,所以总和将小于这个数字,差值就是这个数字。所以我们可以在O(N)
时间和O(1)
空间中找到缺失的数字
在这一点上,我认为我做得很好,但突然问题发生了意想不到的转变:
Q2:这是正确的,但是现在如果缺少两个数字,您会怎么做呢
我以前从未见过/听到/考虑过这种变化,所以我惊慌失措,无法回答这个问题。面试官坚持要了解我的思维过程,所以我提到,也许我们可以通过与预期产品进行比较来获得更多信息,或者在收集了第一遍的信息后再进行第二遍,等等,但我真的只是在黑暗中拍摄,而不是真正有一个明确的解决办法
面试官确实试图鼓励我说,第二个等式确实是解决问题的一种方法。在这一点上,我有点心烦意乱(因为之前不知道答案),并问这是一种通用的编程技术(阅读:“有用的”)还是仅仅是一个技巧/抓住答案
面试官的回答让我很惊讶:你可以概括这个技巧,找出3个缺失的数字。事实上,您可以对其进行推广以查找k缺失的数字
Qk:如果包中缺少确切的k数字,您如何有效地找到它
这是几个月前的事了,我仍然不知道这是什么技术。显然存在一个Ω(N)
时间下限,因为我们必须至少扫描所有数字一次,但采访者坚持认为,求解技术的时间和空间复杂性(减去O(N)
时间输入扫描)是在k中定义的,而不是N
所以这里的问题很简单:
- 您将如何解决第二季度的问题
- 您将如何解决第三季度的问题
- 您将如何解决Qk问题
澄清
- 一般来说,1..N中有N,而不仅仅是1..100
- 我不是在寻找明显的基于集合的解决方案,例如,使用一个位集合,通过指定位的值对每个数字的存在/不存在进行编码,因此在额外的空间中使用
O(N)
位。我们负担不起任何与N成比例的额外空间 - 我也不是在寻找明显的排序优先的方法。这一点和基于集合的方法值得在访谈中提及(它们易于实现,并且取决于N,可能非常实用)。我正在寻找圣杯解决方案(它可能实现起来很实用,也可能实现起来不实用,但仍然具有所需的渐进特性)
因此,当然您必须再次扫描O(N)
中的输入,但您只能捕获少量信息(定义为k而不是N),然后必须以某种方式找到k缺失的数字
下面是Dimitris Andreou链接的摘要
记住i次方之和,其中i=1,2,…,k。这将问题简化为求解方程组
a1+a2+…+ak=b1
a12+a22+…+ak2=b2
a1k+a2k+…+akk=bk
利用牛顿恒等式,知道bi可以计算
c1=a1+a2+。。。ak
c2=a1a2+a1a3+…+ak-1ak
ck=a1a2。。。ak
如果展开多项式(x-a1)…(x-ak),则系数将精确为c1,…,ck-参见Viète的公式。由于每个多项式因子都是唯一的(多项式环是欧几里德域),这意味着ai是唯一确定的,直到置换
这就结束了一个证明:记住幂就足以恢复数字。对于常数k,这是一个很好的方法
然而,当k变化时,计算c1,…,ck的直接方法是非常昂贵的,因为例如ck是所有缺失数的乘积,数量级n/(n-k)!。为了克服这个问题,在Zq字段中执行计算,其中q是质数,使得n<;=q<;2n-根据伯特兰的假设,它是存在的。证明不需要改变,因为公式仍然成立,多项式的因式分解仍然是唯一的。您还需要有限域上的因式分解算法,例如Berlekamp或Cantor Zassenhaus的算法
常数k的高级伪码:
- 计算给定数字的i次方
- 减法得到未知数的i次方和。调用总和bi
- 使用牛顿恒等式从bi计算系数;叫他们ci。基本上,c1=b1;c2=(c1b1-b2)/2;有关精确公式,请参见维基百科
- 多项式xk-c1xk-1+…+ck
- 多项式的根是所需的数字a1,…,ak
对于变化的k,找到一个素数n<;=q<;2n使用例如Miller-Rabin,并使用所有减少的模数q执行步骤
编辑:该答案的前一版本指出,可以使用特征2(q=2^(logn))的有限域,而不是Zq,其中q是素数。事实并非如此,因为牛顿公式要求除以k以下的数