这个现代编程面试挑战的解决方案不可靠吗？
Is this modern programming interview challenge's solution unreliable?
所以我没有通过类似
的编程面试问题
"Given an array of ints 1, 2, ..., n with one of them missing, find
the missing one."
面试官说正确答案是对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);
这不像 "cool" 我承认我从未想过要尝试的求和解决方案。
首先，求和法有没有溢出的危险？我的意思是，如果 arr 包含 ~((int)0) 和 ~((int)0) - 1 怎么办？那么arr[0] + arr[1] + ... + arr[n-1]不会溢出吗？还是由于 1 + 2 + ... + n 也溢出，解决方案仍然有效？
的确，面试官提出的方案会溢出。事实上，有一个更好的解决方案，不会受到溢出的影响，如果你建议求和，面试官可能会跟进。
更好的解决方案不那么直观，但据我所知，它现在已经广为人知。
它依赖于以下内容：
x xor y = y xor x
x xor 0 = x
x xor x = 0
所以更好的解决方案是计算所有给定数字的异或，然后将其与从 1 到 n 的所有数字的异或进行异或。出现在您的数组中的那些将与 1 到 n 中的那些抵消。丢失的那个会留下来。
至于如何思考这样的解决方案，没有秘诀。你只需要熟悉这样的挑战/面试问题，并接受过一些计算机科学和数学方面的培训。
不要因为没有得到它而难过。如果我在大学毕业之前没有看到这个问题，我几乎肯定不会在面试环境中得到求和解决方案（我最终可能会在我自己的时间弄清楚）而且我绝对不会想出 xor没有先看到它的解决方案。这些问题几乎是偶然的。如果成功了，他们可能会问其他问题，直到您不知道答案为止。
他们这样做不是为了让你措手不及。他们这样做是为了看看你是怎么想的，通常是：你能想出一个天真的解决方案吗（你做到了），你能说出它有什么问题吗？你能想出改进它的方法吗，也许是朝着正确的方向推动？你能解释一下你将如何研究更好的解决方案吗？思考过程可能比解决方案更重要。
如果面试官只说你的解决方案不好，而你应该知道更好的解决方案（我认为没有你必须绝对了解的清单X专业毕业后X），你应该找一个更好的工作地方。
如果您使用无符号整数，使用公式的方法仍然有效，因为 C 标准指定了乘法和加法的模运算。使用 n 位整数，您可以保证得到正确的结果模 2^n，并且由于您知道结果必须在 0-2^n 范围内，所以您知道它一定是正确的。
几乎所有计算机科学专业的学生都应该已经解决了它。他的解决方案在 O(n) 时间和 O(1) space 内运行，您的解决方案在 O(n) 时间内运行，常数更大，O(n) space。所以他的方案更好也就不足为奇了。
关于溢出。几乎对于任何问题，您都可以想出会溢出的输入。如果听到题目"how to add two numbers"，再看到解法a+b，同样会溢出。或者输出你从输入中得到的数字也会溢出。
面试中的一个好主意是询问您期望什么样的输入。当你提出解决方案时，你必须告诉你会遇到什么样的问题。如果总和小于 X，我的两个数字相加将起作用。如果你想要更好，请使用 big int 算术。
P.S.你有没有想过当数字n太大时，你可能没有足够的内存来进行malloc操作？
这是一道数学题，不是编程题。我不确定计算机科学专业的学生是否参加了包括系列的数学课程，如果没有，那么如果程序员以前遇到过这种情况，那就有点随机了。许多 http://en.wikipedia.org/wiki/List_of_mathematical_series.
中还有其他系列，例如幂级数
这些问题在什么时候不再是编程问题和数学问题？
所以我没有通过类似
的编程面试问题"Given an array of ints 1, 2, ..., n with one of them missing, find the missing one."
面试官说正确答案是对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);
这不像 "cool" 我承认我从未想过要尝试的求和解决方案。
首先，求和法有没有溢出的危险？我的意思是，如果 arr 包含 ~((int)0) 和 ~((int)0) - 1 怎么办？那么arr[0] + arr[1] + ... + arr[n-1]不会溢出吗？还是由于 1 + 2 + ... + n 也溢出，解决方案仍然有效？
的确，面试官提出的方案会溢出。事实上，有一个更好的解决方案，不会受到溢出的影响，如果你建议求和，面试官可能会跟进。
更好的解决方案不那么直观，但据我所知，它现在已经广为人知。
它依赖于以下内容：
x xor y = y xor x
x xor 0 = x
x xor x = 0
所以更好的解决方案是计算所有给定数字的异或，然后将其与从 1 到 n 的所有数字的异或进行异或。出现在您的数组中的那些将与 1 到 n 中的那些抵消。丢失的那个会留下来。
至于如何思考这样的解决方案，没有秘诀。你只需要熟悉这样的挑战/面试问题，并接受过一些计算机科学和数学方面的培训。
不要因为没有得到它而难过。如果我在大学毕业之前没有看到这个问题，我几乎肯定不会在面试环境中得到求和解决方案（我最终可能会在我自己的时间弄清楚）而且我绝对不会想出 xor没有先看到它的解决方案。这些问题几乎是偶然的。如果成功了，他们可能会问其他问题，直到您不知道答案为止。
他们这样做不是为了让你措手不及。他们这样做是为了看看你是怎么想的，通常是：你能想出一个天真的解决方案吗（你做到了），你能说出它有什么问题吗？你能想出改进它的方法吗，也许是朝着正确的方向推动？你能解释一下你将如何研究更好的解决方案吗？思考过程可能比解决方案更重要。
如果面试官只说你的解决方案不好，而你应该知道更好的解决方案（我认为没有你必须绝对了解的清单X专业毕业后X），你应该找一个更好的工作地方。
如果您使用无符号整数，使用公式的方法仍然有效，因为 C 标准指定了乘法和加法的模运算。使用 n 位整数，您可以保证得到正确的结果模 2^n，并且由于您知道结果必须在 0-2^n 范围内，所以您知道它一定是正确的。
几乎所有计算机科学专业的学生都应该已经解决了它。他的解决方案在 O(n) 时间和 O(1) space 内运行，您的解决方案在 O(n) 时间内运行，常数更大，O(n) space。所以他的方案更好也就不足为奇了。
关于溢出。几乎对于任何问题，您都可以想出会溢出的输入。如果听到题目"how to add two numbers"，再看到解法a+b，同样会溢出。或者输出你从输入中得到的数字也会溢出。
面试中的一个好主意是询问您期望什么样的输入。当你提出解决方案时，你必须告诉你会遇到什么样的问题。如果总和小于 X，我的两个数字相加将起作用。如果你想要更好，请使用 big int 算术。
P.S.你有没有想过当数字n太大时，你可能没有足够的内存来进行malloc操作？
这是一道数学题，不是编程题。我不确定计算机科学专业的学生是否参加了包括系列的数学课程，如果没有，那么如果程序员以前遇到过这种情况，那就有点随机了。许多 http://en.wikipedia.org/wiki/List_of_mathematical_series.
中还有其他系列，例如幂级数这些问题在什么时候不再是编程问题和数学问题？