È corretto chiedere di risolvere un problema NP-completo su un colloquio di lavoro? [chiuso]

Question

Oggi c'è stata una domanda su SO, dove l'autore è stato dato un problema NP-completo durante un'intervista e lui, ovviamente, non era stato detto che si trattava di uno.

Qual è lo scopo di porre queste domande? Che comportamento non l'intervistatore si aspetta quando si chiede queste cose? Prova? euristica utili? Ed è anche legittimo chiedersi uno se non è un ben noto problema NP-completo tutti dovrebbero conoscere? (C'è un un sacco di loro )

Answer 1

tutto legittima per me. Se siete informatica professionale ci sono buone possibilità che si può uno degli argomenti in modo informale perché il problema sembra essere difficile, o (ancora meglio) fornire uno schizzo di riduzione da un noto problema NP-hard.

Molti problemi del mondo reale alla fine risultano essere NP-hard, e StackOverflow ha anche ora e poi domande circa la complessità di un problema che si rivela essere un anno difficile (NP-hard, per esempio). Si tratta di una parte importante di un CS professionisti cassetta degli attrezzi per essere in grado di riconoscere e di discutere i problemi che sono noti per essere difficili da risolvere.

Answer 2

Non vedo alcun problema con chiedendo qualcosa di simile. Inoltre, i programmatori dovrebbero non essere tenuti a riconoscere i problemi NP-completi a memoria. Essi dovrebbero, tuttavia, essere in grado di identificare che il loro algoritmo è potenzialmente lento indipendentemente dal fatto che un dato problema è NP-completo.

Answer 3

Certo, perché no? NP-completo non significa irrisolvibile, significa solo la soluzione sarà lenta. Si può essere alla ricerca per vedere se il candidato sceglierà la soluzione di forza bruta, o provare una soluzione di programmazione dinamica. E questo tipo di domanda può portare in domande su runtime e altra teoria utile.

Answer 4

C'è una categoria di domande di intervista che sono illegali in alcuni paesi, di solito appartenenti ai dati personali che sono nessuna delle attività del datore di lavoro. A parte questo, ogni questione è un gioco equo se l'intervistatore sente vi aiuterà avere un'idea delle capacità dell'intervistato!

Se si sta assumendo per una posizione che richiede un pensatore piuttosto che solo una scimmia codice, può essere utile per lanciare questo tipo di problema al richiedente. Chi se ne frega se un problema è "ben noto" per essere NP? Se il ragazzo è bene che verrà a che la comprensione per l'analisi del problema. Questo potrebbe essere il risultato l'intervistatore vuole vedere, o il richiedente può andare a fare un po 'di pre-analisi e descrivere come avrebbe forza bruta il problema, o quello che le ottimizzazioni che può pensare di applicare per renderlo più gestibile .

Answer 5

Non vedo un problema con questo, ma io un po 'in dubbio l'utilità di questo tipo di domande nelle interviste in generale.

Il vantaggio di fare domande di questo tipo, come intervistatore, è vedere come la persona che si avvicina a un problema, e come pensano. Se dite loro di parlare fuori, si può scoprire un po 'su come essi si avvicineranno un problema difficile.

Detto questo, nel corso di un'intervista, la maggior parte delle persone non sono al loro meglio -. In modo gettare qualcosa che sia un po ' "difficile" come questo è spesso eccessivo, IMO

Answer 6

Credo che sia valida per fare una domanda si conosce l'intervistato non conoscere la risposta a.

Ognuno incontra problemi che non si conosce la risposta. Questo tipo di domanda vi darà informazioni su quanto processo interno dell'intervistato è. Se essi concludono logicamente le cose e iniziano a formulare una risposta corretta, anche se non è il miglior algoritmo di programmazione dinamica per esso, mostra che essi possono ragionare bene e scoprire una risposta.

Inoltre, dal momento che probabilmente non sanno tutto ciò che riguarda il problema, questo tipo di domanda consente di vedere quanto comodo l'intervistato è con chiedere aiuto o chiarimenti.

Credo che il modo migliore per rispondere a questo tipo di domanda è quello di chiedere per eventuali chiarimenti se qualcosa manca o non è ben noto, e quindi postulare una risposta, sottolineando il motivo per cui si pensa che è corretto, e perché è probabile che isn' t la soluzione migliore.

Answer 7

E 'bene chiedere una domanda che è difficile rispondere, per vedere come un programmatore ragioni attraverso un problema.

Ma tutto dipende da come l'intervistatore pone la domanda, e richiede il programmatore verso una soluzione se non sono un genio della matematica (ad esempio per vedere come la ragione, e come reagiscono a domande del tipo "questo è un buon inizio , ma se ... ") anziché per rilevare se sono autistici e possono fornire una soluzione ottimale in 4,3 secondi).

vale la pena ricordare che le interviste sono questioni altamente stressante, in cui molte persone trovano queste domande molto difficile rispondere bene -. Una domanda molto più semplice di solito sufficiente senza mettere l'intervistato sotto eccessivo stress / pressione

Se lo fate per cercare deliberatamente per vedere come affrontare lo stress è solo stupido - che non è il tipo di stress un programmatore deve fare i conti con nel loro lavoro, in modo da non sta testando qualcosa di buono

Answer 8

E 'una sorta di media a fare domande quasi impossibile senza informare l'intervistato di esso, ma in osservata problem solving, la questione è spesso chiesto in modo che si può dimostrare la capacità di pensiero critico, come ci si avvicina la soluzione dei problemi, e come gestire la pressione o il fallimento.

Mi è stato chiesto domande di intervista non riuscivo a risolvere, e non credo di aver mai "fallito", un'intervista a causa di esso.

Answer 9

E 'giusto chiedere in un'intervista come fattorizzare numeri?

Non è noto essere NP-C, ma nessuna soluzione polinomiale [*] si sa, quindi non è certamente noto per essere in P.

Credo che la risposta ad entrambe mia domanda, e alla domanda iniziale, è "sì", e per le stesse ragioni. Alcuni problemi non hanno soluzione scalabile, ma non devono essere risolti comunque per determinati input. Se avete bisogno di programmatori in grado di gestire questo tipo di problemi, c'è un buon modo per far loro provare in un'intervista, e questo è a passo di loro uno e vedere se fuori di testa.

Se qualcuno sostiene uno sfondo CompSci, allora dovrebbero anche essere in grado di fornire buone soluzioni ad alcuni problemi NP-C su richiesta, come ad esempio la soluzione del problema dello zaino con la programmazione dinamica. Riterrei inutile chiedere un candidato per un lavoro di programmazione per prendere un problema che non hanno mai visto prima, e in realtà dimostrarlo NP-completo (per esempio riducendo zaino al problema specificato). Non hai bisogno di molto molti programmatori per società che può fare che (di solito 0), e tutto è probabile che scoprirete è quanto a lungo il candidato mantiene a esso prima di tentare di cambiare argomento e fare qualcosa di più prezioso con il tempo di intervista. ..

[*] polinomiale nella dimensione dell'input in bit, che è. Si vedono spesso persone discutendo complessità algoritmica dei problemi interi come fattorizzazione in termini di dimensione del numero rappresentato dall'ingresso, per esempio "sqrt (N) divisioni di prova". Ma non è così che si definiscono NP e NP-C.

Answer 10

No, è maleducato e un segno che l'intervistatore piace solo essere in una posizione di potere. Haha, peon! Io conosco la risposta, e tu no! E il ragazzo, lo faccio mi piace fare contorcere cercando di trovare con essa!

L'unico modo in cui potrebbe essere anche un po 'valido come questione intervista utile è se si trattasse di una domanda ben noto o uno che fosse in qualche modo, ovviamente, NP-completo, e ha chiesto in un modo che ha incoraggiato la discussione della fattibilità.

Answer 11

Non c'è niente di sbagliato nel dare un problema NP-completo come una sfida di programmazione durante un'intervista. Vedo solo qualcosa di sbagliato con aspettandosi di trovare una soluzione in tempo polinomiale per il problema durante l'intervista.

Un intervistatore dovrebbe desiderare di vedere come un candidato offerte con una varietà di situazioni - comprese le situazioni che il candidato non riesce a trovare una soluzione facile per. domande "impossibili" mostrano come il candidato reagisce quando non c'è una soluzione semplice. Il candidato proprio rinunciare? Quanti tentativi diverso fa la ricerca candidato? Come di vasta portata sono le soluzioni provato? Quando parte il candidato chiedere aiuto - e come? Il candidato si lamentano che il problema "non è giusto"?

In breve, tale questione intervista non è di risolvere P = NP ... è una risposta psicologica.

Answer 12

Se una questione del genere è stato dato prima di un colloquio (a cui rispondere in un colloquio) direi che è ok .. ma per solo risolvere un problema così difficile come quello sul posto non è sicuramente sta per essere fatto bene da qualsiasi programmatore, e se il programmatore non farlo bene che appena significa che possono agire sul posto (che non è sempre la cosa migliore per la programmazione, come la progettazione di cose ha bisogno di prendere tempo e verificare ogni possibile difetto) o che hanno visto una simile problema prima.

Modifica: O forse la discussione sul problema sarebbe bene, come dire, che stabilisce un piano d'azione se non si risolve completamente .. e discutere su come fattibile e se c'è un modo veloce (ma difficile) per farlo e come. Non direi che l'intervistato dovrebbe avere a scrivere più di 50 righe di codice C in un'intervista per risolverlo se

Answer 13

Questo è il male!

Se l'intervistatore chiede una questione NP-completo in un intervistatore l'unica risposta che possono ragionevolmente aspettarsi è che l'intervistato risponde con una prova che il problema è NP-completo. In un ambiente a bassa tensione come una domanda compiti a casa universitaria, questo di solito prende uno studente brillante 2-3 o più ore per provare. La prova stessa può richiedere diverse pagine di scrivere completamente, forse diverse ore di lavoro stesso. In un ambiente ad alta tensione come un colloquio ci si può aspettare che l'intervistato può anche non riconoscere che questo è NP-completo.

L'unica alternativa ragionevole è che l'intervistato produrre un algoritmo di approssimazione; tuttavia, in questo caso l'intervistatore dovrebbe rendere più esplicitamente chiaro che sono bene con approssimazioni.

Anche così, la maggior parte delle approssimazioni venire solo con un ordine di 2 della risposta corretta.

Credo che ci sia 1 più alternativa: l'intervistato suggerisce che un algoritmo di ricerca di tipo forse il più adatto (Prendiamo ad esempio il problema di ottimizzazione intero dominio, che è NP-completo, la maggior parte degli algoritmi di approssimazione utilizzano un ramo e di ricerca legata rotazione sull'algoritmo simplex di produrre risultati decenti.)

Answer 14

Io li preferisco chiedendo di dimostrare che P! = NP o P == NP. Un giorno un candidato risponderà, te lo rubo la loro risposta ed essere famoso!

Su una nota più grave, però, credo che sia del tutto giusto. La maggior parte dei problemi NP completi sono facili da risolvere, hanno appena eseguito molto lentamente. A meno che il lavoro richiede loro di sapere molto su teoria della complessità, però, tutti hanno bisogno di dimostrare è che essi comprendono la soluzione sarà lenta. I punti di bonus se sanno che è tempo non polinomiale, stella d'oro se sanno che è NP completo.