Risolvere i problemi difficili di Leetcode con ChatGPT?

Sebbene ChatGPT sia impressionante, sembra che non dia facilmente risposte corrette a problemi complessi. Ho provato a risolvere i primi 10 problemi difficili di Leetcode (etichettati sotto le domande principali dell'intervista) utilizzando ChatGPT per verificare lo stesso.

Puoi trovare i problemi qui: Problem Set . Alcuni di questi includono problemi famosi come intrappolare l'acqua piovana e finestre scorrevoli.

Non sprecherò il tuo tempo in questo articolo che mostra tutti i prompt, il codice e le risposte fornite da ChatGPT. Invece, condenserò le mie osservazioni e gli apprendimenti dall'esperienza complessiva. L'approccio di base è dare l'intera o parte della domanda Leetcode come prompt a ChatGPT.

Ecco una sintesi dei risultati.

1. Mediana di due array ordinati : primo tentativo, soluzione diretta, nessuna modifica del codice/ulteriore analisi richiesta. Questa era una domanda facile, in entrambi i casi. Finito in un minuto.
2. Corrispondenza di espressioni regolari : prima prova, ha fornito un codice in esecuzione. Tuttavia, ha superato solo 287/353 casi di test. Il codice ha avuto esito negativo per uno scenario edge in cui il modello è più lungo della stringa. Anche questo è piuttosto impressionante. Quindi ho riprovato con ChatGPT, inclusi tutti gli esempi, e ho cercato una soluzione ottimizzata. Ha escogitato un approccio utilizzando la programmazione dinamica e ha superato tutti i casi di test senza alcuna modifica del codice. Finito in ~ 15 minuti, mentre stavo provando diverse modifiche per arrivare a una soluzione DP. Nota che non l'ho menzionato per usare DP ovunque.
3. Unisci k elenchi ordinati : i primi tre tentativi non forniscono la soluzione corretta. C'erano anche errori di sintassi. Inizialmente, ha cercato di fornire una soluzione utilizzando gli heap. Quindi aggiorno e modifico il prompt e lo mantengo breve e diretto. In questo modo, ottengo una soluzione in cui prima crea una funzione di supporto per unire due elenchi e la usa per unire tutti gli elenchi. Non è stato necessario modificare il codice. Tutti i casi di test sono stati superati. Finito in ~ 10 minuti.
4. Primo positivo mancante : quinto tentativo e funziona! Non è stato necessario modificare il codice. Tutti i casi di test sono stati superati. Finito in ~ 6 minuti. Le prime soluzioni fornite erano dappertutto, con errori di sintassi o non superando i casi di test. Quindi aggiorno tutto e provo ad aggiungere l'intera domanda nel prompt con i vincoli, e boom, ottengo una soluzione elegante.
5. Intrappolare l'acqua piovana - Questa è una delle domande famose e più complicate. E indovina cosa! Primo tentativo, nessuna modifica del codice e TUTTI I CASI DI TEST PASSATI. Finito in meno di 1 minuto. Me lo aspettavo perché è un problema famoso e può probabilmente avere molte informazioni nei dati di allenamento. Ecco un riassunto dell'approccio a due punti che utilizza:
   “Per risolvere questo problema, possiamo utilizzare un approccio a due punti. Manterremo due puntatori all'inizio e alla fine dell'array e li spostiamo verso l'interno finché non si incontrano. Ad ogni passaggio, calcoleremo la quantità di acqua che può essere intrappolata dalle due barre sui puntatori.
   Per calcolare la quantità di acqua che può essere intrappolata, prendiamo il minimo delle due barre in corrispondenza dei puntatori e sottraiamo l'altezza della barra in corrispondenza del puntatore inferiore. Questo ci darà l'altezza dell'acqua che può essere intrappolata. Lo moltiplicheremo quindi per la distanza tra i due indicatori per ottenere la quantità totale di acqua che può essere intrappolata».
6. Corrispondenza con caratteri jolly : secondo tentativo, offre un'elegante soluzione ricorsiva che supera i casi di test 1616/1811. Quindi genera un errore di superamento del limite di tempo. Ho chiesto a ChatGPT di trovare una soluzione più ottimizzata. Genera una soluzione utilizzando la programmazione dinamica. Tutti i casi di test vengono superati senza che sia richiesta alcuna modifica del codice. Finito in circa ~ 3 minuti. Sembra che ChatGPT sia abbastanza buono con la programmazione dinamica.
7. Sottostringa minima della finestra — Questa è pazzesca. Finito in ~ 20 secondi. Non ho nemmeno letto l'intero problema o la soluzione. 1° tentativo, tutti i casi di test sono stati superati. Le cose si stanno facendo interessanti. Ho pensato che avrei dovuto mettere a punto il mio approccio a problemi più impegnativi. Sembra che non sia così.
8. Rettangolo più grande nell'istogramma : la striscia continua. Ha generato una soluzione utilizzando uno stack con più di 40 righe di codice. 1° tentativo, ha superato tutti i casi di test. Finì in meno di un minuto.
9. Somma del percorso massimo dell'albero binario : prima fornisce una soluzione ricorsiva. Gli chiedo di provare a ottimizzare utilizzando direttamente DP. Lo fa. Tuttavia, la soluzione supera solo 62/94 casi di test. Questa volta, aggiorno la conversazione, pongo nuovamente la domanda e le chiedo esplicitamente di risolverla in DP. Lo fa e il codice supera tutti i casi di test. Finito in 5 minuti.
10. Word ladder — Secondo tentativo, genera una soluzione usando deque. Ho dovuto solo cambiare alcuni nomi di variabili per far funzionare il codice. Tutti i casi di test sono stati superati. Finito in ~ 3 minuti.

• Per alcune domande, è utile fornire esempi di input, output e vincoli nel prompt. Per alcune altre domande, funziona solo la domanda diretta. Se uno non funziona, aggiorna e prova l'altro.
• Puoi generare le risposte richieste più velocemente se comprendi la tecnica che puoi utilizzare per una determinata dichiarazione del problema. Ad esempio, se sai che DP o BFS possono risolvere un problema, puoi chiedere a ChatGPT di utilizzare immediatamente tali tecniche.
• È possibile risolvere errori o modificare il codice per i casi limite richiedendolo esplicitamente nella chat.
• Se capisci il codice, probabilmente puoi dire a colpo d'occhio se funzionerebbe. Se ritieni che stia andando nella direzione sbagliata, puoi aggiornare rapidamente la conversazione e spingerla correttamente. Probabilmente arriverà per dare una risposta corretta.
• Una cosa che trovo abbastanza intuitiva è come cerca di dare spiegazioni e scrive commenti sul codice. Mi aiuta immensamente a capire la logica e verificare se è plausibile.

Forse testerò le acque con la codifica competitiva e Google Code Jam.