这个现代编程面试挑战的解决方案不可靠吗？

Question

我在编程面试中失败了，问题是：

“给定一个由整数1、2、...、n组成的数组，其中一个数字丢失了，找出这个缺失的数字。”

面试官说正确答案是将这些数字求和，然后用n(n+1)/2减去总和，即应用公式https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

并且说任何计算机科学专业的学生都应该知道这个方法。而我的解决方案是：

char takenSpots [] = n*malloc(sizeof(char)); 
for (int k = 0; k < n; ++k) takenSpots[arr[k]-1] = 'x';
for (int k = 0; k < n; ++k) if (takenSpots[k] != 'x') return (k+1);

这并不像我承认我从未尝试过的总和解决方案那么“酷”。

首先，使用总和方法存在溢出的危险，如果arr包含 ~((int)0) 和 ~((int)0) - 1怎么办？那么arr[0] + arr[1] + ... + arr[n-1]会溢出吗？还是说这个解决方案仍然有效，因为1 + 2 + ... + n也会溢出？

- user5124106

---

for(i = 1; i < n; i++){ if(arr[i - 1] != arr[i] - 1){ printf("Found it: %i\n", arr[i] - 1); } } 我是否理解问题有误？ - Kninnug

@Kninnug：也许从问题中并不清楚，但是想法是整数不一定按顺序排列。 - psmears

好的，你应该首先初始化“takenSpots”数组中的所有条目！ - barak manos

从实际角度来看，面试官是完全错误的。他问了一个你永远不会在实践中遇到的特殊情况，并提供了仅适用于这种非常特殊情况的解决方案。但是，有一整个巨大的问题类别，你实际上会遇到，有时使用位图，有时使用集合来解决，因此如果“takenSpots”解决方案被正确实现，我将非常满意，因为这表明候选人可以解决实际生活中可能发生的问题。 - gnasher729

为什么那样会更快呢？平均需要 n/2 次比较，最坏情况下需要 n 次。如果你假设给定的序列为 1 到 n，并且缺失了一个数，你可以使用 O(log n) 的二分查找算法。现在这样就更快了。 - gnasher729

Answer 1

实际上，面试官提出的解决方案可能会遭受溢出问题。事实上，有一种更好的解决方案不会遭受溢出，如果你建议了求和方法，面试官可能会跟进这个更好的解决方案。

这种更好的解决方案不太直观，但据我所知，现在已经相当知名。

它依赖于以下内容：

x xor y = y xor x
x xor 0 = x
x xor x = 0

因此，更好的解决方案涉及计算所有给定数字的异或，然后将其与从1到n的所有数字的异或进行异或。在您的数组中出现的那些数字将与来自1到n的数字相互抵消。缺失的数字将保留。

至于如何思考这种解决方案，没有固定的方法。你只需要熟悉这样的挑战/面试问题，并接受一些计算机科学和数学的培训。

不要太担心没能理解它。如果我在大学毕业后没有看到这个问题，我几乎肯定不会在面试环境中得出求和解决方案（我可能最终会在自己的时间里想出来），并且我肯定不会提出异或解决方案。这些问题基本上是赌博。如果是命中，他们可能会问其他问题，直到你不知道答案为止。

他们不是为了使你措手不及而这样做。通常是为了看看你对此的想法：你能想出一个天真的解决方案吗（你做到了），你能说出其中的问题吗？你能想出改进它的方法，也许是在正确的方向上推动一下？你能解释如何研究更好的解决方案吗？思考过程可能比解决方案更重要。

如果面试官只是说你的解决方案很糟糕，而且你应该知道更好的解决方案（我不认为有一个关于X必须绝对了解的事情清单），那么你应该寻找更好的工作场所。

- IVlad

---

不知道这个解决方案。非常聪明 :) - Juan Lopes

值得注意的是，当 n%4==0 时，XOR[1..n] = 0；当 n%4==1 时，XOR[1..n] = n-1；当 n%4==2 时，XOR[1..n] = 1；当 n%4==3 时，XOR[1..n] = n。 - Juan Lopes

这种异或解决方案再次提醒我编程绝对是艺术与科学的结合。数字中有一定的诗意。 - WDS

Answer 2

如果您使用无符号整数，则使用公式的方法仍将有效，因为C标准为乘法和加法指定了模算术。对于n位整数，您保证得到正确的结果对2^n取模，并且由于您知道结果必须在0-2^n范围内，因此您知道它必须是正确的。

- Joni

---

你确定吗？在模运算中如何除以2？ - IVlad

没错，你需要更加小心，在乘法运算之前把 n 或者 n+1（哪个是偶数就选哪个）除以2（即在需要进行模运算之前） 。 - Joni

如果你小心地这样做（注意 (a + b) % c = (a % c + b % c) % c，同样适用于乘法，但不适用于除法：(a / b) % c != ((a % c) / (b % c)) % c)），那么这应该可以工作。如果你正在测试语言知识，我认为这比异或解决方案更有价值。 - IVlad

Answer 3

几乎所有计算机科学专业的学生都应该解决过这个问题。他的解决方案在O(n)时间和O(1)空间内运行，而你的解决方案在O(n)时间内具有更大的常数和O(n)空间。因此，他的解决方案更好是不足为奇的。

关于溢出问题。几乎任何问题都可能会出现输入溢出的情况。如果你听到问题“如何添加两个数字”，然后看到解决方案a + b，它也会遭受溢出。或者输出从输入得到的数字也会遭受溢出。

面试时一个好主意是询问你期望什么样的输入。当你提出解决方案时，你必须告诉对方你期望出现什么样的问题。我的加法运算将在和小于X的情况下工作。如果你想要更好的结果，请使用大整数算术。

P.S. 你是否考虑过当n太大时，你可能没有足够的内存来进行malloc操作？

- Salvador Dali

---

我没有点踩，但我不同意“几乎所有计算机科学专业的学生都应该解决这个问题”。这是一个需要数学知识或熟悉此类问题的问题，在许多编程工作中并不一定需要。而且据我所知，大学里也没有教这些东西。 - IVlad

@IVlad，感谢您的意见。但我认为数学知识是计算机科学专业学生应该已经具备的东西，无论是申请计算机科学专业还是在学习过程中发展。如果一个人不知道如何求1到n的和，很难想象他将如何分析qsort或dijkstra的复杂性。但我同意，很难说计算机科学专业的学生能做什么和不能做什么，这就是为什么我加了“几乎”的原因。这意味着在100个计算机科学专业的人中，我希望有90个人知道它，并且认为有10个人还没有准备好去工作。 - Salvador Dali

我认为这不一定是不知道这些东西的问题，而是识别出它们在问题中的需要并将它们组合起来的问题。有人可能知道什么是异或，但我敢打赌，大多数知道异或的人如果以前没有听说过异或解决方案，他们不会想到使用异或。了解各个元素是一回事，能够告诉它们可以应用于给定问题是另一回事。对于后者，您需要了解这种类型的问题，并且据我所知，这种知识在正式的计算机科学研究中并没有真正得到发展。 - IVlad

Answer 4

这是一个数学问题，而不是编程问题。我不确定计算机科学专业是否需要学习包括级数在内的数学课程，如果没有，那么程序员是否遇到过这个问题就有些随机了。还有其他一些级数，比如幂级数，它们是许多数学系列的一部分http://en.wikipedia.org/wiki/List_of_mathematical_series。

这些问题从什么时候开始不再是编程问题，而是数学问题呢？

- rcgldr