¿Es correcto pedir resolver un problema NP-completo en una entrevista de trabajo?[cerrado]

Question

Hoy hubo un pregunta en SO, donde al autor se le presentó un problema NP completo durante una entrevista y obviamente no le habían dicho que lo era.

¿Cuál es el propósito de hacer tales preguntas?¿Qué comportamiento espera el entrevistador al preguntar este tipo de cosas?¿Prueba?¿Heurísticas útiles?¿Y es incluso legítimo preguntar si no se trata de un problema NP completo bien conocido que todo el mundo debería conocer?(hay una muchisimos)

Answer 1

completamente legítimo para mí. Si usted es profesional de Ciencias de la Computación hay una buena probabilidad de que usted puede alguno de los argumentos de manera informal por qué el problema parece ser difícil, o (mejor aún) proporcionar un bosquejo de la reducción de un problema NP-duro conocido.

Muchos de los problemas del mundo real con el tiempo llegar a ser NP-duro, y stackoverflow también tiene de vez en cuando preguntas acerca de la complejidad de un problema que resulta ser un año difícil (NP-duro, por ejemplo). Es una parte importante de una caja de herramientas profesionales de CS para ser capaz de reconocer y discutir los problemas de los que se sabe que son difíciles de resolver.

Answer 2

No veo ningún problema con pedir algo como esto. Además, no se debe esperar que los programadores de reconocer los problemas NP-completos de memoria. Deben, sin embargo, ser capaz de identificar que su algoritmo es potencialmente lenta, independientemente de si un determinado problema es NP-completo.

Answer 3

Claro, ¿por qué no? NP-completo no significa sin solución, sólo significa que su solución será lenta. Usted puede estar buscando para ver si el candidato elegirá la solución de fuerza bruta, o intentar una solución de programación dinámica. Y este tipo de pregunta puede dar lugar a preguntas sobre el tiempo de ejecución y otra teoría útil.

Answer 4

Hay una categoría de preguntas de la entrevista que son ilegales en algunos países, por lo general pertenecientes a los detalles personales que son de la incumbencia del empleador. Aparte de eso, cualquier pregunta es juego limpio si el entrevistador siente que va a ayudar a conseguir una idea de las capacidades del entrevistado!

Si está contratando para una posición que requiere de un pensador en lugar de sólo un mono código, puede ser útil para lanzar este tipo de problema en el solicitante. A quién le importa si un problema es "bien conocido" para ser NP? Si el tipo es bueno que va a venir a la comprensión de que en el análisis del problema. Que bien puede ser el resultado del entrevistador quiere ver, o el solicitante puede ir a hacer un poco más de pre-análisis y describir cómo había fuerza bruta del problema, o lo optimizaciones que se le ocurre a aplicar para que sea más manejable .

Answer 5

No veo ningún problema con esto, pero en cierto modo cuestiono la utilidad de este tipo de preguntas en las entrevistas en general.

El beneficio de hacer preguntas como esta, como entrevistador, es ver cómo la persona aborda un problema y cómo piensa.Si les dices que lo hablen, podrás descubrir bastante sobre cómo abordarán un problema difícil.

Dicho esto, durante una entrevista, la mayoría de las personas no están en su mejor momento, por lo que, en mi opinión, lanzar algo que es un tanto "complicado" como esto suele ser excesivo.

Answer 6

Creo que es válida para hacer una pregunta sabes el entrevistado no saber la respuesta a.

Todo el mundo se encuentra con problemas que no saben la respuesta. Este tipo de preguntas le dará una idea de lo que el proceso interno del entrevistado es. Si ellos llegan a la conclusión lógica y las cosas empiezan a formular una respuesta correcta, incluso si no es el mejor algoritmo de programación dinámica para ello, se demuestra que pueden razonar bien y descubrir una respuesta.

También, puesto que probablemente no lo saben todo sobre el problema, este tipo de pregunta le permite ver lo cómodo con el entrevistado es pedir ayuda o aclaración.

Creo que la mejor manera de responder a este tipo de pregunta es para pedir aclaraciones si falta algo o no bien conocido, y luego postular una respuesta, señalando por qué cree que es correcto, y por qué es probable que ISN' t la mejor solución.

Answer 7

Es bueno hacer una pregunta que es difícil de responder, para ver cómo un programador razones a través de un problema.

Pero todo depende de la forma en que el entrevistador hace la pregunta, y le indica al programador hacia una solución si no son un genio matemático (es decir, para ver la forma en que la razón, y cómo reaccionan a preguntas como "que es un buen comienzo , pero lo que si ... ") en lugar de detectar si están autista y pueden proporcionar una solución óptima en 4,3 segundos).

Vale la pena recordar que las entrevistas son asuntos altamente estresantes en la que muchas personas encuentran este tipo de preguntas difíciles de responder bien -. Una pregunta mucho más simple, será usualmente suficiente, sin poner al entrevistado bajo excesiva tensión / presión

Si lo hace deliberadamente para tratar de ver cómo se enfrentan con el estrés es simplemente estúpido - Ese no es el tipo de estrés que un programador tiene que hacer frente en su trabajo, por lo que no está probando cualquier cosa de mérito

Answer 8

Es una especie de medio de hacer preguntas casi imposibles sin informar al entrevistado de ella, pero en la resolución de problemas observados, la cuestión se pregunta a menudo para que pueda demostrar las habilidades de pensamiento crítico, cómo abordar la resolución de problemas, y cómo manejar presión o el fracaso.

Me han pedido preguntas de la entrevista no podía resolver, y no creo que he "fallido" una entrevista a causa de ella.

Answer 9

¿Es justo preguntar en una entrevista cómo factorizar números?

Eso no es conocido por ser NP-C, pero no se conoce ninguna solución en tiempo polinómico [*], por lo que ciertamente no es conocido por ser en P.

Creo que la respuesta a tanto mi pregunta y la pregunta original, es "sí", y por las mismas razones. Algunos problemas no tienen solución que escala bien, pero tienen que ser resueltos de todos modos para ciertos insumos. Si necesita programadores que pueden manejar este tipo de problemas, hay una buena manera de dejar que lo prueben en la entrevista, y eso es para lanzar uno de ellos y ver si se asustan.

Si alguien reclama un fondo CompSci, entonces deben incluso ser capaz de proporcionar buenas soluciones a ciertos problemas NP-C en la demanda, como resolver el problema de la mochila con la programación dinámica. Lo consideraría inútil pedir a un solicitante de un trabajo de programación para tener un problema que nunca han visto antes, y en realidad demostrarlo NP-completo (por ejemplo, reduciendo la mochila para el problema especificado). No es necesario que muchos programadores están por empresa que pueden hacer eso (normalmente 0), y todo lo más probable es descubrir cuánto tiempo es el candidato mantiene en ella antes de intentar cambiar el tema y hacer algo más valioso con el tiempo de la entrevista. ..

[*] polinomio en el tamaño de la entrada en bits, que es. A menudo se ve gente discutiendo la complejidad algorítmica de problemas de números enteros como la factorización en términos del tamaño del número representado por la entrada, por ejemplo, "sqrt (N) divisiones de prueba". Pero no es así como se definen NP y NP-C.

Answer 10

No, es grosero y una señal de que el entrevistador sólo le gusta estar en una posición de poder. Jaja, peón! Yo sé la respuesta, y tú no! Y chico, qué amo para que se retuercen tratando de llegar a ella!

Sobre la única forma en que podría ser incluso un poco válida como una pregunta de la entrevista útil es si se tratara de una pregunta muy conocido o uno que era de alguna manera, obviamente, NP-completo, y le preguntó de una manera que promueve la discusión de la viabilidad.

Answer 11

No hay nada malo en dar un problema NP-completo como un desafío de programación durante una entrevista. Sólo veo algo mal con la esperanza de encontrar una solución en tiempo polinomial al problema durante la entrevista.

Un entrevistador debe querer ver cómo un candidato trata de una variedad de situaciones - incluyendo situaciones que el candidato no puede encontrar una solución fácil. preguntas "imposible" muestran cómo reacciona el candidato cuando no hay una solución simple. ¿El candidato se dan por vencidos? ¿Cuántos intentos diferente que hace la búsqueda de candidatos? ¿Cómo de largo alcance se trataron las soluciones? ¿Cuándo se pide al candidato en busca de ayuda - y cómo? Se queja el candidato que el problema "no es justo"?

En resumen, una pregunta tan entrevista no se trata de resolver P = NP ... es una respuesta psicológica.

Answer 12

Si esta pregunta se le dio antes de una entrevista (que responder a una entrevista) yo diría que está bien .. pero que acaba de resolver un problema tan difícil como el que en el acto es, sin duda no va a hacer bien por cualquier programador, y si el programador no hacerlo así que simplemente significa que pueden actuar sobre el terreno (que no siempre es lo mejor para la programación como el diseño de las cosas tiene que tomar el tiempo y comprobar cualquier posible defecto) o que han visto un parecido problema antes.

Editar: O, posiblemente, la discusión sobre el problema sería bueno, como decir que se establece un plan de acción o no a resolver por completo .. y discutiendo cómo es factible y si hay una manera rápida (pero difícil) para hacerlo y tal. Yo no diría que el entrevistado debe tener para anotar más de 50 líneas de código C en una entrevista para resolverlo aunque

Answer 13

Eso es malo!

Si el entrevistador hace una pregunta NP-completo en un entrevistador la única respuesta que pueden razonablemente esperar es que el entrevistado responde con una prueba de que el problema es NP-completo. En un ambiente de bajo estrés como una pregunta preparación universitaria, esto por lo general toma un estudiante brillante 2-3 horas o más para probar. La prueba en sí mismo puede tomar varias páginas para escribir por completo, tal vez varias horas de trabajo en sí. En un entorno de alto estrés como una entrevista que se puede esperar que el entrevistado puede ni siquiera reconocen que esto es NP-completo.

La única alternativa razonable es que el entrevistado producir un algoritmo de aproximación; Sin embargo, en este caso el entrevistador debe hacer que explícitamente claro que son bien con aproximaciones.

A pesar de ello, la mayoría de las aproximaciones sólo vienen con un orden de 2 de la respuesta correcta.

Creo que hay 1 alternativa más: el entrevistado sugiere que un algoritmo de tipo de búsqueda tal vez el más adecuado (Tomemos por ejemplo el problema de optimización de enteros en el dominio que es NP-completo, la mayoría de los algoritmos de aproximación utilizan una rama y con destino giro de búsqueda en el algoritmo simplex para producir resultados aceptables.)

Answer 14

Yo los prefiero preguntar a demostrar que P! = NP o P == NP. Algún día un candidato contestará a ella, voy a robar su respuesta y ser famoso!

En una nota más seria, sin embargo, creo que es completamente justo. La mayoría de los problemas NP completos son fáciles de resolver, que sólo funcionan muy lentamente. A menos que el trabajo les obliga a saber mucho sobre teoría de la complejidad, sin embargo, todo lo que necesitan para demostrar que entienden es la solución será lenta. Los puntos de bonificación si saben que es hora no es un polinomio, estrella del oro, si saben que es NP completo.