Leetcode Hard Probleme mit ChatGPT lösen?

Während ChatGPT beeindruckend ist, sieht es so aus, als ob es nicht einfach die richtigen Antworten auf komplexe Probleme gibt. Ich habe versucht, die ersten 10 schwierigen Probleme von Leetcode (markiert unter den wichtigsten Interviewfragen) mit ChatGPT zu lösen, um dasselbe zu überprüfen.

Sie finden die Probleme hier: Problem Set . Einige davon sind berühmte Probleme wie das Einfangen von Regenwasser und das Schieben von Fenstern.

Ich werde Ihre Zeit nicht mit diesem Artikel verschwenden, der alle Eingabeaufforderungen, Codes und Antworten zeigt, die ChatGPT gibt. Stattdessen werde ich meine Beobachtungen und Erkenntnisse aus der Gesamterfahrung verdichten. Der grundlegende Ansatz besteht darin, ChatGPT die gesamte oder einen Teil der Leetcode-Frage als Eingabeaufforderung zu geben.

Hier ist eine Zusammenfassung der Ergebnisse.

1. Median von zwei sortierten Arrays – Erster Versuch, direkte Lösung, keine Codeänderung/weitere Analyse erforderlich. Das war so oder so eine einfache Frage. Fertig in einer Minute.
2. Regulärer Ausdrucksabgleich – Erster Versuch, gab einen laufenden Code. Es hat jedoch nur 287/353 Testfälle bestanden. Der Code ist für ein Edge-Szenario fehlgeschlagen, bei dem das Muster länger als die Zeichenfolge ist. Das ist auch ziemlich beeindruckend. Dann habe ich es erneut mit ChatGPT versucht, einschließlich aller Beispiele, und nach einer optimierten Lösung gesucht. Es entwickelte einen Ansatz mit dynamischer Programmierung und bestand alle Testfälle ohne Codeänderung. Fertig in ca. 15 Minuten, da ich verschiedene Modifikationen ausprobierte, um zu einer DP-Lösung zu gelangen. Beachten Sie, dass ich es nirgendwo erwähnt habe, DP zu verwenden.
3. k sortierte Listen zusammenführen — Die ersten drei Versuche ergeben nicht die richtige Lösung. Es gab auch Syntaxfehler. Anfangs wurde versucht, eine Lösung mit Haufen zu geben. Dann aktualisiere und ändere ich die Eingabeaufforderung und halte sie kurz und unkompliziert. So erhalte ich eine Lösung, bei der zuerst eine Hilfsfunktion zum Zusammenführen von zwei Listen erstellt und zum Zusammenführen aller Listen verwendet wird. Es war keine Codeänderung erforderlich. Alle Testfälle bestanden. Fertig in ~10 Minuten.
4. Erstes fehlendes Positiv – 5. Wiederholung, und es funktioniert! Es war keine Codeänderung erforderlich. Alle Testfälle bestanden. Fertig in ~6 Minuten. Die ersten paar Lösungen, die es gab, waren alle vorbei, entweder mit Syntaxfehlern oder nicht bestandenen Testfällen. Dann aktualisiere ich alles und versuche, die gesamte Frage mit den Einschränkungen in die Eingabeaufforderung einzufügen, und boom, ich bekomme eine elegante Lösung.
5. Regenwasser auffangen – Das ist eine der bekanntesten und kniffligeren Fragen. Und rate was! Erster Versuch, keine Codeänderung und ALLE TESTFÄLLE BESTANDEN. Fertig in weniger als 1 Minute. Ich habe es erwartet, da es sich um ein bekanntes Problem handelt und möglicherweise viele Informationen in den Trainingsdaten enthalten sind. Hier ist eine Zusammenfassung des verwendeten Zwei-Zeiger-Ansatzes:
   „Um dieses Problem zu lösen, können wir einen Zwei-Zeiger-Ansatz verwenden. Wir behalten zwei Zeiger am Anfang und am Ende des Arrays bei und verschieben sie nach innen, bis sie sich treffen. Bei jedem Schritt berechnen wir die Wassermenge, die von den beiden Balken an den Zeigern eingefangen werden kann.
   Um die Wassermenge zu berechnen, die eingeschlossen werden kann, nehmen wir das Minimum der beiden Balken an den Zeigern und subtrahieren die Höhe des Balkens am unteren Zeiger. Dies gibt uns die Höhe des Wassers, das eingeschlossen werden kann. Wir werden dies dann mit dem Abstand zwischen den beiden Zeigern multiplizieren, um die Gesamtmenge an Wasser zu erhalten, die eingeschlossen werden kann.“
6. Wildcard-Matching – Beim zweiten Versuch ergibt sich eine elegante rekursive Lösung, die die Testfälle 1616/1811 besteht. Dann wird ein Zeitlimitüberschreitungsfehler ausgegeben. Ich habe ChatGPT gebeten, eine optimiertere Lösung zu finden. Es generiert eine Lösung mit dynamischer Programmierung. Alle Testfälle bestehen, ohne dass eine Codeänderung erforderlich ist. Fertig in ca. 3 Minuten. Sieht so aus, als ob ChatGPT mit dynamischer Programmierung ziemlich gut ist.
7. Minimaler Fensterteilstring – Das ist verrückt. Fertig in ~20 Sekunden. Ich habe nicht einmal das ganze Problem oder die Lösung gelesen. 1. Versuch, alle Testfälle bestanden. Die Dinge werden interessant. Ich dachte, ich müsste meine Herangehensweise an anspruchsvollere Probleme verfeinern. Anscheinend ist das nicht der Fall.
8. Größtes Rechteck im Histogramm – Der Streifen geht weiter. Es generierte eine Lösung mit einem Stack mit mehr als 40 Codezeilen. 1. Versuch, es hat alle Testfälle bestanden. Es war in weniger als einer Minute fertig.
9. Maximale Pfadsumme des Binärbaums – Es gibt zunächst eine rekursive Lösung. Ich bitte es, zu versuchen, direkt mit DP zu optimieren. Das tut es. Die Lösung besteht jedoch nur 62/94 Testfälle. Dieses Mal aktualisiere ich die Konversation, stelle die Frage erneut und fordere sie ausdrücklich auf, sie in DP zu lösen. Das tut es, und der Code besteht alle Testfälle. Fertig in 5 Minuten.
10. Wortleiter – Zweiter Versuch, und es generiert eine Lösung mit deque. Ich musste nur einige Variablennamen ändern, um den Code zum Laufen zu bringen. Alle Testfälle bestanden. Fertig in ~3 Minuten.

• Bei einigen Fragen ist es effektiv, in der Eingabeaufforderung Beispiele für Eingaben, Ausgaben und Einschränkungen anzugeben. Bei einigen anderen Fragen funktioniert nur die direkte Frage. Wenn eines nicht funktioniert, aktualisieren Sie es und versuchen Sie es mit dem anderen.
• Sie können die erforderlichen Antworten schneller generieren, wenn Sie die Technik verstehen, die Sie für eine bestimmte Problemstellung verwenden können. Wenn Sie beispielsweise wissen, dass DP oder BFS ein Problem lösen können, können Sie ChatGPT bitten, diese Techniken sofort zu verwenden.
• Es ist möglich, Fehler zu beheben oder Code für Grenzfälle zu ändern, indem Sie im Chat explizit danach fragen.
• Wenn Sie Code verstehen, können Sie wahrscheinlich auf einen Blick erkennen, ob er funktionieren würde. Wenn Sie das Gefühl haben, dass es in die falsche Richtung geht, können Sie das Gespräch schnell auffrischen und richtig anstoßen. Es wird wahrscheinlich kommen, um eine richtige Antwort zu geben.
• Eine Sache, die ich ziemlich intuitiv finde, ist, wie es versucht, Erklärungen zu geben und Codekommentare zu schreiben. Es hilft mir ungemein, die Logik zu verstehen und zu überprüfen, ob sie plausibel ist.

Vielleicht werde ich das Wasser mit kompetitiver Codierung und Google Code Jam testen.