Da bist du also. Erleichtert. Erschöpft. Sie haben endlich einen Ansatz gefunden, um die knifflige Codierungsfrage zu lösen, die Ihr Interviewer Ihnen stellt. Vielleicht haben Sie es sogar Zeile für Zeile auf die Pinnwand geschrieben. Und du hast gute Zeit gemacht! Sie sind nur 20 Minuten in der Besprechung. Ihr Interviewer muss beeindruckt sein.
Recht?
"Das wird funktionieren, aber gibt es Ideen, wie man es effizienter macht?"
Dein Herz sinkt. Sie dachten, Sie wären mit dem kniffligen Algorithmus-Design fertig! Sie versuchen, mehr Möglichkeiten zur Lösung des Problems zu finden, aber Sie können sich nur den einen Ansatz vorstellen, den Sie sich bereits ausgedacht haben.
Das passiert fast jedem. Und es ist nicht, weil sie dumm sind. Das liegt daran, dass die meisten Menschen keine Methode zur Verbesserung der Effizienz ihrer Algorithmen haben.
Aber die Wahrheit ist, es gibt viele. Wenn Sie das nächste Mal ratlos sind, versuchen Sie, diese drei gängigen Ansätze anzuwenden.
1. Verwenden Sie eine Hash-Karte
Stimmt. Hash-Maps / assoziative Arrays / Wörterbücher (je nach verwendeter Programmiersprache mit vielen Namen) können die Laufzeit von Algorithmen auf magische Weise verkürzen.
Angenommen, die Frage bestand darin, die am häufigsten wiederholte Zahl in einem Array von Zahlen zu finden.
Ihr erster Gedanke könnte sein, in einige Schleifen zu springen. Ermitteln Sie für jede unserer Zahlen die Anzahl und prüfen Sie, ob es die größte ist. Wie erhalten wir die Zählung für jede Zahl? Durchlaufen Sie das Array und zählen Sie, wie oft es auftritt! Wir sprechen also von zwei verschachtelten Schleifen. Im Pseudocode:
def get_mode (nums): max_count = 0 mode = null für potential_mode in nums: count = 0 für number in our_array: count + = 1 wenn count> = max_count: mode = potential_mode max_count = count return mode
Im Moment durchlaufen wir unser gesamtes Array einmal für jedes Element im Array - aber wir können es besser machen. In der großen O-Notation ist das insgesamt O (n 2 ) -Zeit.
Wenn wir unsere Zählungen in einer Hash-Map speichern (Nummern den Zählungen zuordnen), können wir das Problem in nur einem Durchgang durch das Array lösen (O (n) Zeit!):
def get_mode (nums): max_count = 0 mode = null counts = new HashMap, wobei jeder Wert für potential_mode in nums mit 0 beginnt: counts + = 1, wenn counts> max_count: mode = potential_mode max_count = counts return mode
Viel schneller!
2. Verwenden Sie die Bit-Manipulation
Dies wird Sie wirklich von der Masse abheben. Es gilt nicht für jedes Problem, aber wenn Sie dies in Ihrer Gesäßtasche aufbewahren und zur richtigen Zeit herausholen, sehen Sie aus wie ein Rockstar.
Hier ist ein Beispiel: Angenommen, wir hatten ein Array von Zahlen, bei dem jede Zahl zweimal vorkommt, mit Ausnahme einer Zahl, die nur einmal vorkommt. Wir schreiben eine Funktion, um die einsame, nicht wiederholte Zahl zu finden.
Ihr erster Instinkt könnte darin bestehen, eine Hash-Map zu verwenden, da wir gerade darüber gesprochen haben. Das ist ein guter Instinkt! Und es wird für diesen funktionieren. Wir können eine sehr ähnliche "Zählungs" -Karte erstellen und anhand dieser sehen, welche Zahl mit einer Zählung von 1 endet.
Aber es gibt noch einen besseren Weg. Wenn Sie mit Bit-Manipulationen vertraut sind, sind Sie möglicherweise mit XOR vertraut. Das Besondere an XOR ist, dass, wenn Sie eine Zahl mit sich selbst XORen, die Bits auf 0 "auslöschen". Wenn wir für dieses Problem jede Zahl im Array XORen, bleiben wir bei der einen Zahl, die nicht XORen konnte nicht stornieren:
def find_unrepeated (nums): nicht wiederholt = 0 für num in nums: nicht wiederholt = nicht wiederholt XOR num return nicht wiederholt
3. Gehen Sie von unten nach oben
Schreiben Sie eine Funktion, die die “n-te” Fibonacci-Zahl mit der Zahl n ausgibt. Dies ist ein Klassiker und eignet sich sehr gut für Rekursionen:
def fib (n): wenn n 0 oder 1 ist: return 1 return fib (n-1) + fib (n-2)
Aber die einfache rekursive Antwort ist nicht die einzige! Überlegen Sie genau, was diese Funktion bewirkt. Angenommen, n ist 5. Um die Antwort zu erhalten, werden fib (4) und fib (3) rekursiv aufgerufen. Was macht dieser Aufruf von fib (4)? Es nennt sich fib (3) und fib (2). Aber wir sagten nur, wir hätten bereits einen Anruf bei fib (3)! Diese nette rekursive Funktion erledigt viel Wiederholungsarbeit. Die Gesamtzeitkosten betragen O (2 n ). Das ist schlimm - viel schlimmer als O (n 2 ).
Anstatt rekursiv von n auf 1 zu gehen, gehen wir von 1 auf n. So können wir die Rekursion überspringen:
def fib (n): previous = 0 previous_previous = 1 für i im Bereich von 1 bis n: current = previous + previous_previous previous_previous = previous previous = current Rückstrom
Der Code ist länger, aber viel effizienter! Bis zu O (n) Zeit. Als zusätzlichen Vorteil beim Abrollen rekursiver Algorithmen sparen wir Platz. Alle diese rekursiven Aufrufe werden im Aufrufstapel aufgebaut, der sich im Speicher befindet und auf unsere Platzkosten angerechnet wird. Unsere rekursive Funktion hatte O (n) Platzkosten, aber diese iterative benötigt O (1) Platz.
Wenn Sie Ihr Interviewer das nächste Mal auffordert, die Effizienz Ihrer Lösung zu verbessern, versuchen Sie, diese Strategien durchzugehen und zu prüfen, ob sie helfen. Wenn Sie genug Übung haben, werden Sie wahrscheinlich direkt zu der optimierten Lösung springen und die naivere Lösung überspringen. Und das ist eine großartige Sache. Es bedeutet nicht nur, dass Sie ein besserer Interviewer werden - es bedeutet, dass Sie ein besserer Ingenieur werden.
