在工作面试中要求解决NP完全问题正确吗?[闭门]

对我来说完全合法。如果你是计算机科学专业人士,你很有可能会非正式地论证问题看起来很难的原因,或者(甚至更好)提供一个已知NP难问题的简化草图。

许多现实世界中的问题最终证明是NP难的,stackoverflow有时也会问一些关于问题复杂性的问题,这些问题最终证明是困难的(例如NP难)。它是CS专业人员工具箱的重要组成部分,能够识别和辩论已知难以解决的问题。

我觉得这样问没什么问题。同样,程序员也不应该死记硬背地认识NP完全问题。然而,无论给定的问题是否是NP完全问题,他们都应该能够确定他们的算法可能很慢。

当然,为什么不呢?NP完全并不意味着不可解,它只是意味着你的解会很慢。您可能希望了解候选人是否会选择暴力解决方案,或者尝试动态编程解决方案。这种类型的问题可能导致关于运行时和其他有用理论的问题。

在某些国家,有一类面试问题是非法的,通常涉及与雇主无关的个人细节。除此之外,如果面试官认为任何问题都有助于了解被面试者的能力,那么任何问题都是公平的!

如果你正在招聘一个需要思考者而不仅仅是一个代码猴子的职位,那么向应聘者提出这样的问题可能会很有用。谁在乎一个问题是否“众所周知”是NP?如果这个人很好,他在分析问题时就会有这样的理解。这很可能是面试官想要看到的结果,或者应聘者可以继续做更多的预分析,并描述他将如何强行解决问题,或者他可以考虑采取哪些优化措施使问题更易于管理。

但这一切都取决于面试官如何提问,并在程序员不是数学天才时提示他们寻求解决方案(即,看看他们如何推理,以及他们对“这是一个好的开始,但如果……”等问题的反应),而不是检测他们是否患有自闭症,并能在4.3秒内提供最佳解决方案)。

如果你这样做是为了故意看看他们是如何处理压力的,那就太愚蠢了——这不是程序员在工作中必须处理的那种压力,所以你没有测试任何有价值的东西。

我认为问一个你知道受访者不知道答案的问题是有道理的。

此外,由于他们可能并不完全了解问题,这类问题可以让你看到受访者在寻求帮助或澄清时有多自在。

我认为回答这类问题的最好方法是,如果有什么东西缺失或不为人所知,请澄清,然后假设一个答案,指出为什么你认为它是正确的,为什么它可能不是最好的解决方案。

我不认为这有什么问题,但我确实有点怀疑这些问题在一般面试中的有用性。

作为一名面试官,提出这样的问题的好处在于了解这个人是如何处理问题的,以及他们是如何思考的。如果你让他们说出来,你会发现他们将如何解决一个难题。

话虽如此,在一次采访中,大多数人都不是处于最佳状态,所以在我看来,扔一些像这样有点“棘手”的东西往往是矫枉过正。

在不通知受访者的情况下问几乎不可能的问题有点意思,但在观察到的问题解决过程中,经常会问这个问题,这样你就可以展示批判性思维技能,如何解决问题,以及如何应对压力或失败。

有人问过我无法解决的面试问题,我想我从来没有因为它而“失败”过面试。

作为一个有用的面试问题,它可能稍微有效的唯一方法是,如果它是一个众所周知的问题,或者是一个明显的NP完全问题,并且以一种鼓励讨论可行性的方式提问。

在面试中询问如何分解数字公平吗?

这不是已知的NP-C,但没有已知的多项式时间解[*],所以肯定不知道它在P中。

如果有人声称有CompSci背景,那么他们甚至应该能够根据需要为某些NP-C问题提供良好的解决方案,例如使用动态规划解决背包问题。我认为找一个程序员做一个以前从未遇到过的问题是毫无意义的,并且实际上证明它是NP-完全的(例如通过减少背包到指定的问题)。每个公司不需要太多程序员(通常为0人)就能做到这一点,而你可能会发现应聘者在试图改变话题、利用面试时间做一些更有价值的事情之前会坚持多久。。。

那是邪恶的!

唯一合理的选择是受访者产生一个近似算法;然而,在这种情况下,面试官应该做到这一点 明确地 很明显他们是 用近似法。

即使如此,大多数近似值也只有正确答案的2个数量级。

简而言之,这样的面试问题不是关于解决P=NP。。。这是心理上的回答。

我更喜欢让他们证明P!=NP或P==NP。总有一天一个候选人会回答这个问题,我会偷他们的答案,然后出名!

不过,更严肃地说,我认为这是完全公平的。大多数NP完全问题很容易解决,它们只是运行得很慢。除非这项工作要求他们对复杂性理论有很多了解,否则他们需要证明的是,他们明白解决方案的速度会很慢。如果他们知道这是非多项式时间,就可以获得额外的分数;如果他们知道这是NP完全时间,就可以获得金星奖。

如果这样一个问题是在面试前提出的(面试时回答),我会说没关系。。但是,仅仅当场解决这样一个困难的问题肯定不会被任何程序员做好,如果程序员做得好,那就意味着他们可以当场行动(这对编程来说并不总是最好的事情,因为设计东西需要花时间并检查每一个可能的缺陷)或者他们以前也见过类似的问题。

编辑: 或者,关于这个问题的讨论可能会很好,比如说制定一个行动计划,不管你是否完全解决了它。。并讨论如何可行以及是否有一种快速(但困难)的方法来实现这一目标等等。不过,我不会说被采访者必须在采访中写下50多行C代码才能解决这个问题