Von einem Übersetzer : Wir veröffentlichen für Sie eine Übersetzung eines Artikels von Steve Merrit , einem Google-Mitarbeiter, der darüber spricht, wie er typische Programmierprobleme löst. Der Beitrag wird vor allem für Programmieranfänger nützlich sein.In diesem Artikel werde ich über meine Strategie zur Lösung von Problemen sprechen, die während der Arbeit an einem Projekt von Anfang bis Ende auftreten. Ich verwende es im täglichen Workflow bei Google sowie bei der Arbeit mit Programmierern aller Ebenen (Kollegen, Absolventen von Bootcamps, Studenten). Eine strukturierte Technik minimiert den Zeitaufwand für das Debuggen und führt gleichzeitig zur Erstellung eines besseren Codes.
Übrigens funktioniert dieselbe Strategie häufig bei Interviews in großen Technologieunternehmen. Vor drei Jahren bekam ich dank ihr einen Job bei Google.
Wir erinnern Sie daran: Für alle Leser von „Habr“ - ein Rabatt von 10.000 Rubel bei der Anmeldung für einen Skillbox-Kurs mit dem Promo-Code „Habr“.
Skillbox empfiehlt: Der Online-Schulungskurs "Profession Java-Entwickler" .
Schritt für Schritt
Ich werde Beispiele in Form typischer Probleme zeigen, um das Thema aufzuzeigen.
Problem: „Bei zwei Zeilen, sourceString und searchString, müssen Sie den ersten Index zurückgeben, wenn sourceString in searchString angezeigt wird. Wenn searchString nicht in sourceString enthalten ist, geben Sie -1 zurück. "
1. Zeichne es
Es ist keine gute Idee, sofort mit dem Schreiben von Code zu beginnen. Zuerst müssen Sie einen Weg zur Lösung des Problems skizzieren. Bilden Sie zunächst eine Hypothese und einen Beweis für Ihren Standpunkt. Und machen Sie sich erst an die Arbeit, wenn Sie bereits einen klaren Plan haben. Wenn dies nicht getan wird, können Sie, wenn die Arbeit bereits begonnen hat, auf die Tatsache stoßen, dass einzelne Codeteile nicht miteinander korrespondieren.
Die Lösung kann oft nicht trivial sein, selbst wenn die Aufgabe einfach aussieht. Die Papierplanung hilft Ihnen, den richtigen Ansatz zu finden und sicherzustellen, dass er in anderen Situationen funktioniert. Und das alles lernen Sie schon, bevor die erste Codezeile geschrieben wird.
Beginnen Sie also nicht mit dem Schreiben von Code, sondern denken Sie nicht einmal darüber nach. Sie haben viel Zeit zum Arbeiten. Sie sind ein menschlicher Computer und lösen das Problem.
Schreiben Sie den Lösungsalgorithmus auf Papier. Wenn Ihnen etwas hilft, Ihren Plan zu visualisieren, tun Sie es. Die Aufgabe besteht darin, das Problem mit Bleistift und Papier ohne Tastatur zu lösen.
Überlegen Sie sich eine einfache Eingabe. Wenn die Funktion "den String übergibt", ist "abc" das erste hervorragende Beispiel. Versuchen Sie zu verstehen, was das richtige Ergebnis sein sollte. Überlegen Sie dann, wie Sie das Problem verstanden haben und welche Schritte unternommen wurden.
Stellen Sie sich vor, dass Zeichenfolgen die folgenden Werte haben:
sourceString: "abcdyesefgh"
searchString: "yes"Wir können also sehen, dass searchString in sourceString enthalten ist. Aber wie sind wir dazu gekommen? Wir haben am Anfang von sourceString begonnen und es bis zum Ende gelesen. Dabei haben wir jedes dreistellige Fragment untersucht, um festzustellen, ob es mit dem Wort „yes“ übereinstimmt. Zum Beispiel "abc", "bcd", "cde" und so weiter. Als wir zu Index 4 kamen, fanden wir „Ja“ und entschieden daher, dass es eine Übereinstimmung gab, und sie beginnt bei Index 4.
Ich hatte einen Lehrer am Institut, der sich die Aufgabe stellte, Anweisungen für die Herstellung eines Erdnussbuttersandwichs zu erarbeiten. Für eine detaillierte und verständliche Anleitung versprachen sie uns die höchste Bewertung.
Ich habe folgendes geschrieben:
„Öffne die Erdnussbutter und verteile sie auf dem Brot. Lege ein weiteres Stück Brot darauf und du bist fertig. “
Ich dachte, ich hätte es geschafft, bis der Lehrer die Butter nahm und auf dem Brot verteilte, das sich noch in einer Plastiktüte befand.
Programme, wie mein Lehrer, erfordern sehr detaillierte Anweisungen, um die Aufgabe zu ermöglichen. Daher stellen wir bei der Erstellung des Algorithmus sicher, dass wir alles bereitstellen - alle möglichen Szenarien. Die richtige Antwort zurückzugeben, wenn die Übereinstimmung GEFUNDEN ist, ist ausgezeichnet, aber es ist notwendig, die Antwort zurückzugeben, auch wenn die Übereinstimmung NICHT GEFUNDEN ist.
Versuchen wir es noch einmal mit einem anderen Zeilenpaar:
sourceString: "abcdyefg"
searchString: "yes"Hier haben wir am Anfang von sourceString begonnen und es bis zum Ende gelesen. Dabei haben wir jedes dreistellige Fragment untersucht, um festzustellen, ob es mit dem Wort „yes“ übereinstimmt. Als wir zu Index 4 kamen, fanden wir yef, was fast ein Zufall war, aber unvollständig, da das dritte Zeichen anders war. Daher lasen wir weiter, bis wir das Ende der Zeile erreichten, und entschieden dann, dass es keine Übereinstimmung gab, also gaben wir -1 zurück.
Wir haben eine Reihe von Schritten erstellt (bei der Programmierung wird dies als Algorithmus bezeichnet), die wir ausführen, um das Problem zu lösen, und wir haben versucht, mehrere Szenarien auszuführen, um jedes Mal das richtige Ergebnis zu erzielen. Im Moment können wir sicher sein, dass unser Algorithmus funktioniert, und jetzt ist es Zeit, ihn zu formalisieren, was uns zum nächsten Schritt führt.
2. Wir schreiben den Algorithmus in Worten
Dies macht die Schritte real, was bedeutet, dass wir später beim Schreiben des Codes darauf verweisen können.
- Beginnen Sie am Anfang der Zeile.
- Wir sehen uns alle dreistelligen Kombinationen an (oder wie viele Zeichen in searchString angegeben sind).
- Wenn einer von ihnen gleich searchString ist, geben wir den aktuellen Index zurück.
- Wenn wir am Ende der Zeile angelangt sind, ohne eine Übereinstimmung zu finden, geben Sie -1 zurück.
3. Wir schreiben einen Pseudocode
Pseudocode ist nicht wirklich ein Code, aber er gibt vor, ein Code zu sein. Ein Beispiel dafür, wovon ich angesichts unseres Algorithmus spreche:
for each index in sourceString,
there are N characters in searchString
let N chars from index onward be called POSSIBLE_MATCH
if POSSIBLE_MATCH is equal to searchString, return index
at the end, if we haven't found a match yet, return -1.Ich kann es noch mehr wie echten Code machen:
for each index in sourceString,
N = searchString.length
POSSIBLE_MATCH = sourceString[index to index+N]
if POSSIBLE_MATCH === searchString:
return index
return -14. Wir übersetzen alles, was wir können, in den Code
Jetzt müssen wir uns um die Syntax, Funktionsparameter und Sprachregeln kümmern. Vielleicht können Sie nicht alles schreiben, und das ist normal. Schreiben Sie in den Code, was Sie sicher wissen!
function findFirstMatch (searchString, sourceString) { let length = searchString.length; for (let index = 0; index < sourceString.length; index++) { let possibleMatch = <the LENGTH chars starting at index i> if (possibleMatch === searchString) { return index; } } return -1; }
Beachten Sie, dass ich einen Teil dieses Codes leer gelassen habe. Das ist beabsichtigt! Ich war mir der Syntax für die Verarbeitung von Zeichenfolgen in JavaScript nicht sicher, aber dazu später mehr.
5. Verlassen Sie sich nicht auf Glück
Ein ziemlich häufiger Fehler, insbesondere für unerfahrene Programmierer, besteht darin, etwas zu verwenden, das im Netzwerk gefunden wurde, in der Hoffnung, dass es einfach funktioniert. Das gefundene Fragment wird einfach ohne Test in Ihr eigenes Projekt eingefügt. Je mehr Abschnitte Ihres Programms Sie nicht verstehen, desto unrealistischer ist der erfolgreiche Abschluss der Arbeit.
Die Wahrscheinlichkeit eines Fehlers verdoppelt sich, wenn Sie Elemente hinzufügen, bei denen Sie sich nicht sicher sind. Infolgedessen gerät der Prozess einfach außer Kontrolle.
Kommentar: Die Wahrscheinlichkeit eines Fehlers kann mit der Mersenne-Sequenz berechnet werden: a (n) = (2 ^ n) - 1
Testen Sie Ihren Code. Es ist cool, etwas online zu finden, aber bevor Sie Ihrem Programm einen Ausschnitt hinzufügen, versuchen Sie diesen Abschnitt getrennt von allem.
Im vorherigen Schritt habe ich gesagt, dass ich nicht weiß, wie ich einen bestimmten Teil der Zeichenfolge mit JavaScript auswählen soll. Lass es uns googeln.
https://www.google.com/search?q=how+to+select+part+of+a+string+in+javascriptDas erste Ergebnis stammt von w3schools. Ein bisschen veraltet, wird aber funktionieren:
http://www.w3schools.com/jsref/jsref_substr.aspIch gehe davon aus, dass ich substr (index, searchString.length) verwenden sollte, um den sourceString-Teil jedes Mal hervorzuheben. Bisher ist dies jedoch eine Annahme und nichts weiter. Also werde ich es zuerst überprüfen.
let testStr = "abcdefghi"
let subStr = testStr.substr(3, 4); // simple, easy usage
console.log(subStr);
"defg"
subStr = testStr.substr(8, 5); // ask for more chars than exist
"i"Jetzt weiß ich genau, wie diese Funktion funktioniert. Wenn ich dieses Fragment zu meinem Programm hinzufüge, weiß ich bereits, dass das Problem nicht im hinzugefügten Abschnitt liegt, wenn es nicht funktioniert.
Und schließlich füge ich den letzten Teil des Codes hinzu.
function findFirstMatch(searchString, sourceString) { let length = searchString.length; for (let index = 0; index < sourceString.length; index++) { let possibleMatch = ( sourceString.substr(index, searchString.length)); if (possibleMatch === searchString) { return index; } } return -1; }
Fazit
Wenn Sie bis zum Ende gelesen haben, versuchen Sie den Tipp. Suchen Sie ein Problem, das Sie nicht lösen können. Ich garantiere, dass jetzt alles klappt.
Viel Glück und viel Spaß beim Codieren!
Skillbox empfiehlt: