algorithm - tiempo - ¿Es correcto pedir resolver un problema de NP-completo en una entrevista de trabajo?
tiempo polinomial (14)
Hoy hubo una question sobre SO, donde al autor se le dio un problema NP-completo durante una entrevista y obviamente no le habían dicho que era una.
¿Cuál es el propósito de hacer tales preguntas? ¿Qué comportamiento espera el entrevistador cuando pregunta tales cosas? ¿Prueba? ¿Heurísticas útiles? ¿Y es incluso legítimo preguntarle a uno si no es un problema NP-completo bien conocido que todos deberían conocer? (hay un montón de ellos )
¿Es justo preguntar en una entrevista cómo factorizar números?
No se sabe que sea NP-C, pero no se conoce ninguna solución de tiempo polinomial [*], por lo que ciertamente no se sabe que esté en P.
Creo que la respuesta tanto a mi pregunta como a la pregunta original es "sí", y por las mismas razones. Algunos problemas no tienen una solución que se escale bien, pero deben resolverse de todos modos para ciertas entradas. Si necesita programadores que puedan manejar este tipo de problemas, hay una buena manera de que lo demuestren en una entrevista, y eso es lanzarles uno y ver si se asustan.
Si alguien reclama un fondo de CompSci, entonces debería poder proporcionar buenas soluciones a ciertos problemas de NP-C bajo demanda, como resolver el problema de la mochila con la programación dinámica. Considero que no tiene sentido pedirle a un solicitante un trabajo de programación para que se ocupe de un problema que nunca han visto antes, y realmente lo demuestre NP-completo (por ejemplo, reduciendo la mochila al problema especificado). No necesita muchos programadores por empresa que puedan hacer eso (generalmente 0), y todo lo que probablemente descubrirá es cuánto tiempo se mantiene el candidato antes de intentar cambiar de tema y hacer algo más valioso en el momento de la entrevista. ..
[*] polinomio en el tamaño de la entrada en bits, es decir. A menudo se ve gente discutiendo la complejidad algorítmica de problemas de enteros como la factorización en términos del tamaño del número representado por la entrada, por ejemplo, "divisiones de prueba sqrt (N)". Pero no es así como se definen NP y NP-C.
¿Seguro Por qué no? NP-completo no significa sin solución, solo significa que su solución será lenta. Puede estar buscando para ver si el candidato elegirá la solución de fuerza bruta o probará una solución de programación dinámica. Y este tipo de pregunta puede llevar a preguntas sobre el tiempo de ejecución y otras teorías útiles.
Completamente legítimo para mí. Si usted es un profesional de ciencias de la computación, existen muchas posibilidades de que pueda argumentar de manera informal por qué el problema parece ser difícil, o (incluso mejor) proporcionar un resumen de la reducción de un problema conocido de NP-difícil.
Muchos problemas del mundo real eventualmente resultan ser NP-difíciles, y el flujo de apilamiento también tiene de vez en cuando preguntas sobre la complejidad de un problema que resulta ser difícil (NP-hard, por ejemplo). Es una parte importante de una caja de herramientas para profesionales de la CS poder reconocer y argumentar por problemas que se sabe que son difíciles de resolver.
Creo que es válido hacer una pregunta para la cual el entrevistado no sabrá la respuesta.
Todo el mundo encuentra problemas a los que no sabe la respuesta. Este tipo de pregunta le dará una idea de lo que es el proceso interno del entrevistado. Si concluyen lógicamente las cosas y comienzan a formular una respuesta correcta, incluso si no es el mejor algoritmo de programación dinámico para ello, eso demuestra que pueden razonar bien y descubrir una respuesta.
Además, como es probable que no sepan todo sobre el problema, este tipo de pregunta le permite ver qué tan cómodo está el entrevistado con pedir ayuda o aclaraciones.
Creo que la mejor manera de responder a este tipo de pregunta es pedir aclaraciones si falta algo o no se conoce bien, y luego postular una respuesta, señalando por qué cree que es correcto y por qué es probable que no sea la mejor. solución.
Es algo así como hacer preguntas casi imposibles sin informar al entrevistado, pero en la resolución de problemas observados, a menudo se hace la pregunta para que pueda demostrar habilidades de pensamiento crítico, cómo abordar la resolución de problemas y cómo manejar la presión o el fracaso. .
Me han hecho preguntas de la entrevista que no pude resolver, y creo que nunca he "fallado" una entrevista por eso.
Es bueno hacer una pregunta que es difícil de responder, para ver cómo un programador razona un problema.
Pero todo depende de cómo el entrevistador formule la pregunta, y le pide al programador una solución si no es un genio matemático (es decir, para ver cómo razonan y cómo reaccionan a preguntas como "ese es un buen comienzo, pero qué si ... ") en lugar de detectar si son autistas y pueden proporcionar una solución óptima en 4,3 segundos).
Vale la pena recordar que las entrevistas son asuntos muy estresantes en los que a muchas personas les resulta muy difícil responder bien a esas preguntas; por lo general, una pregunta mucho más simple será suficiente sin someter al entrevistado a un estrés / presión excesivos.
Si lo haces para tratar de ver deliberadamente cómo lidiar con el estrés es estúpido, no es el tipo de estrés con el que un programador tiene que lidiar en su trabajo, por lo que no está probando nada que valga la pena.
Eso es malvado!
Si el entrevistador hace una pregunta NP-completa en un entrevistador, la única respuesta que razonablemente puede esperar es que el entrevistado responda con una prueba de que el problema es NP-completo. En un ambiente de bajo estrés, como una pregunta de la tarea de la universidad, esto generalmente toma un estudiante brillante de 2-3 horas o más para demostrarlo. La prueba en sí puede tomar varias páginas para escribir por completo, tal vez varias horas de trabajo en sí. En un entorno altamente estresante como una entrevista, puede esperar que el entrevistado ni siquiera reconozca que esto es np-complete.
La única alternativa razonable es que el entrevistado produzca un algoritmo de aproximación; sin embargo, en este caso, el entrevistador debe dejar claro explícitamente que están bien con las aproximaciones.
Aun así, la mayoría de las aproximaciones solo vienen con un orden de 2 de la respuesta correcta.
Supongo que hay una alternativa más: el entrevistado sugiere que un algoritmo de tipo de búsqueda quizás sea el más adecuado (por ejemplo, el problema de optimización de dominio de enteros que está completo en NP, la mayoría de los algoritmos de aproximación usan una ramificación y un giro de búsqueda en el simplex algoritmo para producir resultados decentes.)
Hay una categoría de preguntas de entrevista que son ilegales en algunos países, generalmente relacionadas con detalles personales que no son asunto del empleador. Aparte de eso, cualquier pregunta es un juego justo si el entrevistador siente que ayudará a tener una idea de las capacidades del entrevistado.
Si está contratando para un puesto que requiere un pensador en lugar de solo un código mono, puede ser útil lanzar este tipo de problema al solicitante. ¿A quién le importa si un problema es "conocido" como NP? Si el chico es bueno, llegará a esa comprensión al analizar el problema. Ese podría ser el resultado que el entrevistador desea ver, o el solicitante puede continuar con un análisis previo y describir cómo podría forzar el problema, o qué optimizaciones puede pensar aplicar para hacerlo más manejable. .
No hay nada de malo en dar un problema de NP-completo como un desafío de programación durante una entrevista. Solo veo algo malo en esperar encontrar una solución polinómica al problema durante la entrevista.
Un entrevistador debería querer ver cómo un candidato trata una variedad de situaciones, incluidas situaciones en las que el candidato no puede encontrar una solución fácil. Las preguntas "imposibles" muestran cómo reacciona el candidato cuando no hay una solución simple. ¿El candidato se rinde? ¿Cuántos intentos diferentes busca el candidato? ¿Hasta qué punto son probadas las soluciones? ¿Cuándo pide ayuda el candidato y cómo? ¿Se queja el candidato de que el problema "no es justo"?
En resumen, esta pregunta de entrevista no se trata de resolver P = NP ... es una respuesta psicológica.
No veo ningún problema con preguntar algo como esto. Además, NO se debe esperar que los programadores reconozcan los problemas de NP-completa de memoria. Sin embargo, deberían ser capaces de identificar que su algoritmo es potencialmente lento, independientemente de si un problema dado es NP-completo.
No veo un problema con esto, pero cuestiono un poco 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 dice que lo hablen, puede averiguar 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 lanzar algo que es un tanto "complicado" como esto a menudo es una exageración, IMO.
Prefiero pedirles que demuestren que P! = NP o P == NP. Algún día un candidato responderá, les robaré la respuesta y seré famoso.
En una nota más seria, sin embargo, creo que es completamente justo. La mayoría de los problemas completos de NP son fáciles de resolver, simplemente se ejecutan muy lentamente. Sin embargo, a menos que el trabajo requiera que ellos conozcan mucho sobre la teoría de la complejidad, todo lo que necesitan demostrar es que entienden que la solución será lenta. Puntos de bonificación si saben que es tiempo no polinomial, estrella de oro si saben que está completo NP.
No, es grosero y una señal de que al entrevistador le gusta estar en una posición de poder. Jaja peon ¡Sé la respuesta, y tú no! Y chico, ¿me encanta hacer que te retuerces tratando de llegar a eso?
Casi de la única manera en que podría ser incluso un poco válido como una pregunta de entrevista útil es si se tratara de una pregunta conocida o que de alguna manera fuera NP-completa, y se formulara de manera que alentara la discusión de la viabilidad.
Si se hiciera una pregunta de este tipo antes de una entrevista (para ser respondida en una entrevista), diría que está bien ... pero solo para resolver un problema tan difícil como que en el lugar definitivamente no va a ser bien hecho por ningún programador, y si el programador lo hace bien, eso significa que puede actuar en el momento (lo que no siempre es lo mejor para programar, ya que el diseño de las cosas debe tomar tiempo y controlar todos los defectos posibles) o que hayan visto un problema similar anteriormente.
Edición: O posiblemente sería bueno hablar sobre el problema, como decir, establecer un plan de acción, ya sea que lo resuelva o no por completo ... y discutir si es posible y si existe una manera rápida (pero difícil) de hacerlo. No diría que el entrevistado debería escribir más de 50 líneas de código C en una entrevista para resolverlo.