Neulich bei einem Vorstellungsgespräch bekam ich folgendes Problem:
Schreiben Sie ein Skript, das in der Befehlszeile als python
Es sollte zwei Wörter in der Befehlszeile enthalten (oder optional, wenn Sie es vorziehen, kann es den Benutzer abfragen, um die zwei Wörter über die Konsole zu liefern).
Mit diesen zwei Worten: ein. Stellen Sie sicher, dass sie gleich lang sind b. Stellen Sie sicher, dass beide Wörter im Wörterbuch der gültigen Wörter in der englischen Sprache vorhanden sind dass Sie heruntergeladen haben.
Wenn ja, berechnen Sie, ob Sie das zweite Wort vom ersten durch eine Reihe von Schritten wie folgt erreichen können ein. Sie können jeweils einen Buchstaben ändern b. Jedes Mal, wenn Sie einen Buchstaben ändern, muss das resultierende Wort auch im Wörterbuch vorhanden sein c. Sie können keine Buchstaben hinzufügen oder entfernen
Wenn die beiden Wörter erreichbar sind, sollte das Skript den Pfad ausgeben, der als einzelner, kürzester Pfad von einem Wort zum anderen führt.
Sie können / usr / share / dict / words für Ihr Wörterbuch von Wörtern verwenden.
Meine Lösung bestand darin, die erste Suche nach Breite zu verwenden, um den kürzesten Weg zwischen zwei Wörtern zu finden. Aber anscheinend war das nicht gut genug, um den Job zu bekommen :(
Würdest du wissen, was ich falsch gemacht haben könnte? Vielen Dank.
%Vor%Danke für die tollen Antworten. Ich denke, was mich wirklich dazu gebracht hat, ist die Tatsache, dass ich jedes Mal ALLE Wörter im Wörterbuch wiederhole, um mögliche Wortnachbarn zu berücksichtigen. Stattdessen hätte ich einen invertierten Index verwenden können, auf den Duncan und Matt Anderson hingewiesen hatten. Ein * -Ansatz hätte bestimmt auch geholfen. Vielen Dank, jetzt weiß ich, was ich falsch gemacht habe.
Hier ist der gleiche Code mit invertiertem Index:
%Vor%Und ein Timing-Vergleich:
% python one_letter_game_old.py glücklich Hallo der kürzeste Weg (gefunden in 91,57 Sek.) Ist:
= & gt; glücklich - Harpyie - Harfe - Harts - Halts - Hallen - Höllen - Hallo% python one_letter_game.py glücklich Hallo der kürzeste Weg (gefunden in 1,71 sec.) Ist:
= & gt; glücklich - Harpyie - Harfe - Harts - Halts - Hallen - Höllen - Hallo
Ich würde nicht sagen, dass Ihre Lösung falsch ist, aber es ist ein wenig langsam. Aus zwei Gründen.
Die Breite-zuerst-Suche wird alle Pfade der Länge, die kürzer als benötigt sind, sowie einige der benötigten Pfade der Länge besuchen, bevor sie Ihnen eine Antwort geben können. Eine Best-First-Suche (A *) wird idealerweise die meisten irrelevanten Pfade überspringen.
Sie überprüfen jedes Wort im Wörterbuch auf Kandidatur als Nachbar jedes Mal, wenn Sie nach Nachbarn suchen. Wie Duncan vorschlägt, können Sie eine Datenstruktur aufbauen, die im Wesentlichen die Nachbarn nachschlägt, anstatt nach ihnen zu suchen.
Hier ist eine andere Lösung für Ihr Problem:
%Vor%Und ein Timing-Vergleich:
%Vor%Ich stimme zu, dass es seltsam wäre zu erwarten, dass Ihre Antwort auf diesen Programmiertest der einzige Grund ist, warum sie sich für jemand anderen entschieden haben, aber es gibt tatsächlich Probleme mit Ihrem Code. Sie durchsuchen das Wörterbuch linear nach jedem Schritt des Pfades oder nach jedem möglichen Pfad. Das könnte lange dauern für ein großes Wörterbuch und viele mögliche Pfade. Es ist auch ziemlich offensichtlich, dass Sie es nicht gründlich getestet haben, da es fehlschlägt, wenn es keinen Pfad gibt.
Wenn ich das programmieren würde, würde ich ein Wörterbuch erstellen, wenn ich die Wörter lese, die die lineare Suche entfernen würden, indem ich die nächsten Wörter direkt auswählen kann. Dieser Code ist nicht die vollständige Lösung, sollte aber angeben, was ich meine:
%Vor%Vielleicht erwarteten sie die A * Suche mit der Bearbeitungsdistanz als Schätzung?
Vielleicht wolltest du ja gar nicht erst bei einer solchen Firma arbeiten. Ich persönlich glaube nicht an Code-Reviews. Ich denke, wenn Sie eine gute Arbeit machen mit dem Auschecken des Portfolios und der Vergangenheit Referenzen, dass es keine Notwendigkeit für solche bei den Spot-Code-Tests. Unternehmen mit strengen Richtlinien wie diesen sind diejenigen, die es nie schaffen, da sie nur einen Track-Code-Nerd einsetzen, der Code 24/7 denkt. Nur meine 2 Cent.
Vielleicht hast du vergessen, den Shebang hinzuzufügen? & gt; - |
Oder vielleicht haben sie Ihren Programmierstil einfach nicht gemocht ... Zum Beispiel hätte ich keine Klasse für solch ein einfaches Problem gemacht, es ist die Lösung der Lösung (obwohl ich nicht so wählerisch bin) die Einstellungsentscheidung nur darauf natürlich).
Tags und Links python optimization letter