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

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溢出？

Answer 1

实际上,采访者提出的解决方案会遭遇溢出.事实上,有一个更好的解决方案,没有溢出,如果你建议总结,面试官可能会跟进.

更好的解决方案更不直观,但据我所知,它现在已经非常有名.

它依赖于以下内容:

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

因此,更好的解决方案是计算所有给定数字的xor,然后使用x的所​​有数字xor 1来计算n.出现在数组中的那些将取消来自1to的那些n.失踪者将继续存在.

至于如何考虑这样的解决方案,没有配方.你只需要熟悉这些挑战/面试问题,并接受一些计算机科学和数学方面的培训.

不要因为没有得到它而感到太糟糕.如果我在完成大学之前没有看到问题,我几乎肯定不会在面试环境中得到总和解决方案(我可能最终在我自己的时间内弄清楚了)并且我绝对不会想出xor解决方案没有先看到它.这类问题非常受欢迎.如果它是一个打击,他们可能会问别的东西,直到你不知道答案.

他们不这样做是为了让你措手不及.他们这样做是为了看你如何看待它,通常:你能想出一个天真的解决方案(你做过),你能告诉它有什么问题吗？你能想出改善它的方法吗？也许是朝着正确的方向努力？你能解释一下如何研究更好的解决方案吗？思考过程可能比解决方案更重要.

如果所有的面试官都说你的解决方案很糟糕而且你应该知道更好的解决方案(我不认为在完成X专业后你必须完全了解X的事项清单),你应该寻找更好的解决方案工作的地方.