容易的面试问题变得更加困难:给定数字1..100，在正好缺少k的情况下，找到缺失的数字

记住第i次幂的和，其中i = 1,2，..，k.这减少了求解方程组的问题 a 1 + a 2 + ... + a k = b 1 a 1 2 + a 2 2 + ... + a k 2 = b 2 ... a 1 k + a 2 k + ... + a k k = b k使用牛顿的身份，知道b i 可以计算 c 1 = a 1 + a 2 + ... a k c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k ... c k = a 1 a 2 ... a k如果展开多项式(xa 1 )...(xa k )，则系数将恰好是c 1 ，.. .，c k -请参见维埃特公式 .由于每个多项式因子都是唯一的(多项式的环是欧几里德域)，因此这意味着 i 是唯一确定的，直到排列.到此为止，证明记忆力足以恢复数字.对于常数k，这是个好方法.但是，当k变化时，直接计算c 1 ，...，c k 的方法非常昂贵，因为例如c k 是所有缺失数字的乘积，大小为n！/(n-k)!.为了克服这个问题，请在Z q 字段中执行计算，其中q是素数使得n< = q< 2n-它存在于 Bertrand的假设中.由于公式仍然成立，并且多项式的因式分解仍然是唯一的，因此无需更改证明.您还需要一种用于对有限域进行因式分解的算法，例如 Berlekamp 或 Cantor-Zassenhaus .常数k的高级伪代码:计算给定数字的第i次幂减去可得到未知数的i次幂.求和b i .使用牛顿的恒等式从b i 计算系数；称它们为c i .基本上，c 1 = b 1 ； c 2 =(c 1 b 1 -b 2 )/2;有关详细公式，请参见Wikipedia多项式x k -c 1 x k-1 + ... + c k多项式的根是所需的数字a 1 ，...，a k .对于变化的k，求素数n< = q< 2n使用Miller-Rabin，然后执行所有以q为模的数字减少的步骤.该答案的先前版本指出，代替Z q (其中q是质数)，可以使用特征2的有限域(q = 2 ^(log n)) ).情况并非如此，因为牛顿公式需要除以不超过k的数字.I had an interesting job interview experience a while back. The question started really easy:I've heard this interview question before, of course, so I very quickly answered along the lines of:At this point I thought I had done well, but all of a sudden the question took an unexpected turn:I had never seen/heard/considered this variation before, so I panicked and couldn't answer the question. The interviewer insisted on knowing my thought process, so I mentioned that perhaps we can get more information by comparing against the expected product, or perhaps doing a second pass after having gathered some information from the first pass, etc, but I really was just shooting in the dark rather than actually having a clear path to the solution.The interviewer did try to encourage me by saying that having a second equation is indeed one way to solve the problem. At this point I was kind of upset (for not knowing the answer before hand), and asked if this is a general (read: "useful") programming technique, or if it's just a trick/gotcha answer.The interviewer's answer surprised me: you can generalize the technique to find 3 missing numbers. In fact, you can generalize it to find k missing numbers.This was a few months ago, and I still couldn't figure out what this technique is. Obviously there's a Ω(N) time lower bound since we must scan all the numbers at least once, but the interviewer insisted that the TIME and SPACE complexity of the solving technique (minus the O(N) time input scan) is defined in k not N.So the question here is simple:How would you solve Q2?How would you solve Q3?How would you solve Qk?ClarificationsGenerally there are N numbers from 1..N, not just 1..100.I'm not looking for the obvious set-based solution, e.g. using a bit set, encoding the presence/absence each number by the value of a designated bit, therefore using O(N) bits in additional space. We can't afford any additional space proportional to N.I'm also not looking for the obvious sort-first approach. This and the set-based approach are worth mentioning in an interview (they are easy to implement, and depending on N, can be very practical). I'm looking for the Holy Grail solution (which may or may not be practical to implement, but has the desired asymptotic characteristics nevertheless).So again, of course you must scan the input in O(N), but you can only capture small amount of information (defined in terms of k not N), and must then find the k missing numbers somehow. 解决方案 Here's a summary of Dimitris Andreou's link.Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equationsa1 + a2 + ... + ak = b1a12 + a22 + ... + ak2 = b2...a1k + a2k + ... + akk = bkUsing Newton's identities, knowing bi allows to computec1 = a1 + a2 + ... akc2 = a1a2 + a1a3 + ... + ak-1ak...ck = a1a2 ... akIf you expand the polynomial (x-a1)...(x-ak) the coefficients will be exactly c1, ..., ck - see Viète's formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain), this means ai are uniquely determined, up to permutation.This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.High level pseudocode for constant k:Compute i-th powers of given numbersSubtract to get sums of i-th powers of unknown numbers. Call the sums bi.Use Newton's identities to compute coefficients from bi; call them ci. Basically, c1 = b1; c2 = (c1b1 - b2)/2; see Wikipedia for exact formulasFactor the polynomial xk-c1xk-1 + ... + ck.The roots of the polynomial are the needed numbers a1, ..., ak.For varying k, find a prime n <= q < 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.EDIT: The previous version of this answer stated that instead of Zq, where q is prime, it is possible to use a finite field of characteristic 2 (q=2^(log n)). This is not the case, since Newton's formulas require division by numbers up to k. 这篇关于容易的面试问题变得更加困难:给定数字1..100，在正好缺少k的情况下，找到缺失的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！