Résoudre les problèmes difficiles de Leetcode avec ChatGPT ?

Bien que ChatGPT soit impressionnant, il semble qu'il ne donne pas facilement les bonnes réponses à des problèmes complexes. J'ai essayé de résoudre les 10 premiers problèmes difficiles de Leetcode (marqués sous les principales questions d'entretien) en utilisant ChatGPT pour vérifier la même chose.

Vous pouvez trouver les problèmes ici : Ensemble de problèmes . Certains d'entre eux incluent des problèmes célèbres comme le piégeage de l'eau de pluie et la fenêtre coulissante.

Je ne vais pas perdre votre temps dans cet article montrant toutes les invites, le code et les réponses que ChatGPT donne. Au lieu de cela, je vais condenser mes observations et mes apprentissages à partir de l'expérience globale. L'approche de base consiste à donner tout ou partie de la question Leetcode en tant qu'invite à ChatGPT.

Voici un résumé des résultats.

1. Médiane de deux tableaux triés — Premier essai, solution directe, aucune modification de code/analyse supplémentaire requise. C'était une question facile, de toute façon. Fini en une minute.
2. Correspondance d' expression régulière - Premier essai, a donné un code en cours d'exécution. Cependant, il n'a réussi que 287/353 cas de test. Le code a échoué pour un scénario Edge où le modèle est plus long que la chaîne. C'est assez impressionnant aussi. Ensuite, j'ai réessayé avec ChatGPT, y compris tous les exemples, et j'ai cherché une solution optimisée. Il a proposé une approche utilisant la programmation dynamique, et il a réussi tous les cas de test sans aucun changement de code. Terminé en ~ 15 minutes, alors que j'essayais différentes modifications pour arriver à une solution DP. Notez que je ne l'ai pas mentionné pour utiliser DP n'importe où.
3. Fusionner k listes triées — Trois premiers essais, cela ne donne pas la bonne solution. Il y avait aussi des erreurs de syntaxe. Initialement, il a essayé de donner une solution en utilisant des tas. Ensuite, j'actualise et modifie l'invite et je la garde courte et simple. Comme ça, j'obtiens une solution où il crée d'abord une fonction d'assistance pour fusionner deux listes et l'utilise pour fusionner toutes les listes. Aucun changement de code n'a été nécessaire. Tous les cas de test ont réussi. Terminé en ~10 minutes.
4. Premier positif manquant - 5ème tentative, et ça marche ! Aucun changement de code n'a été nécessaire. Tous les cas de test ont réussi. Terminé en ~6 minutes. Les premières solutions qu'il a données étaient partout, avec des erreurs de syntaxe ou ne réussissant pas les cas de test. Ensuite, je rafraîchis tout et j'essaie d'ajouter toute la question dans l'invite avec les contraintes, et boum, j'obtiens une solution élégante.
5. Piéger l'eau de pluie - C'est l'une des questions les plus célèbres et les plus délicates. Et devine quoi! Premier essai, aucun changement de code et TOUS LES CAS DE TEST SONT RÉUSSIS. Terminé en moins d'une minute. Je m'y attendais car c'est un problème célèbre et peut sans doute avoir beaucoup d'informations dans les données d'entraînement. Voici un aperçu de l'approche à deux points qu'il utilise :
   « Pour résoudre ce problème, nous pouvons utiliser une approche à deux points. Nous garderons deux pointeurs au début et à la fin du tableau et les déplacerons vers l'intérieur jusqu'à ce qu'ils se rencontrent. A chaque étape, nous calculerons la quantité d'eau qui peut être piégée par les deux barres au niveau des pointeurs.
   Pour calculer la quantité d'eau qui peut être piégée, nous allons prendre le minimum des deux barres aux pointeurs et soustraire la hauteur de la barre au pointeur inférieur. Cela nous donnera la hauteur de l'eau qui peut être piégée. Nous multiplierons ensuite cela par la distance entre les deux pointeurs pour obtenir la quantité totale d'eau qui peut être piégée.
6. Correspondance générique - Deuxième essai, cela donne une solution récursive élégante qui passe 1616/1811 cas de test. Ensuite, il lance une erreur de limite de temps dépassée. J'ai demandé à ChatGPT de proposer une solution plus optimisée. Il génère une solution en utilisant la programmation dynamique. Tous les cas de test réussissent sans qu'aucune modification de code ne soit requise. Terminé en environ ~ 3 minutes. On dirait que ChatGPT est assez bon avec une programmation dynamique.
7. Sous-chaîne de fenêtre minimale - Celle-ci est folle. Terminé en ~ 20 secondes. Je n'ai même pas lu tout le problème ni la solution. 1er essai, tous les cas de test ont réussi. Les choses deviennent intéressantes. Je pensais que je devrais affiner mon approche à des problèmes plus difficiles. On dirait que ce n'est pas le cas.
8. Rectangle le plus grand de l'histogramme — La séquence continue. Il a généré une solution en utilisant une pile avec plus de 40 lignes de code. 1er essai, il a réussi tous les cas de test. Il s'est terminé en moins d'une minute.
9. Somme maximale du chemin de l'arbre binaire - Il donne d'abord une solution récursive. Je lui demande d'essayer d'optimiser en utilisant directement DP. Il le fait. Cependant, la solution ne passe que 62/94 cas de test. Cette fois, je rafraîchis la conversation, pose à nouveau la question et lui demande explicitement de résoudre dans DP. C'est le cas, et le code passe tous les cas de test. Fini en 5 minutes.
10. Échelle de mots - Deuxième essai, et il génère une solution à l'aide de deque. J'ai juste eu à changer certains noms de variables pour que le code s'exécute. Tous les cas de test ont réussi. Terminé en ~3 minutes.

• Pour certaines questions, il est efficace de donner des exemples d'entrées, de sorties et de contraintes dans l'invite. Pour certaines autres questions, seule la question directe fonctionne. Si l'un ne fonctionne pas, actualisez et essayez l'autre.
• Vous pouvez générer les réponses requises plus rapidement si vous comprenez la technique que vous pouvez utiliser pour un énoncé de problème donné. Par exemple, si vous savez que DP ou BFS peuvent résoudre un problème, vous pouvez demander à ChatGPT d'utiliser ces techniques immédiatement.
• Il est possible de résoudre les erreurs ou de modifier le code pour les cas extrêmes en demandant explicitement la même chose dans le chat.
• Si vous comprenez le code, vous pouvez probablement dire en un coup d'œil si cela fonctionnerait. Si vous sentez que cela va dans la mauvaise direction, vous pouvez rapidement rafraîchir la conversation et la pousser correctement. Il reviendra probablement pour donner une réponse correcte.
• Une chose que je trouve assez intuitive est la façon dont il essaie de donner des explications et écrit des commentaires de code. Cela m'aide énormément à comprendre la logique et à vérifier si elle est plausible.

Peut-être que je testerai les eaux avec un codage compétitif et Google Code Jam.