Ist es in einem Interview besser, eine Brute-Force-Lösung für eine schwierige Frage zu programmieren oder das Interview damit zu verbringen, die Frage sorgfältig zu untersuchen? [geschlossen]

14

Manchmal sind Interviewfragen schwierig, ob der Interviewer dies beabsichtigt oder nicht. Es kann darauf ankommen, ob die begrenzte Interviewzeit genutzt werden soll, um eine hässliche, ineffiziente Brute-Force-Lösung zu erstellen, oder ob die Zeit darauf verwendet werden soll, alle Aspekte des Problems mit dem Interviewer zu verstehen.

Zum Beispiel kann das Problem 91 bei Project Euler durch eine nicht so schwierige Brute-Force-Lösung gelöst werden, bei der jedes mögliche Dreieck berechnet, ein isRightTriangle () -Test geschrieben und alle Dreiecke, die den Test bestehen, in eine Menge eingefügt werden. Die beiden X / Y-Koordinatenpaare ergeben jedoch eine O (x ^ 4) -Lösung mit einem hohen konstanten Wert. Ein Freund und ich haben gerade eine Lösung gefunden, die viel eleganter und effizienter ist, aber wir beide haben drei Stunden damit verbracht und Dutzende von Diagrammen gezeichnet, mehrere Formeln getestet, mehrere Ansätze untersucht usw.

Nicht jede Interviewfrage ist fair. Auch was für eine Person einfach ist, kann für eine andere schwer sein. Wenn jemand mit einer Frage zu kämpfen hat, würde Sie eine hässliche Lösung mit brachialer Gewalt beeindrucken, die funktioniert? Oder exzellentes Problemverständnis und Wege zu einer eleganten Lösung, aber zu keiner codierten Lösung? Gibt es eine Regel, die besagt, dass Sie nach 20 Minuten mit dem Codieren beginnen sollten, egal was passiert?

GlenPeterson
quelle
10
Fragen Sie sie, ob sie eine Brute-Force-Lösung oder eine nuancierte Lösung wollen.
Robert Harvey
Wenn sie eine gewaltfreie Lösung gewollt hätten, hätten sie eine Frage gestellt, die von vornherein nicht mit Gewalt gelöst werden kann.
minusSeven

Antworten:

9

Erstens ist eine Frage, für die zwei erfahrene Entwickler drei Stunden benötigen, um sie elegant zu optimieren, eine schlechte Wahl für eine Interviewfrage. Wenn Sie danach fragen, sollten Sie keine perfekten Antworten erwarten.

Andererseits lernt man manchmal am meisten über jemanden, wenn man ihn dazu bringt, an seine Grenzen zu stoßen. Das ist der Grund, warum viele College-Kurse die Schwierigkeit ansteigen lassen, bevor sie in die Kurve steigen. Wenn jeder bei jeder Prüfung 100% erreicht, bleibt Ihnen viel Potenzial zum Lernen.

Mein idealer Kandidat würde wahrscheinlich zuerst die Komplexitätsberechnung durchführen und sagen: "Oh, das sind nur 6 Millionen Iterationen, was nicht sehr lange dauert." Dann schreiben Sie schnell die Brute-Force-Lösung. Dann diskutierten sie Ansätze, um sie zu optimieren, ohne sie unbedingt umzusetzen, es sei denn, der Interviewer bat sie darum.

Dies liegt zum Teil daran, dass viele der in der Praxis auftretenden Probleme vom Typ Projekt-Euler One-Shot-Probleme sind, die Sie einmal lösen und dann vergessen müssen. Ich möchte wissen, dass jemand, den ich anstelle, in der Lage ist, einen Brute-Force-Algorithmus zu erkennen, der 2 Minuten zum Schreiben und 10 Minuten zum Ausführen benötigt. Dieser Algorithmus ist effizienter als ein Algorithmus, der 3 Stunden zum Schreiben und 10 Sekunden zum Ausführen benötigt, wenn Sie dies nur benötigen um es einmal auszuführen.

Karl Bielefeldt
quelle
Gute Antwort. Caleb hat das Brute-Force-First-Then-Optimization-Konzept vorgestellt, aber Ihre Antwort ist die einzige, die den Grund dafür angibt, warum eine Brute-Force-Lösung in diesem Fall akzeptabel ist: "Das sind nur 6 Millionen Iterationen, die nicht ausreichen sehr lang." Das ist nur Gold. Vielen Dank!
GlenPeterson
14

Wenn Sie als Personalchef darum bitten, ein Problem mit dem Code direkt vor mir zu lösen, tue ich nicht so viel, um den Code selbst zu sehen (obwohl dies wichtig ist), sondern um herauszufinden, wie und warum du hast getan, was du getan hast. Eines der Dinge, die Sie tun könnten, ist, nicht zu codieren, sondern mich zu den Aspekten des Problems selbst zu befragen, um es besser zu lösen. Das ist für mich aussagekräftiger und in der Regel sinnvoller als die dort im Code festgelegte Lösung. Das ist jedoch nicht jedermanns Sache und auch nicht das, was jeder sehen möchte (und in der Tat bitte ich die Leute nur selten, in einem Interview zu codieren, aber ich lege Probleme auf den Tisch und wir durchsprechen sie und manchmal taucht ein Pseudocode auf , was für mich genauso gut ist ).

Sie haben Recht, dass nicht jede Interviewfrage fair ist, und was für jemanden einfach ist, ist für einen anderen schwierig, in diesem Umfeld und mit diesen Einschränkungen, und deshalb suchen jene Interviews, die das verstehen, normalerweise nicht nach der Codelösung (obwohl das bedeutet wiederum eine wichtige Rolle spielen) , sondern die Lösung Prozess .

"Gibt es eine Regel, die besagt, dass Sie nach 20 Minuten einfach mit dem Codieren beginnen sollten, egal was passiert?" Ich würde diese Frage beantworten , indem er sagte , dass innerhalb kürzester Zeit zu denken über das Problem, sollten Sie zumindest tun etwas - mehr Fragen zu stellen, einen Rahmen für eine Lösung zu skizzieren, oder sagen Sie sich einfach nicht tun können / Ich weiß nicht, wo ich anfangen soll.

Wenn ich Ihnen ein schweres Problem vorlegen würde und die von Ihnen bereitgestellte Lösung - unter Berücksichtigung der Zeit und Ihrer Bedürfnisse - brachial und hässlich wäre, würde ich Ihnen eine Reihe von Fragen stellen, warum dies der Fall ist. und was würde es zu etwas Eleganterem machen: mehr Informationen? mehr Zeit? eine andere Umgebung? Sich selbst bewusst zu sein und mit dem Warum von dem, was Sie getan haben, und dem, was Sie nicht getan haben, in Berührung zu kommen und es rational erklären zu können, ist ein großer goldener Stern in meinem Buch, aber das sind die Arten von Entwicklern, die ich suchen. "Ausgezeichnetes Problemverständnis und eine elegante Lösung" würde also auch für mich funktionieren, aber nicht für alle.

jcmeloni
quelle
6
Plus eine Million für "Selbstbewusstsein und Kontakt mit dem Warum von dem, was Sie getan haben und was Sie nicht getan haben, und in der Lage zu sein, es rational zu erklären, ist ein großer goldener Stern in meinem Buch" . Die Anzahl der Leute, die auf die Frage "Warum?" Nur Gründer sind und nicht antworten können, ist unglaublich. Bei der Einstellung würde ich fast immer lieber jemanden lehren, der selbst denken kann, als jemanden einzustellen, der kodieren kann, aber nicht denken kann.
Ben
Vielen Dank. Das ist aufschlussreich. Meine berufliche Neigung besteht darin, vor dem Berühren der Tastatur zu analysieren. Aber unter dem Druck eines Interviews möchte ich verzweifelt eine Programmierlösung zeigen . Stackexchange.com/questions/178075/.
GlenPeterson
4

Ich möchte beides, aber sie zeigen möglicherweise einen "Code an, der nur funktioniert" in einer Lösung und diskutieren dann möglicherweise mögliche Lösungen zur Verbesserung des einen oder anderen Problems.

Wenn Sie jemanden bitten, Code zu schreiben, und dieser nur über mögliche Lösungen mit Nullcode sprechen möchte, ist dies ein Problem.

Wie Sie sagten, kann jemand mit dem bestimmten Problem aus irgendeinem Grund kämpfen, aber Sie müssen lernen, wie er vorgeht, um es zu lösen. Sie könnten Glück haben und haben bereits von einer Lösung für ein ähnliches Problem gehört. Es passiert.

Beobachten Sie, wie jemand genug Code schreibt und darüber diskutiert, und Sie können herausfinden, ob er für den Job geeignet ist.

JeffO
quelle
1
Ich würde auch gerne hören, warum die Brute-Force-Lösung ein Problem sein könnte, wie in der obigen Frage.
Christopher Creutzig
@ChristopherCreutzig - Ich ging davon aus, dass es schwierig sein würde, Verbesserungen anzubieten, ohne zumindest die Probleme mit der aktuellen Lösung vorzuschlagen.
JeffO
Wahr. Ich denke, ich werde das kratzen.
Christopher Creutzig
3

Gibt es eine Regel, die besagt, dass Sie nach 20 Minuten mit dem Codieren beginnen sollten, egal was passiert?

Nein, aber wenn Sie 20 Minuten damit verbringen, das Problem zu analysieren, bevor Sie sich an die Arbeit machen, stecken Sie wahrscheinlich bereits in Schwierigkeiten. Ein Arbeitgeber, der Ihnen eine Frage stellt, wie Sie sie zitiert haben, ist hauptsächlich daran interessiert, wie Sie sich einem Problem nähern. Wenn er sie jedoch als Codierungsproblem fragt, möchte er auch Code sehen. Sprechen Sie sie durch Ihren Denkprozess ...

Nun, der offensichtliche Ansatz ist hier rohe Gewalt. Wenn ich in Anbetracht der drei Eckpunkte ein rechtwinkliges Dreieck erkennen könnte, könnte ich alle Kombinationen aus zwei Punkten und dem Ursprung durchlaufen, um nach rechtwinkligen Dreiecken zu suchen. Das sollte nicht schwer sein - ich kann eine Funktion schreiben, die den Satz von Pythagoras verwendet, um rechtwinklige Dreiecke zu identifizieren. Um dies zu vereinfachen, schreibe ich auch eine Funktion, die den Abstand zwischen zwei Punkten mithilfe der Abstandsformel bestimmt ...

Das Schreiben dieser Funktionen sollte ungefähr drei Minuten dauern. Nach wenigen Minuten haben Sie bereits gezeigt, dass Sie sich an die grundlegende Geometrie erinnern und wirklich wissen, wie man Code schreibt. Es gibt Ihnen auch etwas zu besprechen:

Wir könnten also die isRightTriangle(p1, p2, p3)Funktion offensichtlich in die Mitte von vier forSchleifen setzen und alle möglichen Auswahlen für jeden der beiden variablen Punkte durchlaufen. Mal sehen ... das Problem fragt nach der Anzahl der rechtwinkligen Dreiecke, einschließlich des Ursprungs in einem 50x50-Raster. Wenn wir also die Brute-Force-Methode verwenden, überprüfen wir 50 Möglichkeiten für jede Koordinate jedes Punkts. Das sind 50 ^ 4 Schecks ... Ich bin sicher, wir können es besser machen, aber der Code ist offensichtlich, also lass mich das aufschreiben ...

Nun schreiben Sie eine Funktion, die verschachtelte forSchleifen verwendet, und die isRightTriangle()Funktion, die Sie gerade geschrieben haben. Sie haben das Problem gelöst, aber Sie haben auch den Interviewer sehen lassen, wohin Sie gehen. Wenn ihr Ziel nur darin bestand, zu sehen, dass Sie Code schreiben können, werden Sie möglicherweise aufgefordert, damit aufzuhören. Wahrscheinlich sind sie froh, mit jemandem zu sprechen, der weiß, was sie tun, und sie werden sehen wollen, wie weit Sie damit kommen. Also mach weiter ...

Mir ist beim Schreiben eingefallen, dass wir die Symmetrie ausnutzen können. Wir können ein beliebiges rechtwinkliges Dreieck um die 45 ° -Linie spiegeln. Wenn wir also einen der Punkte nur auf einer Seite dieser Linie markieren, können wir alle rechtwinkligen Dreiecke, die wir finden, einfach zweimal zählen ... einmal für das Dreieck und einmal für sein Spiegelbild. Das halbiert die Anzahl der Schecks. Wenn wir es uns jetzt ansehen, nehmen wir eine Quadratwurzel, um den Abstand zwischen zwei Punkten zu finden, aber dann quadrieren wir das einfach noch einmal in isRightTriangle()...

Und so weiter. Auch hier wollen sie normalerweise keine perfekte Lösung sehen, sie wollen sehen, wie man zu einer Lösung kommt. Ihr Denkprozess muss nicht so sein wie oben - nur das Selbstvertrauen, laut zu denken, wird eine Menge ausmachen. Schwitzen Sie nicht, wenn Sie einen Fehler machen - sagen Sie einfach "hmmm, ich glaube, ich bin hier von den Schienen geraten - lassen Sie mich einen Schritt zurückgehen ..."

Caleb
quelle
1
Sehr nette Antwort. Ich mag besonders: "Ich bin sicher, wir können es besser machen, aber der Code ist offensichtlich, also lassen Sie mich das aufschreiben ..."
GlenPeterson
3

Wenn ich Sie als Manager auffordere, als Test zu programmieren, interessiert mich Folgendes:

  • Ob Sie Code schreiben können
  • Ihr Codierungsstil
  • Der von Ihnen ausgewählte Algorithmus
  • Zeigt der Versuch an, dass Sie das Problem verstanden haben?
  • Wenn ich wirklich scharf auf eine bestimmte Technologie bin, haben Sie bewiesen, dass Sie es mehr oder weniger wissen.

Der erste Punkt mag verrückt erscheinen, aber Sie wären überrascht ...

Coding-Stil - damit meine ich nicht nur, wo Sie Ihre Zahnspange setzen, sondern Dinge wie:

  • Haben Sie Komposition oder Vererbung gewählt, um dieses Problem zu lösen? Warum?
  • Warum haben Sie für diesen Wert die Option "enum vs. string vs. int" gewählt (oder was auch immer für eine Permutation gilt)?
  • Haben Sie Eigenschaften, Felder oder Get / Set-Methoden für diesen Wert verwendet? Warum?
  • Wie sind Sie in Ihrem Unterricht mit dem Staat umgegangen?
  • Verstehen Sie, wie Vererbung, Schnittstellen und Lambdas funktionieren?
  • Verstehst du die Parameterkonventionen der Sprache?
  • Wissen Sie, wie man Komponententests schreibt?

Hier ist , was ich wirklich nicht tun interessieren:

  • Dass es kompiliert (vorausgesetzt, ich habe Ihnen gerade Notepad und keinen Compiler gegeben)
  • Dass Sie die Reihenfolge dieser 2 Parameter in dieser einen Funktion auswendig kannten
  • Dass Sie eine SQL Server- oder Oracle-Verbindungszeichenfolge auswendig können
  • Dass Sie perfekt codieren können, während ich über Ihre Schulter stehe und jeden Fehler beobachte.

Ehrlich gesagt war ich nie ein großer Fan von Codierungstests - außer als Werkzeug zur Stilanalyse.

JMarsch
quelle
1
Ich bin auch kein großer Fan von Codingtests. Die Probleme in Project Euler sind interessante Denksportaufgaben und eine großartige Möglichkeit, um Fähigkeiten zur Problemlösung zu entwickeln. Aber wenn Sie hauptsächlich CRUD-Apps schreiben, ist es besser zu wissen, ob ein Kandidat weiß, wie man gute DB-Abfragen schreibt, oder, wenn Sie in der .NET-Welt wie ich sind, wie man Dinge wie MVC, WCF, WPF und richtig verwendet LINQ.
Jfrankcarr
1
Ich möchte diesem Kommentar hinzufügen, dass nicht einmal die Semantik eine Rolle spielt, sondern vielmehr, welche Art von Problemen diese Dinge lösen und wann und wo sie eine Rolle spielen und welche Nachteile sie haben.
Rig
@jfrankcarr - wie stellst du fest, ob jemand SQL ohne irgendeine Art von Test schreiben kann?
JeffO
1
@JeffO - Ich mache es im Allgemeinen gerne, indem ich ein Gespräch darüber auf der Grundlage ihres Lebenslaufs oder allgemeiner Szenarien führe. Beispiel: "Haben Sie in Ihren Abfragen Tabellenvariablen oder temporäre Tabellen verwendet?" oder "Wie haben Sie ältere Datenabfragen in das Design Ihrer neuen App integriert?" Ich kann auf Tests zurückgreifen, wenn ich einen Junior-Programmierer anstelle, der gerade nicht zur Schule geht, aber ich bevorzuge den offenen Konversationsansatz.
Jfrankcarr
1

In diesem Fall ist der Weg zu einer eleganten Lösung besser als zu einer schlechten, aber vollständigen Lösung. Beide Fälle sind jedoch gut. Es ist absolut in Ordnung, einen Pusdocode aufgeschrieben zu haben, der zeigt, dass Sie das Problem verstehen und wie Sie es lösen wollen, auch wenn Sie keine Zeit hatten, das Programm tatsächlich zu codieren.

Tom Squires
quelle
1

Ich denke, Sie stellen eine Frage, auf die es eigentlich keine Antwort gibt, geschweige denn eine „richtige“ Antwort. Der Grund, warum ich das sage, ist, dass es ganz davon abhängt, was die Person, die die Frage stellt, bewertet.

Es ist möglich, dass der Interviewer ein eingefleischter Pragmatiker ist, der wirklich versucht, etwas schnell zum Laufen zu bringen und es dann als Aktivität mit niedrigerer Priorität zu optimieren, wenn Sie noch Zeit haben. Ebenso ist es möglich, dass der Interviewer seinen besten Eindruck von den Einstellungspraktiken von Google gewinnt und sich für nichts anderes als den sexy, elegantesten Algorithmus interessiert. Dies ist ein Zeichen der Schwäche, dass Sie jemals die Wörter "brute" und "brachial" verwendet haben. Kraft "innerhalb von 5 Wörtern voneinander. Genauso gut ist es möglich, dass der Interviewer "Interviewfragen" gegoogelt hat und dieses Problem 5 Minuten vor Ihrer Ankunft im Internet gefunden hat und keine Ahnung hat, was er will.

In jedem Fall ist es wahrscheinlich am besten, nach einer Klärung zu fragen, wenn Sie anhand der Kontextinformationen nicht ableiten können, was der Interviewer will. Sie haben Recht, dass nicht alle Interviewfragen fair sind, und in der Tat sind nicht alle gute oder sogar sinnvolle Fragen. Ein Interview ist von Natur aus eine reduktionistische Aktivität, ähnlich wie "Speed-Dating", bei dem Sie ein oder zwei Stunden mit jemandem verbringen und anhand dieser Stunde zu erraten versuchen, ob Sie für das nächste Mal gut zusammenarbeiten werden 5 Jahre oder nicht. Aus dieser Perspektive betrachtet, hoffe ich, dass es klarer ist, warum ich sage, dass es auf Ihre Frage nach einer „Regel“ wirklich keine Antwort gibt.

Jemand stellt Ihnen eine Frage, von der er denkt, dass sie Ihnen einen Einblick in Ihre Kompetenz gibt und zu seinem Team passt. Sie müssen sich das Team ansehen, was Sie über sie wissen, die Persönlichkeit des Interviewers und Dutzende anderer Faktoren, und eine bestmögliche Schätzung abgeben, welche Antworten, Herangehensweisen und Prozesse sie wahrscheinlich zu schätzen wissen. Persönlich würde ich sagen, dass Sie es so angehen sollten, wie Sie es für die beste Idee halten. Wenn sie nicht mit Ihnen übereinstimmen, könnte es ohnehin keine gute Passform haben - es ist einfacher, dies früher als später herauszufinden.

Erik Dietrich
quelle
0

Die Interviewer werden Sie bitten, Ihre Lösung trotzdem zu verbessern.

Und der Ansatz "Brute-Force-Lösung zuerst" hat einen unbestreitbaren Vorteil: Wenn Sie keine ideale Lösung finden, haben Sie immer noch etwas Abgeschlossenes, um sie aufzuzeigen.

Wirbelwolf
quelle
1
"Die Interviewer werden Sie trotzdem bitten, Ihre Lösung zu verbessern." Scheint mir ein Glücksspiel zu sein.
Craige
1
@Craige: Nicht wirklich. Aber wenn sie es nicht ansprechen. Angenommen, dies ist eine Brute-Force-Lösung, mit der die Analyse verbessert werden kann.
Martin York