É correto pedir para resolver um problema de preenchimento de NP em uma entrevista de emprego? [fechado

Question

Hoje havia um pergunta SO, onde o autor recebeu um problema de preenchimento de NP durante uma entrevista e ele obviamente não havia sido informado de que era um.

Qual é o objetivo de fazer tais perguntas? Que comportamento o entrevistador espera ao perguntar essas coisas? Prova? Heurísticas úteis? E é mesmo legítimo perguntar se não é um problema bem conhecido com preenchimento de NP que todos devem saber? (há um muitos deles)

Answer 1

Completamente legítimo para mim. Se você é profissional de ciência da computação, há boas chances de que você possa argumentar informalmente por que o problema parece ser difícil ou (ainda melhor) fornecer um esboço de redução de um problema conhecido por NP.

Muitos problemas do mundo real acabam sendo NP-Hard, e o Stackoverflow também tem de vez em quando as perguntas sobre a complexidade de um problema que acaba sendo difícil (NP-Hard, por exemplo). É uma parte importante de uma caixa de ferramentas de profissionais da CS ser capaz de reconhecer e argumentar por problemas que são conhecidos por serem difíceis de resolver.

Answer 2

Não vejo nenhum problema em perguntar algo assim. Além disso, não se deve esperar que os programadores reconheçam os problemas completos de NP por Rote. Eles devem, no entanto, ser capazes de identificar que seu algoritmo é potencialmente lento, independentemente de um determinado problema ser o NP-completo.

Answer 3

Claro, por que não? O NP-completo não significa inútil, isso significa que sua solução será lenta. Você pode estar procurando ver se o candidato escolherá a solução de força bruta ou tentará uma solução de programação dinâmica. E esse tipo de pergunta pode levar a perguntas sobre o tempo de execução e outra teoria útil.

Answer 4

Há uma categoria de perguntas de entrevista ilegais em alguns países, geralmente referentes a detalhes pessoais que não são da conta do empregador. Além disso, qualquer pergunta é justa se o entrevistador sentir que ajudará a ter uma idéia das capacidades do entrevistado!

Se você está contratando uma posição que exige um pensador em vez de apenas um macaco de código, pode ser útil jogar esse tipo de problema no candidato. Quem se importa se um problema é "conhecido" por ser NP? Se o cara é bom, ele chegará a esse entendimento ao analisar o problema. Esse pode muito bem ser o resultado que o entrevistador deseja ver, ou o candidato pode continuar fazendo mais um pouco de análise e descrever como ele seria o problema bruto, ou quais otimizações ele pode pensar para se aplicar para torná-lo mais gerenciável .

Answer 5

Não vejo um problema com isso, mas questiono a utilidade desses tipos de perguntas em entrevistas em geral.

O benefício de fazer perguntas como essa, como entrevistador, é ver como a pessoa aborda um problema e como ela pensa. Se você disser a eles para conversar, poderá descobrir um pouco sobre como eles abordarão um problema difícil.

Dito isto, durante uma entrevista, a maioria das pessoas não está no seu melhor - então jogar algo que é um tanto "complicado" como esse geralmente é exagerado, IMO.

Answer 6

Eu acho que é válido fazer uma pergunta que você sabe que o entrevistado não saberá a resposta.

Todo mundo encontra problemas aos quais não conhecem a resposta. Esse tipo de pergunta lhe dará informações sobre qual é o processo interno do entrevistado. Se eles concluirem logicamente as coisas e começarem a formular uma resposta correta, mesmo que não seja o melhor algoritmo de programação dinâmica, mostra que eles podem raciocinar bem e descobrir uma resposta.

Além disso, como eles provavelmente não sabem tudo sobre o problema, esse tipo de pergunta permite que você veja o quão confortável o entrevistado está em pedir ajuda ou esclarecimento.

Eu acho que a melhor maneira de responder a esse tipo de pergunta é pedir esclarecimentos se algo está faltando ou não é bem conhecido e depois postular uma resposta, apontando por que você acha que está correto e por que provavelmente não é o melhor solução.

Answer 7

É bom fazer uma pergunta difícil de responder, para ver como um programador razões através de um problema.

Mas tudo depende de como o entrevistador faz a pergunta e leva o programador a uma solução se eles não são um gênio matemático (ou seja, para ver como eles argumentam e como eles reagem a perguntas como "esse é um bom começo, mas o que o que Se ... ") em vez de detectar se são autistas e podem fornecer uma solução ideal em 4,3 segundos).

Vale lembrar que as entrevistas são assuntos altamente estressantes, nos quais muitas pessoas acham essas perguntas muito difíceis de responder bem - uma pergunta muito mais simples geralmente é suficiente sem colocar o entrevistado sob estresse/pressão indevidos.

Se você fizer isso para tentar deliberadamente ver como eles lidam com o estresse é apenas estúpido - esse não é o tipo de estresse com o qual um programador precisa lidar em seu trabalho, para que você não esteja testando nada que valha a pena.

Answer 8

É meio que significa fazer perguntas quase impossíveis sem informar o entrevistado, mas na resolução de problemas observada, a pergunta é frequentemente feita para que você possa demonstrar habilidades de pensamento crítico, como aborda a solução de problemas e como lida com pressão ou falha .

Fui perguntas à entrevista que não consegui resolver e acho que nunca "falhei" em uma entrevista por causa disso.

Answer 9

É justo perguntar em uma entrevista como fatorar os números?

Isso não é conhecido por ser NP-C, mas nenhuma solução de tempo polinomial [*] é conhecido, por isso certamente não é conhecido por estar em P.

Eu acho que a resposta para a minha pergunta e a pergunta original é "sim" e pelas mesmas razões. Alguns problemas não têm solução que escalem bem, mas precisam ser resolvidos de qualquer maneira para certas entradas. Se você precisa de programadores que possam lidar com esses problemas, há uma boa maneira de deixá -los provar isso na entrevista, e isso é para lançá -los e ver se eles surtam.

Se alguém reivindicar um plano de fundo da COMPSCI, deve até fornecer boas soluções para certos problemas de NP-C sob demanda, como resolver o problema da mochila com a programação dinâmica. Eu consideraria inútil pedir a um candidato a um trabalho de programação que tome um problema que eles nunca viram antes e provar que NP completa (por exemplo, reduzindo a mochila para o problema especificado). Você não precisa de muitos programadores por empresa que podem fazer isso (geralmente 0), e tudo o que você provavelmente descobrirá é quanto tempo o candidato continua antes de tentar mudar de assunto e fazer algo mais valioso com o tempo da entrevista. ..

*] Polinômio no tamanho da entrada em bits, ou seja. Você costuma ver pessoas discutindo a complexidade algorítmica de problemas inteiros, como fatorização em termos do tamanho do número representado pela entrada, por exemplo, "SQRT (N) Trial Divisions". Mas não é assim que o NP e o NP-C são definidos.

Answer 10

Não, é rude e um sinal de que o entrevistador gosta de estar em uma posição de poder. Haha, peão! Eu sei a resposta, e você não! E garoto, eu amo fazer você se contorcer tentando inventá -lo!

A única maneira de ser um pouco válida como uma pergunta útil da entrevista é se era uma pergunta bem conhecida ou que de alguma forma foi obviamente completa, e perguntou de uma maneira que incentivava a discussão sobre viabilidade.

Answer 11

Não há nada de errado em dar um problema de preenchimento de NP como um desafio de programação durante uma entrevista. Eu só vejo algo errado em esperar encontrar uma solução de tempo polinomial para o problema durante a entrevista.

Um entrevistador deve querer ver como um candidato lida com uma variedade de situações - incluindo situações para as quais o candidato não consegue encontrar uma solução fácil. As perguntas "impossíveis" mostram como o candidato reage quando não há solução simples. O candidato simplesmente desiste? Quantas tentativas diferentes o candidato pesquisam? Qual a alcance das soluções de abrangência? Quando o candidato pede ajuda - e como? O candidato reclama que o problema "não é justo"?

Em suma, essa pergunta de entrevista não é sobre resolver p = np ... é uma resposta psicológica.

Answer 12

Se essa pergunta foi feita antes de uma entrevista (a ser respondida em uma entrevista), eu diria que está tudo bem ... mas apenas resolver um problema tão difícil que o local definitivamente não será bem feito por nenhum programador e Se o programador o fizer bem, isso significa que eles podem agir no local (o que nem sempre é a melhor coisa para programar, pois o design das coisas precisa levar tempo e verificar todas as falhas possíveis) ou que já viram um problema semelhante antes.

Editar: ou possivelmente discussões sobre o problema seria bom, como digamos, estabelecendo um plano de ação, se você o resolveu completamente. E discutindo o quão viável e se houver uma maneira rápida (mas difícil) de fazê -lo e tal. Eu não diria que o entrevistado deveria escrever mais de 50 linhas de código C em uma entrevista para resolvê -lo embora

Answer 13

Isso é mau!

Se o entrevistador fizer uma pergunta completa ao NP em um entrevistador, a única resposta que ele pode esperar razoavelmente é que o entrevistado responda com uma prova de que o problema é NP-completo. Em um ambiente de baixo estresse, como uma questão de lição de casa da universidade, isso geralmente leva um aluno brilhante por 2 a 3 horas ou mais para provar. A prova em si pode levar várias páginas para escrever completamente, talvez várias horas de trabalho em si. Em um ambiente de alto estresse, como uma entrevista, você pode esperar que o entrevistado nem reconheça que isso é o NP-completo.

A única alternativa razoável é que o entrevistado produz um algoritmo de aproximação; No entanto, neste caso, o entrevistador deve fazê -lo explicitamente claro que eles são multar com aproximações.

Mesmo assim, a maioria das aproximações vem apenas com uma ordem de 2 da resposta correta.

Eu acho que há mais 1 alternativa: o entrevistado sugere que um algoritmo do tipo de pesquisa talvez seja o mais adequado (pegue, por exemplo, o problema de otimização do domínio inteiro que é NP-Presente, a maioria dos algoritmos de aproximação usa uma ramificação e uma pesquisa ligada no simplex algoritmo para produzir resultados decentes.)

Answer 14

Prefiro pedir que prove que P! = NP ou P == NP. Algum dia, um candidato responderá, vou roubar a resposta deles e ser famosa!

Em uma nota mais séria, porém, acho que é completamente justo. A maioria dos problemas completos do NP é fácil de resolver, eles apenas correm muito lentamente. A menos que o trabalho exija que eles saibam muito sobre a teoria da complexidade, tudo o que eles precisam demonstrar é que eles entendem que a solução será lenta. Pontos de bônus Se eles souberem que é tempo não polinomial, Gold Star, se souber que é o NP completo.