Befolgen Sie diese Schritte, um alle Probleme mit Dynamic Programming-Interviews zu lösen

Trotz umfangreicher Erfahrung in der Entwicklung von Softwareprodukten sind viele Ingenieure nervös bei dem Gedanken, ein Codierungsinterview zu führen, das sich auf Algorithmen konzentriert. Ich habe Hunderte von Ingenieuren bei Refdash, Google und bei Startups interviewt, an denen ich beteiligt war, und einige der häufigsten Fragen, die Ingenieure unruhig machen, betreffen die dynamische Programmierung (Dynamic Programming, DP).

Viele Technologieunternehmen stellen DP-Fragen gerne in ihren Interviews. Während wir darüber diskutieren können, ob sie die Fähigkeit einer Person, eine technische Rolle zu übernehmen, effektiv bewerten, ist DP weiterhin ein Bereich, der Ingenieure auf ihrem Weg zur Suche nach einem Job, den sie lieben, auf Trab hält.

Dynamische Programmierung - vorhersehbar und vorbereitbar

Einer der Gründe, warum ich persönlich der Meinung bin, dass DP-Fragen möglicherweise nicht der beste Weg sind, um die technischen Fähigkeiten zu testen, ist, dass sie vorhersehbar und einfach zu finden sind. Sie ermöglichen es uns, viel mehr nach Bereitschaft zu filtern als nach technischen Fähigkeiten.

Diese Fragen scheinen von außen normalerweise ziemlich komplex zu sein und können den Eindruck erwecken, dass eine Person, die sie löst, sehr gut mit Algorithmen umgehen kann. In ähnlicher Weise scheinen Menschen, die möglicherweise nicht in der Lage sind, über einige umwerfende Konzepte von DP hinwegzukommen, in ihren Kenntnissen über Algorithmen ziemlich schwach zu sein.

Die Realität sieht anders aus, und der größte Faktor für ihre Leistung ist die Bereitschaft. Stellen wir also sicher, dass alle darauf vorbereitet sind. Ein für alle Mal.

7 Schritte zum Lösen eines dynamischen Programmierproblems

Im Rest dieses Beitrags werde ich ein Rezept durchgehen, das Sie befolgen können, um herauszufinden, ob ein Problem ein „DP-Problem“ ist, sowie um eine Lösung für ein solches Problem zu finden. Im Einzelnen werde ich die folgenden Schritte ausführen:

  1. So erkennen Sie ein DP-Problem
  2. Problemvariablen identifizieren
  3. Drücken Sie die Wiederholungsbeziehung deutlich aus
  4. Identifizieren Sie die Basisfälle
  5. Entscheiden Sie, ob Sie es iterativ oder rekursiv implementieren möchten
  6. Memoisierung hinzufügen
  7. Bestimmen Sie die zeitliche Komplexität

Beispiel DP Problem

Um ein Beispiel für Abstraktionen zu haben, die ich machen werde, möchte ich ein Beispielproblem vorstellen. In jedem der Abschnitte werde ich auf das Problem verweisen, aber Sie können die Abschnitte auch unabhängig vom Problem lesen.

Problemstellung:

In diesem Problem sind wir auf einem verrückten Sprungball und versuchen anzuhalten, während wir Stacheln auf dem Weg vermeiden.

Hier sind die Regeln:

1) Sie erhalten eine flache Landebahn mit ein paar Stacheln. Die Landebahn wird durch ein boolesches Array dargestellt, das angibt, ob ein bestimmter (diskreter) Punkt frei von Spitzen ist. Es ist wahr für klar und falsch für nicht klar.

Beispiel für eine Array-Darstellung:

2) Sie erhalten eine Startgeschwindigkeit S. S ist zu jedem Zeitpunkt eine nicht negative Ganzzahl und gibt an, wie weit Sie sich beim nächsten Sprung vorwärts bewegen werden.

3) Jedes Mal, wenn Sie auf einem Punkt landen, können Sie Ihre Geschwindigkeit vor dem nächsten Sprung um bis zu 1 Einheit anpassen.

4) Sie möchten sicher irgendwo auf der Landebahn anhalten (muss sich nicht am Ende des Arrays befinden). Sie hören auf, wenn Ihre Geschwindigkeit 0 wird. Wenn Sie jedoch zu irgendeinem Zeitpunkt auf einem Spike landen, platzt Ihr verrückter springender Ball und das Spiel ist vorbei.

Die Ausgabe Ihrer Funktion sollte ein Boolescher Wert sein, der angibt, ob wir irgendwo auf der Landebahn sicher anhalten können.

Schritt 1: Erkennen eines Problems mit der dynamischen Programmierung

Lassen Sie uns zunächst klarstellen, dass DP im Wesentlichen nur eine Optimierungstechnik ist. DP ist eine Methode zur Lösung von Problemen, indem sie in eine Sammlung einfacherer Teilprobleme zerlegt, jedes dieser Teilprobleme nur einmal gelöst und ihre Lösungen gespeichert werden. Wenn das nächste Mal dasselbe Teilproblem auftritt, suchen Sie einfach die zuvor berechnete Lösung nach, anstatt die Lösung neu zu berechnen. Dies spart Rechenzeit auf Kosten eines (hoffentlich) bescheidenen Speicherplatzaufwands.

Das Erkennen, dass ein Problem mit DP gelöst werden kann, ist der erste und oft schwierigste Schritt, um es zu lösen. Sie möchten sich fragen, ob Ihre Problemlösung als Funktion von Lösungen für ähnliche kleinere Probleme ausgedrückt werden kann.

Im Fall unseres Beispielproblems könnten wir anhand eines Punktes auf der Landebahn, einer Geschwindigkeit und der vor uns liegenden Landebahn die Stellen bestimmen, an denen wir möglicherweise als nächstes springen könnten. Darüber hinaus scheint es nur davon abzuhängen, ob wir mit der aktuellen Geschwindigkeit vom aktuellen Punkt anhalten können, ob wir von dem Punkt anhalten können, den wir als nächstes wählen.

Das ist eine großartige Sache, denn wenn wir vorwärts gehen, verkürzen wir die Landebahn und verkleinern unser Problem. Wir sollten in der Lage sein, diesen Prozess bis zu einem Punkt zu wiederholen, an dem es offensichtlich ist, ob wir aufhören können.

Das Erkennen eines dynamischen Programmierproblems ist oft der schwierigste Schritt zur Lösung. Kann die Problemlösung als Funktion von Lösungen für ähnliche kleinere Probleme ausgedrückt werden?

Schritt 2: Identifizieren Sie Problemvariablen

Jetzt haben wir festgestellt, dass zwischen unseren Teilproblemen eine rekursive Struktur besteht. Als nächstes müssen wir das Problem in Bezug auf die Funktionsparameter ausdrücken und sehen, welche dieser Parameter sich ändern.

Normalerweise haben Sie in Interviews einen oder zwei sich ändernde Parameter, aber technisch gesehen kann dies eine beliebige Zahl sein. Ein klassisches Beispiel für ein Problem mit einem sich ändernden Parameter ist „Bestimmen einer n-ten Fibonacci-Zahl“. Ein solches Beispiel für ein Problem mit zwei sich ändernden Parametern ist "Berechnen des Bearbeitungsabstands zwischen Zeichenfolgen". Wenn Sie mit diesen Problemen nicht vertraut sind, machen Sie sich darüber keine Sorgen.

Eine Möglichkeit, die Anzahl der sich ändernden Parameter zu bestimmen, besteht darin, Beispiele für mehrere Teilprobleme aufzulisten und die Parameter zu vergleichen. Das Zählen der Anzahl sich ändernder Parameter ist wertvoll, um die Anzahl der zu lösenden Teilprobleme zu bestimmen. Es ist auch an sich wichtig, um das Verständnis der Wiederholungsbeziehung ab Schritt 1 zu verbessern.

In unserem Beispiel können sich die beiden Parameter für jedes Teilproblem ändern:

  1. Array-Position (P)
  2. Geschwindigkeit (S)

Man könnte sagen, dass sich auch die Landebahn vor uns ändert, aber das wäre überflüssig, wenn man bedenkt, dass die gesamte unveränderte Landebahn und die Position (P) diese Informationen bereits enthalten.

Mit diesen 2 sich ändernden Parametern und anderen statischen Parametern haben wir nun die vollständige Beschreibung unserer Unterprobleme.

Identifizieren Sie die sich ändernden Parameter und bestimmen Sie die Anzahl der Teilprobleme.

Schritt 3: Drücken Sie die Wiederholungsbeziehung klar aus

Dies ist ein wichtiger Schritt, den viele durchlaufen, um in die Codierung einzusteigen. Wenn Sie die Wiederholungsbeziehung so klar wie möglich ausdrücken, wird Ihr Problemverständnis gestärkt und alles andere wird erheblich einfacher.

Sobald Sie herausgefunden haben, dass die Wiederholungsrelation besteht, und die Probleme in Bezug auf Parameter spezifizieren, sollte dies ein natürlicher Schritt sein. Wie hängen Probleme zusammen? Mit anderen Worten, nehmen wir an, Sie haben die Teilprobleme berechnet. Wie würden Sie das Hauptproblem berechnen?

So denken wir in unserem Beispielproblem darüber:

Da Sie Ihre Geschwindigkeit um bis zu 1 einstellen können, bevor Sie zur nächsten Position springen, gibt es nur 3 mögliche Geschwindigkeiten und daher 3 Stellen, an denen wir als nächstes sein könnten.

Wenn unsere Geschwindigkeit S, Position P ist, könnten wir formeller von (S, P) gehen zu:

  1. (S, P + S) ; # wenn wir die Geschwindigkeit nicht ändern
  2. (S - 1, P + S - 1) ; # wenn wir die Geschwindigkeit um -1 ändern
  3. (S + 1, P + S + 1) ; # wenn wir die Geschwindigkeit um +1 ändern

Wenn wir einen Weg finden, um in einem der oben genannten Unterprobleme anzuhalten, können wir auch bei (S, P) anhalten. Dies liegt daran, dass wir von (S, P) zu einer der drei oben genannten Optionen wechseln können.

Dies ist normalerweise ein gutes Verständnis des Problems (einfache englische Erklärung), aber manchmal möchten Sie die Beziehung möglicherweise auch mathematisch ausdrücken. Rufen wir eine Funktion auf, die wir versuchen, canStop zu berechnen. Dann:

canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)

Woohoo, es scheint, als hätten wir unsere Wiederholungsbeziehung!

Wiederholungsrelation: Angenommen, Sie haben die Teilprobleme berechnet, wie würden Sie das Hauptproblem berechnen?

Schritt 4: Identifizieren Sie die Basisfälle

Ein Basisfall ist ein Teilproblem, das von keinem anderen Teilproblem abhängt. Um solche Teilprobleme zu finden, möchten Sie in der Regel einige Beispiele ausprobieren, sehen, wie sich Ihr Problem in kleinere Teilprobleme vereinfacht, und ermitteln, an welcher Stelle es nicht weiter vereinfacht werden kann.

Der Grund, warum ein Problem nicht weiter vereinfacht werden kann, besteht darin, dass einer der Parameter zu einem Wert wird, der angesichts der Einschränkungen des Problems nicht möglich ist .

In unserem Beispielproblem haben wir zwei sich ändernde Parameter, S und P. Lassen Sie uns überlegen, welche möglichen Werte von S und P möglicherweise nicht legal sind:

  1. P sollte innerhalb der Grenzen der gegebenen Landebahn liegen
  2. P kann nicht so sein, dass die Landebahn [P] falsch ist, da dies bedeuten würde, dass wir auf einer Spitze stehen
  3. S kann nicht negativ sein und ein S == 0 zeigt an, dass wir fertig sind

Manchmal kann es eine kleine Herausforderung sein, Aussagen, die wir über Parameter machen, in programmierbare Basisfälle umzuwandeln. Dies liegt daran, dass Sie nicht nur die Aussagen auflisten müssen, wenn Sie Ihren Code präzise gestalten und nicht nach unnötigen Bedingungen suchen möchten, sondern auch darüber nachdenken müssen, welche dieser Bedingungen überhaupt möglich sind.

In unserem Beispiel:

  1. P <0 || P> = Länge der Landebahn scheint das Richtige zu sein. Eine Alternative könnte darin bestehen, P == Ende der Landebahn als Basisfall zu betrachten. Es ist jedoch möglich, dass sich ein Problem in ein Teilproblem aufteilt, das über das Ende der Landebahn hinausgeht. Daher müssen wir wirklich auf Ungleichheit prüfen.
  2. Das scheint ziemlich offensichtlich. Wir können einfach überprüfen, ob die Landebahn [P] falsch ist .
  3. Ähnlich wie bei # 1 könnten wir einfach nach S <0 und S == 0 suchen. Hier können wir jedoch argumentieren, dass es unmöglich ist, dass S <0 ist, da S um höchstens 1 abnimmt, so dass es durchlaufen müsste S == 0 Fall vorher. Ther efore S == 0 ist ein ausreichender Basisfall für die S - Parameter.

Schritt 5: Entscheiden Sie, ob Sie es iterativ oder rekursiv implementieren möchten

Die Art und Weise, wie wir bisher über die Schritte gesprochen haben, könnte Sie zu der Annahme veranlassen, dass wir das Problem rekursiv implementieren sollten. Alles, worüber wir bisher gesprochen haben, ist jedoch völlig unabhängig davon, ob Sie sich entscheiden, das Problem rekursiv oder iterativ zu implementieren. In beiden Ansätzen müssten Sie die Wiederholungsrelation und die Basisfälle bestimmen.

Um zu entscheiden, ob Sie iterativ oder rekursiv vorgehen möchten, sollten Sie sorgfältig über die Kompromisse nachdenken .

Stapelüberlaufprobleme sind in der Regel ein Deal Breaker und ein Grund, warum Sie keine Rekursion in einem (Backend-) Produktionssystem wünschen. Für die Zwecke des Interviews sollten Sie jedoch in der Regel mit beiden Implementierungen einverstanden sein, solange Sie die Kompromisse erwähnen. Sie sollten sich wohl fühlen, wenn Sie beide implementieren.

In unserem speziellen Problem habe ich beide Versionen implementiert. Hier ist Python-Code dafür:

Eine rekursive Lösung: (Original-Codefragmente finden Sie hier)

Eine iterative Lösung: (Original-Codefragmente finden Sie hier)

Schritt 6: Memoisierung hinzufügen

Das Auswendiglernen ist eine Technik, die eng mit DP verbunden ist. Es wird zum Speichern der Ergebnisse teurer Funktionsaufrufe und zum Zurückgeben des zwischengespeicherten Ergebnisses verwendet, wenn dieselben Eingaben erneut auftreten.

Warum fügen wir unserer Rekursion Memoisierung hinzu? Wir stoßen auf dieselben Teilprobleme, die ohne Memoisierung wiederholt berechnet werden. Diese Wiederholungen führen sehr oft zu exponentiellen Zeitkomplexitäten.

In rekursiven Lösungen sollte sich das Hinzufügen von Memoisierung einfach anfühlen. Mal sehen warum. Denken Sie daran, dass das Auswendiglernen nur ein Cache der Funktionsergebnisse ist. Es gibt Zeiten, in denen Sie von dieser Definition abweichen möchten, um einige geringfügige Optimierungen zu vermeiden. Die Behandlung von Memoization als Funktionsergebnis-Cache ist jedoch die intuitivste Methode, um sie zu implementieren.

Dies bedeutet, dass Sie:

  1. Speichern Sie Ihr Funktionsergebnis vor jeder return- Anweisung in Ihrem Speicher
  2. Suchen Sie im Speicher nach dem Funktionsergebnis, bevor Sie mit einer anderen Berechnung beginnen

Hier ist der Code von oben mit zusätzlicher Notiz (hinzugefügte Zeilen sind hervorgehoben): (Original-Codefragmente finden Sie hier)

Um die Wirksamkeit der Memoisierung und verschiedene Ansätze zu veranschaulichen, führen wir einige kurze Tests durch. Ich werde alle drei Methoden, die wir bisher gesehen haben, einem Stresstest unterziehen. Hier ist der Aufbau:

  1. Ich habe eine Landebahn mit einer Länge von 1000 mit Spitzen an zufälligen Stellen erstellt (ich habe eine Wahrscheinlichkeit von 20% gewählt, dass sich eine Spitze an einer bestimmten Stelle befindet).
  2. initSpeed ​​= 30
  3. Ich habe alle Funktionen 10 Mal ausgeführt und die durchschnittliche Ausführungszeit gemessen

Hier sind die Ergebnisse (in Sekunden):

Sie können sehen, dass der reine rekursive Ansatz etwa 500-mal länger dauert als der iterative Ansatz und etwa 1300-mal länger als der rekursive Ansatz mit Memoisierung. Beachten Sie, dass diese Diskrepanz mit der Länge der Landebahn schnell zunehmen würde. Ich ermutige Sie, es selbst zu versuchen.

Schritt 7: Bestimmen Sie die zeitliche Komplexität

Es gibt einige einfache Regeln, die die Komplexität der Rechenzeit eines dynamischen Programmierproblems erheblich vereinfachen können. Hier sind zwei Schritte, die Sie ausführen müssen:

  1. Zählen Sie die Anzahl der Zustände - dies hängt von der Anzahl der sich ändernden Parameter in Ihrem Problem ab
  2. Denken Sie an die Arbeit, die in jedem Staat geleistet wird. Mit anderen Worten, wenn alles andere als ein Zustand berechnet wurde, wie viel Arbeit müssen Sie tun, um diesen letzten Zustand zu berechnen?

In unserem Beispielproblem ist die Anzahl der Zustände | P | * | S |, wo

  • P ist die Menge aller Positionen (| P | gibt die Anzahl der Elemente in P an)
  • S ist die Menge aller Geschwindigkeiten

Die pro Zustand geleistete Arbeit ist in diesem Problem O (1), da wir bei allen anderen Zuständen lediglich 3 Teilprobleme betrachten müssen, um den resultierenden Zustand zu bestimmen.

Wie bereits im Code erwähnt, ist | S | ist durch die Länge der Landebahn (| P |) begrenzt, so dass wir sagen können, dass die Anzahl der Zustände | P | ² ist und da die pro Zustand geleistete Arbeit O (1) ist, ist die Gesamtzeitkomplexität O (| P. | ²).

Es scheint jedoch, dass | S | kann weiter eingeschränkt werden, denn wenn es wirklich | P | wäre, ist es sehr klar, dass ein Anhalten nicht möglich wäre, da Sie beim ersten Zug die Länge der gesamten Landebahn überspringen müssten.

Mal sehen, wie wir | S | enger binden können. Nennen wir die Höchstgeschwindigkeit S. Nehmen wir an, wir starten von Position 0. Wie schnell könnten wir anhalten, wenn wir versuchen würden, so schnell wie möglich anzuhalten, und wenn wir mögliche Spitzen ignorieren?

In der ersten Iteration müssten wir mindestens zum Punkt (S-1) kommen, indem wir unsere Geschwindigkeit auf Null um -1 einstellen. Von dort würden wir mindestens (S-2) Schritte vorwärts gehen und so weiter.

Für eine Landebahn der Länge L muss Folgendes gelten:

=> (S-1) + (S-2) + (S-3) + ... + 1 <L

=> S * (S-1) / 2 <L

=> S² - S - 2L <0

Wenn Sie Wurzeln der obigen Funktion finden, sind diese:

r1 = 1/2 + sqrt (1/4 + 2L) und r2 = 1/2 - sqrt (1/4 + 2L)

Wir können unsere Ungleichung schreiben als:

(S - r1) * (S - r2) < ; 0

In Anbetracht dessen, dass S - r2> 0 für jedes S> 0 und L> 0 ist, benötigen wir Folgendes:

S - 1/2 - sqrt (1/4 + 2 l) < ; 0

=> S <1/2 + sqrt (1/4 + 2L)

Das ist die maximale Geschwindigkeit, die wir möglicherweise auf einer Landebahn der Länge L haben könnten. Wenn wir eine höhere Geschwindigkeit hätten, könnten wir nicht einmal theoretisch anhalten, unabhängig von der Position der Spikes.

Das bedeutet, dass die Gesamtzeitkomplexität nur von der Länge der Landebahn L in der folgenden Form abhängt:

O (L * sqrt (L)), das besser ist als O (L²)

O (L * sqrt (L)) ist die Obergrenze der Zeitkomplexität

Super, du hast es geschafft! :) :)

Die 7 Schritte, die wir durchlaufen haben, sollten Ihnen einen Rahmen für die systematische Lösung eines dynamischen Programmierproblems bieten. Ich empfehle dringend, diesen Ansatz bei einigen weiteren Problemen zu üben, um Ihren Ansatz zu perfektionieren.

Hier sind einige der nächsten Schritte, die Sie ausführen können

  1. Erweitern Sie das Beispielproblem, indem Sie versuchen, einen Pfad zu einem Haltepunkt zu finden. Wir haben ein Problem gelöst, das Ihnen sagt, ob Sie anhalten können, aber was ist, wenn Sie auch wissen möchten, welche Schritte Sie unternehmen müssen, um schließlich auf der Landebahn anzuhalten? Wie würden Sie die vorhandene Implementierung ändern, um dies zu tun?
  2. Wenn Sie Ihr Verständnis von Memoization festigen möchten und verstehen möchten, dass es sich nur um einen Funktionsergebnis-Cache handelt, sollten Sie über Dekoratoren in Python oder ähnliche Konzepte in anderen Sprachen lesen. Überlegen Sie, wie Sie damit Memoisierung generell für jede Funktion implementieren können, die Sie auswendig lernen möchten.
  3. Arbeiten Sie an weiteren DP-Problemen, indem Sie die Schritte befolgen, die wir durchlaufen haben. Sie können immer eine Reihe von ihnen online finden (z. B. LeetCode oder GeeksForGeeks). Denken Sie beim Üben an eines: Lernen Sie Ideen, lernen Sie keine Probleme. Die Anzahl der Ideen ist erheblich geringer und es ist einfacher zu erobern, was Ihnen auch viel besser dienen wird.

Wenn Sie das Gefühl haben, diese Ideen erobert zu haben, lesen Sie Refdash, wo Sie von einem leitenden Ingenieur interviewt werden, und erhalten Sie ein detailliertes Feedback zu Ihrer Codierung, Ihren Algorithmen und Ihrem Systemdesign.

Ursprünglich im Refdash-Blog veröffentlicht. Refdash ist eine Interviewplattform, mit der Ingenieure anonym mit erfahrenen Ingenieuren von Top-Unternehmen wie Google, Facebook oder Palantir interviewen und ein detailliertes Feedback erhalten können. Refdash hilft Ingenieuren auch dabei, aufgrund ihrer Fähigkeiten und Interessen erstaunliche Beschäftigungsmöglichkeiten zu entdecken.