Ist es richtig zu bitten, ein NP-Complete-Problem in einem Vorstellungsgespräch zu lösen? [abgeschlossen

Question

Heute gab es eine Frage Wo der Autor während eines Interviews ein NP-Complete-Problem erhielt und ihm offensichtlich nicht gesagt wurde, dass es eines war.

Was ist der Zweck, solche Fragen zu stellen? Welches Verhalten erwartet der Interviewer, wenn sie solche Dinge fragen? Nachweisen? Nützliche Heuristik? Und ist es überhaupt legitim, einen zu fragen, ob es kein bekanntes Problem mit NP-Complete ist, von dem jeder wissen sollte? (Da ist ein viele davon)

Answer 1

Völlig legitim für mich. Wenn Sie Informatikprofi sind, gibt es gute Chancen, dass Sie entweder informell argumentieren können, warum das Problem schwierig zu sein scheint oder (noch besser) eine Skizze der Reduktion von einem bekannten NP-harten Problem darstellen.

Viele Probleme mit der realen Welt erweisen sich schließlich als NP-Hard, und Stackoverflow hat ab und zu auch Fragen zur Komplexität eines Problems, das sich als schwierig herausstellt (zum Beispiel NP-Hard). Es ist ein wichtiger Bestandteil eines CS -Professionals -Toolbox, in der Lage zu sein, Probleme zu erkennen und für Probleme zu streiten, von denen bekannt ist, dass sie schwer zu lösen sind.

Answer 2

Ich sehe kein Problem damit, so etwas zu fragen. Außerdem ist nicht zu erwarten, dass Programmierer NP-Complete-Probleme durch ROTE erkennen. Sie sollten jedoch in der Lage sein, festzustellen, dass ihr Algorithmus möglicherweise langsam ist, unabhängig davon, ob ein bestimmtes Problem NP-Vervollständigung ist.

Answer 3

Sicher warum nicht? NP-Complete bedeutet nicht unlösbar, sondern nur, dass Ihre Lösung langsam ist. Möglicherweise suchen Sie nach, ob der Kandidat die Brute-Force-Lösung auswählt oder eine dynamische Programmierlösung ausprobiert. Und diese Art von Frage kann zu Fragen zu Laufzeit und anderen nützlichen Theorie führen.

Answer 4

Es gibt eine Kategorie von Interviewfragen, die in einigen Ländern illegal sind und in der Regel persönliche Details betrifft, die keines der Geschäftstätigkeit des Arbeitgebers sind. Abgesehen davon ist jede Frage ein faires Spiel, wenn der Interviewer der Meinung ist, dass es sich um eine Vorstellung von den Fähigkeiten des Interviewten handelt!

Wenn Sie eine Position einstellen, die eher einen Denker als nur einen Codeaffen fordert, kann es nützlich sein, diese Art von Problem dem Bewerber zu werfen. Wen interessiert es, ob ein Problem "bekannt" als NP ist? Wenn der Typ gut ist, wird er zu diesem Verständnis kommen, um das Problem zu analysieren. Dies kann durchaus das Ergebnis sein, das der Interviewer sehen möchte, oder der Bewerber kann weiterhin eine weitere Voranalyse durchführen und beschreiben, wie er das Problem brutal machen würde oder welche Optimierungen er bewerben kann, um es zu bewerben, um es zu bewerben .

Answer 5

Ich sehe kein Problem damit, aber ich stelle etwas in Frage, den Nutzen dieser Art von Fragen in Interviews im Allgemeinen.

Der Vorteil, Fragen wie ein Interviewer zu stellen, besteht darin, zu sehen, wie die Person ein Problem nähert und wie sie denkt. Wenn Sie ihnen sagen, dass sie es aussprechen sollen, können Sie einiges darüber herausfinden, wie sie sich einem schwierigen Problem angehen.

Davon abgesehen sind die meisten Menschen während eines Interviews nicht in Bestform - also ist es oft übertrieben, etwas zu werfen, das etwas "knifflig" ist, IMO.

Answer 6

Ich denke, es ist gültig, eine Frage zu stellen, von der Sie wissen, dass der Befragte die Antwort nicht kennt.

Jeder trifft auf Probleme, auf die er die Antwort nicht kennen. Diese Art von Frage gibt Ihnen Einblicke in den internen Prozess des Befragten. Wenn sie die Dinge logischerweise abschließen und eine korrekte Antwort formulieren, auch wenn es nicht der beste dynamische Programmieralgorithmus dafür ist, zeigt dies, dass sie gut argumentieren und eine Antwort entdecken können.

Da sie wahrscheinlich nicht alles über das Problem wissen, können Sie diese Art von Frage sehen, wie bequem der Befragte mit Hilfe oder Klärung bittet.

Ich denke, der beste Weg, diese Art von Frage zu beantworten Lösung.

Answer 7

Es ist gut, eine Frage zu stellen, die schwer zu beantworten ist, um zu sehen, wie ein Programmierer durch ein Problem begründet ist.

Aber es hängt alles davon ab, wie der Interviewer die Frage stellt und den Programmierer zu einer Lösung fordert, wenn sie kein mathematisches Genie sind (dh, um zu sehen, wie sie begründen und wie sie auf Fragen wie "Das ist ein guter Start, aber was ist Wenn ... ") anstatt festzustellen, ob sie autistisch sind und in 4,3 Sekunden eine optimale Lösung liefern können).

Es ist sich daran zu erinnern, dass Interviews sehr stressige Angelegenheiten sind, in denen viele Menschen solche Fragen sehr schwer zu beantworten finden - eine viel einfachere Frage wird normalerweise ausreichen, ohne den Befragten unter unangemessenem Stress/Druck zu stellen.

Wenn Sie es tun, um absichtlich zu versuchen, zu sehen, wie dumm sie mit Stress umgehen, ist dies nicht die Art von Stress, mit dem ein Programmierer in ihrem Job zu tun hat, sodass Sie nichts Wertvolles testen.

Answer 8

Es ist irgendwie gemein, dass es noch unmögliche Fragen stellt, ohne den Befragten darüber zu informieren, aber bei der beobachteten Problemlösung wird die Frage häufig gestellt, damit Sie kritische Denkfähigkeiten demonstrieren können, wie Sie sich mit dem Lösen von Problemen befassen und wie Sie mit Druck oder Misserfolg umgehen können .

Mir wurde Fragen mit Interviewfragen gestellt, die ich nicht lösen konnte, und ich glaube nicht, dass ich ein Interview deswegen jemals "gescheitert" habe.

Answer 9

Ist es fair, in einem Interview zu fragen, wie Sie Zahlen faktorisieren können?

Es ist nicht bekannt, dass es NP-C ist, aber es ist keine Polynom-Zeit-Lösung [*] bekannt, daher ist es sicherlich nicht bekannt, dass es in P. ist.

Ich denke, die Antwort auf sowohl meine Frage als auch die ursprüngliche Frage lautet "Ja" und aus den gleichen Gründen. Einige Probleme haben keine Lösung, die gut skaliert werden, müssen jedoch für bestimmte Eingaben trotzdem gelöst werden. Wenn Sie Programmierer benötigen, die solche Probleme bewältigen können, gibt es einen guten Weg, um sie im Interview zu beweisen, und das ist, um sie aufzunehmen und zu sehen, ob sie ausflippen.

Wenn jemand einen COMPSCI-Hintergrund beansprucht, sollte er sogar in der Lage sein, bestimmte NP-C-Probleme bei Bedarf gute Lösungen zu liefern, z. B. das Lösen des Rucksackproblems mit dynamischer Programmierung. Ich würde es als sinnlos betrachten, einen Bewerber um einen Programmierjob zu bitten, ein Problem zu nehmen, das er noch nie gesehen hat, und es tatsächlich zu beweisen, dass es NP-Complete (zum Beispiel durch Reduzieren von Knapsack auf das angegebene Problem). Sie brauchen nicht sehr viele Programmierer pro Unternehmen, die dies tun können (normalerweise 0), und Sie werden wahrscheinlich nur feststellen, wie lange der Kandidat daran bleibt, bevor Sie versuchen, das Thema zu wechseln und mit der Interviewzeit etwas Wertvolleres zu tun. ..

*] Polynom in der Größe des Eingangs in Bits, das heißt. Sie sehen häufig Menschen, die die algorithmische Komplexität von Ganzzahlproblemen wie die Faktorisierung in Bezug auf die Größe der Anzahl der Eingaben z. Aber so sind NP und NP-C nicht definiert.

Answer 10

Nein, es ist unhöflich und ein Zeichen dafür, dass der Interviewer einfach gerne in einer Machtposition ist. Haha, Peon! Ich kenne die Antwort und du tust es nicht! Und Junge, ich liebe es, dich zu winden, um es zu versuchen, es zu finden!

Über die einzige Möglichkeit, wie es als nützliche Interviewfrage sogar leicht gültig sein könnte, ist, ob es sich um eine bekannte Frage handelte oder eine, die offensichtlich offensichtlich NP-Complete war und auf eine Weise gefragt wurde, die die Diskussion über die Machbarkeit förderte.

Answer 11

Es ist nichts Falsches daran, ein NP-Complete-Problem als Programmierherausforderung während eines Interviews zu geben. Ich sehe nur etwas falsch, wenn ich erwarte, während des Interviews eine Polynom-Zeit-Lösung für das Problem zu finden.

Ein Interviewer sollte sehen, wie ein Kandidat mit einer Vielzahl von Situationen umgeht - einschließlich Situationen, für die der Kandidat keine einfache Lösung finden kann. "Impossible" Fragen zeigen, wie der Kandidat reagiert, wenn es keine einfache Lösung gibt. Gibt der Kandidat einfach auf? Wie viele verschiedene Versuche suchen die Kandidaten? Wie weitreichend sind die Lösungen ausprobiert? Wann bittet der Kandidat um Hilfe - und wie? Beschwert sich der Kandidat darüber, dass das Problem "nicht fair" ist?

Kurz gesagt, in einer solchen Interviewfrage geht es darum, P = NP zu lösen ... es ist eine psychologische Antwort.

Answer 12

Wenn eine solche Frage vor einem Interview gestellt würde (um in einem Interview beantwortet zu werden), würde ich sagen, dass es in Ordnung ist. Wenn der Programmierer es gut macht, bedeutet dies nur, dass er vor Ort reagieren kann (was nicht immer das Beste für das Programmieren ist, da das Entwerfen von Dingen Zeit benötigt und jeden möglichen Fehler überprüfen muss) oder dass er zuvor ein ähnliches Problem gesehen hat.

Bearbeiten: Oder möglicherweise eine Diskussion über das Problem wäre gut, z. B. sagen, dass Sie einen Aktionsplan festlegen, unabhängig davon, ob Sie es vollständig lösen oder nicht, wie machbar und ob es einen schnellen (aber schwierigen) Weg gibt, dies zu tun und so. Ich würde nicht sagen, dass der Befragte in einem Interview über 50 Zeilen C -Code aufschreiben muss, um ihn zu lösen

Answer 13

Das ist böse!

Wenn der Interviewer in einem Interviewer eine NP-Vervollständigung in einem Interviewer stellt, ist die einzige Antwort, die er vernünftigerweise erwarten kann, dass der Befragte mit einem Beweis antwortet, dass das Problem NP-Complete ist. In einer Umgebung mit geringer Stress wie einer Universitäts-Hausaufgabenfrage dauert dies normalerweise ein strahlender Schüler von 2-3 oder mehr Stunden, um zu beweisen. Der Beweis selbst kann mehrere Seiten benötigen, um vollständig, vielleicht mehrere Stunden Arbeit selbst zu schreiben. In einer Stressumgebung wie einem Interview können Sie erwarten, dass der Befragte möglicherweise nicht einmal erkennen, dass dies NP-Vervollständigung ist.

Die einzig vernünftige Alternative ist, dass der Befragte einen Annäherungsalgorithmus produziert; In diesem Fall sollte der Interviewer es jedoch schaffen ausdrücklich klar, dass sie sind fein mit Annäherungen.

Trotzdem sind die meisten Annäherungen nur mit einer Reihenfolge von 2 der richtigen Antwort ausgestattet.

Ich denke, es gibt 1 weitere Alternative: Der Befragte schlägt vor, dass ein Such-Algorithmus möglicherweise am besten geeignet ist (zum Beispiel das Problem der Integer-Domain-Optimierung, das NP-Complete ist, die meisten Approximationsalgorithmen verwenden einen Zweig- und gebundenen Suchspin auf dem Simplex Algorithmus, um anständige Ergebnisse zu erzielen.)

Answer 14

Ich bitte sie vor, sie zu beweisen, dass p! = Np oder p == np. Eines Tages wird ein Kandidat darauf antworten, ich werde seine Antwort stehlen und berühmt sein!

Ich denke jedoch, dass es völlig fair ist. Die meisten NP -vollständigen Probleme sind leicht zu lösen, sie laufen nur sehr langsam. Wenn der Job nicht erforderlich ist, dass sie viel über die Komplexitätstheorie wissen, müssen sie nur nachweisen, dass sie verstehen, dass die Lösung langsam ist. Bonuspunkte Wenn sie wissen, dass es nicht polynomiale Zeit ist, Gold Star, wenn sie wissen, dass es NP vollständig ist.