前段时间我有一次有趣的面试经历。问题一开始很简单:

Q1:我们有一个袋子,里面有数字1,2,3,…,100。每个数字恰好出现一次,所以有100个数字。现在从袋子里随机抽取一个数字。找到丢失的号码。

当然,我以前听过这个面试问题,所以我很快就回答了这个问题:

A1:嗯,1 + 2 + 3 +…+ N的和是(N+1)(N/2)(参见维基百科:等差级数的和)。当N = 100时,和是5050。 因此,如果所有的数字都在袋子里,总和将恰好是5050。因为少了一个数,总和就会小于这个数,差的就是这个数。所以我们可以在O(N)时间和O(1)空间中找到这个缺失的数。

在这一点上,我认为我做得很好,但突然间,问题发生了意想不到的转变:

这是正确的,但是如果少了两个数字,你会怎么做?

我以前从未见过/听过/考虑过这种变化,所以我很恐慌,无法回答这个问题。面试官坚持要知道我的思考过程,所以我提到,也许我们可以通过与预期产品进行比较来获得更多信息,或者在从第一次传递中收集到一些信息后再进行第二次传递,等等,但我真的只是在黑暗中拍摄,而不是真正有一个明确的解决方案的路径。

面试官试图鼓励我说,有第二个方程确实是解决问题的一种方法。在这一点上,我有点不安(因为事先不知道答案),并问这是一种通用的(阅读:“有用的”)编程技术,还是只是一个技巧/答案。

面试官的回答让我惊讶:你可以把这个技巧概括为3个缺失的数字。事实上,你可以推广它来找到k个缺失的数。

Qk:如果袋子里少了k个数字,你如何有效地找到它?

这是几个月前的事了,我还不明白这个技巧是什么。显然有一个Ω(N)的时间下限,因为我们必须扫描所有的数字至少一次,但面试官坚持认为,解决技术的时间和空间复杂度(减去O(N)次输入扫描)定义为k而不是N。

所以问题很简单:

如何解决Q2? 你会如何解决Q3? 如何求解Qk?


澄清

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个缺失的数字。


当前回答

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它,比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案,但如果我在这种情况下面临这样的任务(已知边界,低边界),这是我在现实生活中会使用的解决方案。如果数字集非常大,那么我当然会考虑一个更有效的算法,但在此之前,简单的解决方案对我来说已经足够了。

其他回答

我会用另一种方法来回答这个问题,询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求,显而易见的基于集的解决方案可能是正确的,而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

这当然不是批处理预先生成的数字袋的最快方法,因为整个过程运行O((log 1 + log 2 +…)+ log n) + (log n + log n-1 +…+ log k))。但它确实适用于任何k值(即使它事先不知道),在上面的例子中,它的应用方式使最关键的区间最小化。

你可以通过阅读Muthukrishnan的几页-数据流算法:谜题1:寻找缺失的数字来找到它。它准确地显示了您正在寻找的泛化。也许这就是面试官读到的内容,也是他提出这些问题的原因。


还请参阅sdcvvc的直接相关答案,其中还包括伪代码(万岁!没有必要阅读那些棘手的数学公式:)(谢谢,干得好!)

我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。

一个非常简单的Q2解决方案,我很惊讶没有人回答。用Q1的方法求两个缺失数字的和。我们用S表示它,那么缺失的数字中一个比S/2小另一个比S/2大(胡说)将从1到S/2的所有数字相加,并将其与公式的结果进行比较(类似于Q1中的方法),以找到缺失数字之间的较低者。用S减去它,找出缺失的更大的数。

正如@j_random_hacker所指出的,这与在O(n)个时间和O(1)个空间中寻找重复项非常相似,我的答案在这里也适用。

假设“袋子”由一个大小为N - k的基于1的数组a[]表示,我们可以在O(N)个时间和O(k)个额外空间内求解Qk。

首先,我们将数组A[]扩展k个元素,使它现在的大小为n,这是O(k)个额外空间。然后我们运行以下伪代码算法:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

第一个循环初始化k个额外的条目,使其与数组中的第一个条目相同(这只是我们知道数组中已经存在的一个方便的值——在这一步之后,大小为N-k的初始数组中缺失的任何条目在扩展数组中仍然缺失)。

第二个循环排列扩展数组,如果元素x至少出现一次,那么其中一个元素将位于位置A[x]。

注意,尽管它有一个嵌套循环,但它仍然在O(N)时间内运行——只有当有一个i使a [i] != i时才会发生交换,并且每次交换设置至少一个元素使a [i] == i,而以前不是这样的。这意味着交换的总数(因此while循环体的执行总数)最多为N-1。

第三个循环打印数组i中没有被值i占用的索引——这意味着i一定是缺失的。