简单的面试问题有困难：给定的数字1..100，找到丢失的号码 [英] Easy interview question got harder: given numbers 1..100, find the missing number(s)

问题描述

我有一个有趣的面试经验而回。这个问题开始真的很简单：

I had an interesting job interview experience a while back. The question started really easy:

Q1 ：我们有一个包含数字的包 1 ， 2 ， 3 ，...， 100 。每个数字恰好出现一次，所以有100个号码。现在，一个号码是随机挑选出来的袋子。寻找失踪的数字。

Q1: We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.

我听说过这个采访问题之前，当然，所以我很快线沿线的回答：

I've heard this interview question before, of course, so I very quickly answered along the lines of:

A1 ：嗯，这个数字 1 + 2 + 3 + ... + N 是（N的总和1）（N / 2）（见百科：算术系列和） 。对于 = 100 ，总和 5050 。

A1: Well, the sum of the numbers 1 + 2 + 3 + … + N is (N+1)(N/2) (see Wikipedia: sum of arithmetic series). For N = 100, the sum is 5050.

因此​​，如果所有的数字是present收入囊中，该款项将完全 5050 。由于一个数是缺失，总和将小于这一点，不同的是，数。因此，我们可以发现，在 0失踪数（N）时间和 O（1）的空间。

Thus, if all numbers are present in the bag, the sum will be exactly 5050. Since one number is missing, the sum will be less than this, and the difference is that number. So we can find that missing number in O(N) time and O(1) space.

在这一点上我想我已经做得很好，但突然的问题采取了一个意想不到的转折：

At this point I thought I had done well, but all of a sudden the question took an unexpected turn:

Q2 ：这是正确的，但现在你会怎么做，如果的两个的数字是缺少

Q2: That is correct, but now how would you do this if TWO numbers are missing?

我从来没有见过/闻/前考虑这种变化，让我惊慌失措，不能回答这个问题。面试官坚持要知道我的思维过程，所以我提到，我们或许可以通过比较预期的产品，或者做第二遍已经聚集了从第一通等一些信息后，获得更多的信息，但我真的只是拍摄在黑暗中，而不是实际具有清晰的路径到该溶液中。

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.

面试者的回答让我大吃一惊：你能概括的技术来寻找3人失踪的数字。事实上，你可以概括它找到的 K 的缺号。

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.

QK个：如果完全的 K 的数字从包里丢失，你将如何有效地找到它。

Qk: If exactly k numbers are missing from the bag, how would you find it efficiently?

这是几个月前，我还是无法弄清楚这是什么技术。显然，有一个Ω（N）时间下限，因为我们必须扫描至少一次，所有的数字，但面试官坚持认为的时间和 SPACE 的求解技术的复杂性（减去 O（N）时输入扫描）在 K 不是 N 的。

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:

• 你将如何解决 Q2 ？
• 你将如何解决 Q3 ？
• 你将如何解决 QK个？

• How would you solve Q2?
• How would you solve Q3?
• How would you solve Qk?

从1
• 通常有 N 的数字。 N 的，不只是1..100。
• 我不是在寻找明显的集中式解决方案，例如：使用位设置时，每个数字由指定的位的值编码presence /不存在，因此，使用 O（N）位额外的空间。我们不能承受任何额外的空间成正比的 N 的
• 在我还没有寻找明显的排序第一的方针。这与基于集合的做法是值得一提的在接受采访时（他们很容易实现，并且根据的 N 的，可以是非常实用）。我在寻找圣杯的解决方案（这可能是也可能不是实际的实现，但所需的渐进特征仍然）。

• Generally 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).

所以，再一次，你当然必须扫描输入 O（N），但是你只能捕获少量的信息（在 K来定义的没有的 N 的），然后必须找到的 K 的丢失号码莫名其妙。

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.

推荐答案

下面是<一总结href="http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number/3492664#3492664">Dimitris ANDREOU 的链接。

记住和的第i个大国，其中i = 1,2，...，K。这减少了问题求解方程系统

Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equations

在<子> 1 + A ₂ + ... + A <子> K = B ₁

a₁ + a₂ + ... + a_k = b₁

在<子> 1 ² + A ₂ ² + ... + A <子> K ² = B ₂

a₁² + a₂² + ... + a_k² = b₂

...

在<子> 1 ^K + A ₂ ^K + ... + A <子> K ^K = B <子> K

a₁^k + a₂^k + ... + a_k^k = b_k

使用<一个href="http://en.wikipedia.org/wiki/Newton_identities#Formulation_in_terms_of_symmetric_polynomials">Newton's 的身份，知道b <子>我可以计算

Using Newton's identities, knowing b_i allows to compute

C ₁ = A <子> 1 + A ₂ + ...一个<子> K

c₁ = a₁ + a₂ + ... a_k

C ₂ = A <子> 1 在 ₂ + A <子> 1 在<子> 3 + ... + A <子> K-1 在<子> K

c₂ = a₁a₂ + a₁a₃ + ... + a_k-1a_k

...

C <子> K = A <子> 1 在 ₂ ...一个<子> K

c_k = a₁a₂ ... a_k

如果您展开多项式（XA <子> 1 ）...（XA <子> K ）的系数将完全ç<子> 1 ，.. 。，C <子> K - 见Viète的公式的。由于每个多项式唯一因素（多项式环是欧几里德域），这意味着<子>我被唯一地确定，高达频带排列。

If you expand the polynomial (x-a₁)...(x-a_k) the coefficients will be exactly c₁, ..., c_k - see Viète's formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain), this means a_i are uniquely determined, up to permutation.

这结尾的证明，记忆的力量足以恢复的数字。对于常数K，这是一个很好的办法。

This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.

然而，当k是变化的，计算ç<子> 1 ，...，C <子>的直接方法氏/ SUB>是prohibitely昂贵的，因为如ç<子> K 是所有丢失数的乘积，幅度N！/（NK）！为了克服这个，Z中执行计算<子>①字段，其中q是素使得n＆其中; = Q＆其中; 2N - 它是否存在伯特兰的假设。证明并不需要改变，因为式仍然保持，并且多项式因式分解仍然是唯一的。您还需要一个算法分解有限域上，例如一个由的Berlekamp 或的康托尔 - Zassenhaus

However, when k is varying, the direct approach of computing c₁,...,c_k is prohibitely expensive, since e.g. c_k is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Z_q 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.

高层伪code为常数k：

High level pseudocode for constant k:

• 在给定的数字计算第i个权力
• 减去获得的未知数量的第i个功率总和。打电话的款项b <子>我。
• 使用牛顿的身份从B <子>计算系数我;叫他们ç<子>我。基本上，C ₁ = B ₁ ; ç ₂ =（C ₁ B ₁ - B ₂ ）/ 2;见维基百科精确的公式
• 系数多项式x ^K -c <子> 1 X ^K-1 + ... + C <子> K
• 多项式的根是在需要数字的<子> 1 ，...，A <子> K 。

• Compute i-th powers of given numbers
• Subtract to get sums of i-th powers of unknown numbers. Call the sums b_i.
• Use Newton's identities to compute coefficients from b_i; call them c_i. Basically, c₁ = b₁; c₂ = (c₁b₁ - b₂)/2; see Wikipedia for exact formulas
• Factor the polynomial x^k-c₁x^k-1 + ... + c_k.
• The roots of the polynomial are the needed numbers a₁, ..., a_k.

有关不同K，找到一个素数N'LT; = Q＆LT; 2N例如使用米勒罗宾，并具有降低的模q的所有数值执行的步骤

For varying k, find a prime n <= q < 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.

至于海因里希Apfelmus评论，而不是一个素数q，你可以使用q = 2 ^⌈logn⌉和执行的算术有限域。

As Heinrich Apfelmus commented, instead of a prime q you can use q=2^{⌈log n⌉} and perform arithmetic in finite field.

这篇关于简单的面试问题有困难：给定的数字1..100，找到丢失的号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！