今天有一个关于 SO 的问题，作者在一次采访中被提出了一个 NP 完全问题，他显然没有被告知这是一个问题。
问这些问题的目的是什么？当问这样的问题时，面试官期望什么行为？证明？有用的启发式方法？问一个人是否不是每个人都应该知道的众所周知的 NP 完全问题是否合理？（有很多）
问问题
4412 次
14 回答
16
对我来说完全合法。如果您是计算机科学专业人士，那么您很有可能可以非正式地争论为什么这个问题看起来很难，或者（甚至更好）提供一个从已知 NP-hard 问题中简化的草图。
许多现实世界的问题最终被证明是 NP 难的，而且 stackoverflow 也时不时地对问题的复杂性提出疑问，而这最终证明是一个困难的问题（例如，NP 难）。能够识别和争论已知难以解决的问题是 CS 专业人员工具箱的重要组成部分。
于 2009-11-12T19:26:04.073 回答
10
我认为问这样的问题没有任何问题。此外，不应期望程序员死记硬背地识别 NP 完全问题。然而，无论给定问题是否是 NP 完全问题，他们都应该能够识别出他们的算法可能很慢。
于 2009-11-12T19:22:26.683 回答
8
当然，为什么不呢？NP-complete 并不意味着无法解决，它只是意味着您的解决方案会很慢。您可能正在寻找候选人是否会选择蛮力解决方案，或者尝试动态编程解决方案。这类问题可能会引发关于运行时和其他有用理论的问题。
于 2009-11-12T19:25:05.633 回答
8
在某些国家/地区，有一类面试问题是非法的，通常涉及与雇主无关的个人详细信息。除此之外，如果面试官认为这有助于了解受访者的能力，任何问题都是公平的游戏！
如果您正在招聘一个需要思想家而不仅仅是代码猴子的职位，那么向申请人提出此类问题可能会很有用。谁在乎一个问题是否“众所周知”是 NP？如果这个人很好，他会在分析问题时得出那种理解。这很可能是面试官希望看到的结果，或者申请人可以继续进行更多的预分析并描述他将如何暴力破解问题，或者他可以考虑应用哪些优化以使其更易于管理.
于 2009-11-12T19:26:27.223 回答
5
问一个很难回答的问题，看看程序员是如何解决问题的，这很好。
但这一切都取决于面试官如何提出问题，如果程序员不是数学天才，他们会提示他们找到解决方案（即看看他们如何推理，以及他们如何对诸如“这是一个好的开始，但是什么如果...”）而不是检测他们是否患有自闭症并可以在 4.3 秒内提供最佳解决方案）。
值得记住的是，面试是压力很大的事情，很多人发现这样的问题很难很好地回答——一个简单得多的问题通常就足够了，而不会让被面试者承受过大的压力/压力。
如果您这样做是为了故意尝试了解他们如何应对压力，那是愚蠢的-这不是程序员在工作中必须应对的那种压力，因此您没有测试任何有价值的东西。
于 2009-11-12T20:04:50.360 回答
4
我认为问一个你知道受访者不知道答案的问题是有效的。
每个人都会遇到他们不知道答案的问题。这类问题会让你深入了解受访者的内部流程。如果他们在逻辑上得出结论并开始制定正确的答案，即使它不是最好的动态规划算法，也表明他们可以很好地推理并找到答案。
此外，由于他们可能对问题一无所知，因此此类问题可以让您了解受访者在寻求帮助或澄清方面的自在程度。
我认为回答此类问题的最佳方法是要求澄清是否缺少某些内容或不为人所知，然后假设答案，指出您认为它是正确的原因以及为什么它可能不是最好的解决方案。
于 2009-11-12T19:26:19.720 回答
3
我不认为这有什么问题，但我确实有点质疑这类问题在一般面试中的有用性。
作为面试官，问这样的问题的好处是看到这个人如何解决问题，以及他们是如何思考的。如果您告诉他们说出来，您可以了解很多关于他们将如何解决难题的信息。
话虽如此，在接受采访时，大多数人并没有处于最佳状态——所以扔一些像这样有点“棘手”的东西通常是矫枉过正的，IMO。
于 2009-11-12T19:25:24.243 回答
3
在不通知受访者的情况下提出几乎不可能的问题有点卑鄙，但在观察到的问题解决中，经常会问这个问题，以便您可以展示批判性思维能力，如何解决问题以及如何处理压力或失败.
我被问到一些我无法解决的面试问题，而且我认为我从来没有因此而“失败”过一次面试。
于 2009-11-12T19:26:38.487 回答
2
在面试中问如何分解数字是否公平？
这不知道是 NP-C，但不知道多项式时间解 [*]，所以肯定不知道它在 P 中。
我认为我的问题和原始问题的答案都是“是”，并且出于相同的原因。有些问题没有解决方案可以很好地扩展，但对于某些输入无论如何都需要解决。如果你需要能够处理此类问题的程序员，有一个好方法可以让他们在面试中证明这一点，那就是推销他们，看看他们是否发疯。
如果有人声称有 CompSci 背景，那么他们甚至应该能够按需为某些 NP-C 问题提供良好的解决方案，例如用动态规划解决背包问题。我认为要求编程工作的申请人解决他们以前从未见过的问题并实际证明它是 NP 完全的（例如通过将背包减少到指定的问题）是毫无意义的。你不需要每个公司有很多程序员可以做到这一点（通常是 0 人），你可能会发现候选人在尝试改变主题并在面试时间做一些更有价值的事情之前坚持了多长时间。 ..
[*] 以位为单位的输入大小的多项式，即。您经常看到人们根据输入表示的数字的大小来讨论整数问题的算法复杂性，例如因式分解，例如“sqrt(N) 试除法”。但这不是 NP 和 NP-C 的定义方式。
于 2009-11-12T19:56:02.013 回答
2
不，这很粗鲁，表明面试官只是喜欢处于权力位置。哈哈，佩恩！我知道答案，而你不知道！男孩，我喜欢让你想出它来蠕动吗？
作为一个有用的面试问题，它可能甚至稍微有效的唯一方法是，它是一个众所周知的问题，还是一个在某种程度上显然是 NP 完全的问题，并且以一种鼓励讨论可行性的方式提出。
于 2009-11-12T19:23:49.037 回答
1
在面试中将 NP 完全问题作为编程挑战提出并没有错。我只看到期望在面试期间找到问题的多项式时间解决方案有问题。
面试官应该想看看候选人如何处理各种情况——包括候选人无法找到简单解决方案的情况。“不可能”的问题展示了候选人在没有简单解决方案时的反应。候选人会放弃吗？候选人搜索了多少种不同的尝试？尝试的解决方案有多深远？候选人何时寻求帮助——以及如何寻求帮助？候选人是否抱怨这个问题“不公平”？
简而言之，这样的面试问题不是要解决P=NP……这是一个心理答案。
于 2009-11-13T06:52:27.400 回答
1
那是邪恶的！
如果面试官在面试官中问一个 NP 完全问题，他们唯一可以合理地期望的回答是被采访者回答问题是 NP 完全问题的证据。在像大学家庭作业这样的低压力环境中，这通常需要一个聪明的学生 2-3 小时或更长时间来证明。证明本身可能需要几页才能完整地写出来，甚至可能需要几个小时的工作。在像面试这样的高压力环境中，您可以预期受访者甚至可能没有意识到这是 np-complete。
唯一合理的选择是被采访者产生一个近似算法；但是，在这种情况下，面试官应该明确表示他们可以接受近似值。
即便如此，大多数近似值仅带有 2 个正确答案的顺序。
我想还有另外一种选择：受访者建议搜索类型的算法可能是最合适的（例如整数域优化问题，它是 NP 完全的，大多数近似算法在单纯形上使用分支定界搜索自旋算法产生体面的结果。）
于 2009-11-12T19:28:36.063 回答
1
我更喜欢让他们证明 P != NP 或 P == NP。总有一天候选人会回答它，我会窃取他们的答案并出名！
不过，更严肃地说，我认为这是完全公平的。大多数 NP 完全问题很容易解决，只是运行速度很慢。但是，除非这项工作要求他们对复杂性理论有很多了解，否则他们需要证明的只是他们理解解决方案会很慢。如果他们知道这是非多项式时间，则加分，如果他们知道这是 NP 完整的，则获得金星。
于 2009-11-12T20:23:08.310 回答
0
如果在面试前提出这样的问题（面试时回答）我会说没关系..但是像现场解决这样一个难题绝对不是任何程序员都可以做好的，并且如果程序员做得很好，那只是意味着他们可以当场采取行动（这对于编程来说并不总是最好的事情，因为设计事物需要花费时间并检查每个可能的缺陷）或者他们以前遇到过类似的问题。
编辑：或者可能讨论这个问题会很好，比如说制定一个行动计划，无论你是否完全解决它..并讨论如何可行以及是否有快速（但困难）的方法等等。我不会说被面试者必须在面试中写下超过 50 行 C 代码才能解决它
于 2009-11-12T19:24:12.747 回答