Est-il correct de demander de résoudre un problème NP-complet sur un entretien d'embauche? [fermé]

Question

Aujourd'hui, il y avait un question sur le SO, où l'auteur a eu un problème NP-complet lors d'une interview et il avait évidemment pas été dit qu'il était l'un.

Quel est le but de poser de telles questions? Quel comportement attendre l'intervieweur lorsque vous demandez des choses? Preuve? heuristiques utiles? Et est de demander un encore légitime si elle est pas tout le monde problème NP-complet bien connu devrait connaître? (Il y a un beaucoup d'entre eux )

Answer 1

tout à fait légitime pour moi. Si vous êtes professionnel Informatique il y a de bonnes chances que vous pouvez l'un des arguments de façon informelle pourquoi le problème semble être difficile, ou (encore mieux) fournir une esquisse de réduction d'un problème NP-dur connu.

De nombreux problèmes du monde réel finit par se révéler NP-dur, et stackoverflow a aussi maintenant et puis des questions sur la complexité d'un problème qui se révèle être un (par exemple NP-dur,) difficile. Il est une partie importante d'une boîte à outils professionnels CS pour être en mesure de reconnaître et de faire valoir des problèmes qui sont connus pour être difficiles à résoudre.

Answer 2

Je ne vois aucun problème à demander quelque chose comme ça. En outre, les programmeurs ne devraient pas avoir à reconnaître les problèmes NP-complets par cœur. Cependant, ils devraient être en mesure d'identifier que leur algorithme est potentiellement lent que ce soit un problème donné est NP-complet.

Answer 3

Bien sûr, pourquoi pas? NP-complet ne signifie pas sans solution, cela signifie juste que votre solution sera lente. Vous pouvez chercher à voir si le candidat choisira la solution la force brute, ou d'essayer une solution de programmation dynamique. Et ce genre de question peut conduire à des questions au sujet de l'exécution et autre théorie utile.

Answer 4

Il y a une catégorie de questions d'entrevue qui sont illégales dans certains pays, se rapportant généralement aux données personnelles qui ne sont pas des activités de l'employeur. Cela mis à part, toute question est un jeu équitable si l'enquêteur estime qu'il va aider à avoir une idée des capacités de la personne interrogée!

Si vous embauchez un poste qui demande un penseur plutôt qu'un singe de code, il peut être utile de jeter ce genre de problème au demandeur. Qui se soucie si un problème est « bien connu » être NP? Si le gars est bon, il va venir à cette compréhension dans l'analyse du problème. Cela pourrait bien être le résultat que l'intervieweur veut voir, ou le demandeur peut aller faire un peu plus avant l'analyse et de décrire la façon dont il avait la force brutale du problème, ou ce que les optimisations qu'il peut penser à appliquer pour le rendre plus facile à gérer .

Answer 5

Je ne vois pas de problème avec cela, mais je ne doute un peu l'utilité de ce genre de questions dans des interviews en général.

L'avantage de poser des questions comme celle-ci, comme un enquêteur, est de voir comment la personne se rapproche d'un problème, et comment ils pensent. Si vous leur dites d'en parler, vous pouvez en savoir un peu sur la façon dont ils aborderont un problème difficile.

Cela étant dit, au cours d'une entrevue, la plupart des gens ne sont pas à leur meilleur -. Afin de jeter quelque chose qui est un peu « difficile » comme celui-ci est souvent surpuissant, l'OMI

Answer 6

Je pense qu'il est valable de poser une question que vous connaissez la personne interrogée ne saura pas la réponse.

Tout le monde rencontre des problèmes qu'ils ne savent pas la réponse. Ce type de question vous donnera un aperçu de ce processus interne de la personne interrogée est. S'ils concluent logiquement les choses et commencent à formuler une réponse correcte, même si ce n'est pas le meilleur algorithme de programmation dynamique, il montre qu'ils peuvent bien raisonner et découvrir une réponse.

En outre, étant donné qu'ils ne savent probablement pas tout le problème, ce genre de question vous permet de voir comment l'aise la personne interrogée est à demander de l'aide ou des éclaircissements.

Je pense que la meilleure façon de répondre à ce type de question est de demander des éclaircissements si quelque chose est manquant ou mal connu, et postulent alors une réponse, indiquant pourquoi vous pensez qu'il est correct, et pourquoi il ISN probable » t la meilleure solution.

Answer 7

Il est bon de poser une question qui est difficile de répondre, de voir comment une des raisons de programmeur par un problème.

Mais tout dépend de la façon dont l'intervieweur pose la question, et invite le programmeur vers une solution si elles ne sont pas un génie mathématique (c.-à-voir comment ils raisonnent, et comment ils réagissent aux questions comme « qui est un bon début , mais si ... ») plutôt que de détecter si elles sont autistes et peuvent fournir une solution optimale en 4,3 secondes).

Il faut se rappeler que les entrevues sont des affaires très stressantes où beaucoup de gens trouvent ces questions très difficiles à répondre bien -. Beaucoup plus simple question habituellement suffisante sans mettre la personne interrogée sous une contrainte excessive / pression

Si vous le faites pour essayer délibérément de voir comment ils composer avec le stress est tout simplement stupide - qui est pas le genre de stress programmeur doit faire face à leur emploi, de sorte que vous n'êtes pas tester quoi que ce soit utile

Answer 8

Il est méchant genre de poser des questions proche-impossible sans en informer la personne interrogée de celui-ci, mais dans la résolution des problèmes observés, la question est souvent posée afin que vous puissiez démontrer l'esprit critique, votre approche de résolution de problèmes et la façon dont vous gérer pression ou d'échec.

J'ai posé des questions d'entrevue, je ne pouvais pas résoudre, et je ne pense pas que j'ai jamais « a échoué » une interview à cause de cela.

Answer 9

Est-il juste de demander dans une interview comment factoriser des nombres?

Ce n'est pas connu pour être NP-C, mais pas de solution polynomial [*] est connu, il est donc certainement pas connu pour être dans P.

Je pense que la réponse à la fois ma question, et la question initiale, est « oui », et pour les mêmes raisons. Certains problèmes ont pas de solution qui adapte bien, mais ne doivent être résolus de toute façon pour certaines entrées. Si vous avez besoin de programmeurs qui peuvent gérer ces problèmes, il y a une bonne façon de leur faire le prouver dans une interview, et c'est de les planter un et voir si elles paniquent.

Si quelqu'un prétend un fond CompSci, alors ils devraient même être en mesure de fournir de bonnes solutions à certains problèmes NP-C sur la demande, tels que la résolution du problème de la programmation dynamique havresac. Je considère inutile de demander à un candidat à un emploi de programmation prendre un problème qu'ils ont jamais vu auparavant, et de prouver réellement NP-complet (par exemple en réduisant havresac au problème spécifié). Vous n'avez pas besoin de très nombreux programmeurs par entreprise qui peut le faire (généralement 0), et tout ce que vous allez probablement découvrir est combien de temps le candidat garde à elle avant de tenter de changer le sujet et faire quelque chose de plus précieux avec le temps de l'entrevue. ..

[*] polynomial dans la taille de l'entrée en bits, qui est. Vous voyez souvent les gens à discuter de la complexité algorithmique des problèmes entiers comme factorisation en fonction de la taille du nombre représenté par l'entrée, par exemple "divisions d'essai sqrt (N)". Mais ce n'est pas comment NP et NP-C sont définies.

Answer 10

Non, il est grossier et un signe que l'intervieweur aime juste être dans une position de pouvoir. Haha, péon! Je connais la réponse, et vous ne! Et le garçon, que j'aime vous faire tortiller essayer de trouver avec elle!

A propos de la seule façon dont il pourrait être même un peu valable comme une question d'entrevue utile est si elle était une question ou qui était en quelque sorte de toute évidence NP-complet bien connu, et a demandé d'une manière qui a encouragé la discussion de faisabilité.

Answer 11

Il n'y a rien de mal à donner un problème NP-complet comme un défi de programmation lors d'une interview. Je ne vois que quelque chose de mal avec attendant de trouver une solution polynomial au problème lors de l'entrevue.

Un enquêteur doit vouloir voir comment un traite de candidats avec une variété de situations - y compris les situations que le candidat ne peut pas trouver une solution facile à. des questions « Impossible » montrent comment le candidat réagit quand il n'y a pas de solution simple. Est-ce que le candidat tout simplement abandonner? Combien de différentes tentatives fait la recherche de candidats? Dans quelle mesure sont portée les solutions testées? Quand le candidat demander de l'aide - et comment? Le candidat se plaint que le problème « est pas juste »?

En bref, une telle question d'entrevue n'est pas sur la résolution P = NP ... c'est une réponse psychologique.

Answer 12

Si une telle question a été donnée avant une entrevue (à répondre à une interview) Je dirais que c'est ok .. mais de résoudre un tel problème difficile que sur place est certainement ne va pas être bien fait par tout programmeur, et si le programmeur ne fait bien que cela signifie juste qu'ils peuvent agir sur place (qui ne sont pas toujours la meilleure chose pour la programmation que la conception des choses a besoin de prendre du temps et de vérifier tous les défauts possibles) ou qu'ils ont vu un semblable problème avant.

Edit: Ou peut-être la discussion sur le problème serait bon, comme dire établissant un plan d'action que vous résoudre complètement ou non .. et de discuter la faisabilité et s'il y a un moyen rapide (mais difficile) façon de le faire et tel. Je ne dirais pas que la personne interrogée devrait avoir à écrire plus de 50 lignes de code C dans une interview pour le résoudre si

Answer 13

C'est le mal!

Si l'intervieweur pose une question NP-complet dans un enquêteur la seule réponse qu'ils peuvent raisonnablement espérer est que la personne interrogée répond avec une preuve que le problème est NP-complet. Dans un environnement à faible stress comme une question de devoirs universitaires, cela prend généralement un brillant étudiant 2-3 heures ou plus à prouver. La preuve elle-même peut prendre plusieurs pages pour écrire complètement, peut-être plusieurs heures de travail lui-même. Dans un environnement de stress élevé comme une interview que vous pouvez attendre que la personne interrogée ne peut pas reconnaître même que ce np-complet.

La seule alternative raisonnable est que la personne interrogée de produire un algorithme d'approximation; Cependant, dans ce cas, l'intervieweur doit explicitement clair qu'ils sont fin avec des approximations.

Même si, la plupart des approximations viennent seulement avec un ordre de 2 de la réponse correcte.

Je crois qu'il ya une alternative plus: la personne interrogée suggère qu'un algorithme de type de recherche peut-être le plus approprié (prendre par exemple le problème d'optimisation domaine entier qui est NP-complet, la plupart des algorithmes d'approximation utilisent une branche et de spin de recherche liée sur l'algorithme simplex pour produire des résultats décents.)

Answer 14

Je préfère leur demander de prouver que P! = NP ou P == NP. Un jour un candidat répondra, je volerai leur réponse et être célèbre!

Sur une note plus grave, cependant, je pense qu'il est tout à fait juste. La plupart des problèmes NP complets sont faciles à résoudre, ils courent juste très lentement. À moins que le travail les oblige à connaître beaucoup de choses sur la théorie de la complexité, cependant, tout ce qu'ils doivent démontrer est qu'ils comprennent la solution sera lente. Les points de bonus s'ils savent qu'il est temps non polynomiale, étoile d'or si elles savent que c'est NP complet.