要求在工作面试中解决NP完整问题是正确的吗？ [关闭
https://stackoverflow.com/questions/1724673
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解决方案
对我来说是完全合法的。如果您是计算机科学专业人员，那么您可以非正式地争论为什么问题似乎很困难，或者（甚至更好）从已知的NP硬性问题中减少了草图。
许多现实世界中的问题最终结果是NP-HARD，而Stackoverflow也会有问题地质疑问题的复杂性，这是一个困难的问题（例如，NP-Hard）。它是CS专业人员工具箱的重要组成部分，能够识别并争论已知难以解决的问题。
其他提示
我看不到这样的问题。同样，不应期望程序员通过死记硬背识别NP完整问题。但是，他们应该能够识别出其算法可能会缓慢，而不管给定的问题是否为NP完成。
当然，为什么不呢？ NP完整并不意味着无法解决，这只是意味着您的解决方案会很慢。您可能正在寻找候选人是否会选择蛮力解决方案，或者尝试动态编程解决方案。这种类型的问题可能会导致有关运行时和其他有用理论的问题。
在某些国家，有一类采访问题是非法的，通常与雇主业务无关的个人细节。除此之外，如果面试官认为这将有助于了解受访者的能力，那么任何问题都是公平的游戏！
如果您要雇用一个需要思考者而不是仅仅是代码猴子的职位，则将这种问题提交给申请人可能很有用。谁在乎问题是否“众所周知”是NP？如果这个家伙很好，他将在分析问题时了解到这种理解。这很可能是面试官想要看到的结果，或者申请人可以继续进行更多的预分析，并描述他如何违反问题的问题，或者他认为可以使用哪些优化来使其更加易于管理。
我没有看到这个问题，但是我在一般情况下会质疑这些问题的有用性。
作为面试官，提出这样的问题的好处是查看该人如何解决问题以及他们的想法。如果您告诉他们说出来，您可以找到很多有关他们将如何处理困难问题的信息。
话虽如此，在采访中，大多数人都不处于最佳状态 - 因此，像这样的东西经常过分杀人，而扔出一些“棘手”。
我认为问一个问题您知道受访者不知道答案是有效的。
每个人都遇到他们不知道答案的问题。这种类型的问题将使您了解受访者的内部流程是什么。如果他们从逻辑上结束事情并开始制定正确的答案，即使它不是最好的动态编程算法，它也表明他们可以很好地推理并发现答案。
另外，由于他们可能不了解问题，因此这种问题使您可以看到受访者对寻求帮助或澄清的舒适性。
我认为回答此类问题的最佳方法是询问是否缺少或不知道某些东西，然后假设答案，指出您为什么认为这是正确的，以及为什么它可能不是最好的解决方案。
最好问一个难以回答的问题，看看程序员如何通过问题出现。
但这完全取决于面试官如何提出问题，并提示程序员是否不是数学天才（即了解他们的推理方式，以及他们对诸如诸如“这是一个好的开始）的反应，但是什么是什么？如果...”）而不是检测它们是否自闭症并可以在4.3秒内提供最佳解决方案）。
值得记住的是，访谈是高度压力的事务，其中许多人发现这样的问题很难很好地回答 - 一个简单得多的问题通常就足够了，而不会使受访者承受不必要的压力/压力。
如果您这样做是故意尝试看看他们如何应对压力只是愚蠢的 - 那不是程序员在工作中必须应对的压力，因此您不会测试任何值得的事情。
在不通知受访者的情况下，问几个不可能的问题是有些卑鄙的，但是在观察到的问题解决时，通常会问这个问题，以便您可以演示批判性思维技能，如何解决问题以及如何处理压力或失败。
我被问到我无法解决的采访问题，而且我认为我从来没有“失败”采访。
在面试中询问如何分解数字是否公平？
众所周知，这是NP-C，但没有多项式时间解决方案[*]，因此当然不知道它在P中。
我认为我的问题和原始问题的答案是“是”，出于同样的原因。有些问题没有解决方案，可以很好地缩放，但是无论如何都需要解决某些输入。如果您需要可以解决此类问题的程序员，那么有一个很好的方法可以让他们在面试中证明这一点，那就是将他们推销，看看他们是否吓坏了。
如果有人声称具有COMPSCI背景，那么他们甚至应该能够按需为某些NP-C问题提供良好的解决方案，例如通过动态编程解决背包问题。我认为这是毫无意义的，要求申请人以编程工作来解决他们从未见过的问题，并实际证明了NP核算（例如，将背包简化为指定的问题）。您每家公司都不需要太多的程序员可以做到这一点（通常为0），您可能会发现的是，候选人在尝试更改主题并在面试时间中做更有价值的事情要持续了多长时间。 ..
*]在位的输入大小中的多项式，也就是说。您经常会看到人们讨论整数问题的算法复杂性，例如因输入所示的数量的大小，例如“ sqrt（n）试验部”。但这不是定义NP和NP-C的方式。
不，这是不礼貌的，这是面试官喜欢处于权力的迹象。哈哈，牡丹！我知道答案，你不知道！男孩，我喜欢让你蠕动试图提出它！
关于唯一的唯一途径，它甚至可以稍有有效，因为它是一个有用的访谈问题，它是一个众所周知的问题，还是一个显然是NP完整的问题，并以鼓励讨论可行性的方式进行询问。
在面试中将NP完整问题作为编程挑战没有错。我只看到在面试中找到问题的多项式时间解决方案时，我只会发现有问题。
面试官应该想看看候选人如何处理各种情况，包括候选人找不到简单解决方案的情况。 “不可能”的问题表明，当没有简单的解决方案时，候选人的反应如何。候选人只是放弃吗？候选人搜索几次不同的尝试？解决方案尝试了多远？候选人什么时候寻求帮助？候选人是否抱怨问题“不公平”？
简而言之，这样的采访问题不是要解决P = NP ...这是一个心理答案。
如果在面试之前提出了这样的问题（请在面试中回答），我会说可以。但是，要解决一个困难的问题，任何程序员绝对不会做得很好，并且如果程序员做得很好，那就意味着他们可以当场采取行动（这并不总是为编程的最好的事情，因为设计事物需要花费时间并检查所有可能的缺陷），或者以前看过类似的问题。
编辑：或可能讨论问题是好的，例如说制定一个行动计划，无论您是否完全解决了它。.讨论如何可行以及是否有一种快速（但困难）做到这一点的方法。我不会说受访者必须在面试中写下50行C代码以解决它
那是邪恶的！
如果访调员在访调员中问一个NP完整的问题，他们可以合理地期望的唯一回答是，受访者回应了问题是NP完整的。在像大学家庭作业问题这样的低压力环境中，通常需要一个聪明的学生2-3或更多小时才能证明。证明本身可能需要几页来完全写出，也许是几个小时的工作本身。在像采访一样高应力的环境中，您可以期望受访者甚至可能不认识到这是NP的完整。
唯一合理的选择是受访者产生近似算法。但是，在这种情况下，面试官应该做到这一点 明确 清楚他们是 美好的 与近似。
即便如此，大多数近似值仅带有2个正确答案的订单。
我猜还有另外1个替代方法：受访者建议搜索型算法也许最合适（例如，以NP完整的整数域优化问题为例，大多数近似算法都使用分支和绑定的搜索旋转算法产生不错的结果。）
我更喜欢要求他们证明p！= np或p == np。总有一天，候选人会回答，我会窃取他们的答案并出名！
不过，我认为这是完全公平的。大多数NP完整问题很容易解决，它们的运行非常缓慢。但是，除非工作要求他们对复杂性理论有很多了解，否则他们需要证明的只是他们了解解决方案会很慢。如果他们知道这是非多项式时间的奖励点，如果他们知道NP完成了，那么金星。
