我曾经有过一次有趣的工作面试经历。问题开始非常简单:
Q1:我们有一个装着数字
1
、2
、3
、……、100
的袋子。每个数字恰好出现一次,因此总共有 100 个数字。现在从袋子里随机取出一个数字,请找到缺失的数字。
当然,我之前听过这个面试问题,所以我很快回答道:
A1:嗯,数字
1 + 2 + 3 + … + N
的和是(N+1)(N/2)
(参见 Wikipedia: sum of arithmetic series)。对于N = 100
,总和为5050
。因此,如果袋子里所有数字都在,那么总和将恰好为
5050
。由于缺少一个数字,因此总和将小于这个值,差值就是那个缺失的数字。因此我们可以在O(N)
时间和O(1)
空间内找到那个缺失的数字。
这时候我觉得自己做得不错,但突然问题出乎意料地转向了:
Q2:那确实正确,但是如果有 两个 数字缺失,你会怎么做呢?
我以前从未见过/听说过/考虑过这种变化,所以我很慌乱,无法回答问题。面试官坚持要知道我的思考过程,所以我提到,也许我们可以通过与预期产品进行比较或者在收集了第一遍的一些信息后进行第二次遍历等方式获得更多信息,但实际上,我只是在胡乱猜测,而不是真正有一个清晰的解决方案。
面试官试图鼓励我,说有第二个方程确实是解决问题的一种方法。这时,我有点沮丧(因为事先不知道答案),问这是否是一种通用(即“有用”的)编程技术,还是只是一个诡计/捉弄的答案。
面试官的答案让我吃惊:你可以将该技术推广到找到3个缺失的数字。事实上,你可以将其推广到找到k个缺失的数字。
Qk:如果袋子中确切地缺少k个数字,你会如何高效地找到它?
这是几个月前的事了,我仍然无法理解这个技术是什么。显然,由于我们必须至少扫描所有数字一次,因此存在Ω(N)
的时间下限,但面试官坚持认为解决技术(减去O(N)
的时间输入扫描)的时间和空间复杂度是用k而不是N来定义的。
所以这里的问题很简单:
- 你会如何解决Q2?
- 你会如何解决Q3?
- 你会如何解决Qk?
澄清
- 一般来说,从1到N有N个数字,而不仅仅是1到100。
- 我不寻求明显的基于集合的解决方案,例如使用位图,通过指定位的值来编码每个数字的存在/不存在,因此额外使用
O(N)
比特。我们无法承担与N成比例的任何额外空间。 - 我也不寻求明显的先排序方法。这种方法和基于集合的方法在面试中值得一提(它们易于实现,并且根据N的不同,可能非常实用)。我正在寻找圣杯解决方案(可能实现起来实际或不实际,但具有所需的渐近特性)。
因此,当然您必须以O(N)
的时间扫描输入,但是您只能捕获少量信息(以k而不是N定义),然后必须找到k个缺失的数字。