¿Resolviendo problemas difíciles de Leetcode con ChatGPT?

Si bien ChatGPT es impresionante, parece que no brinda respuestas correctas fácilmente a problemas complejos. Intenté resolver los primeros 10 problemas difíciles de Leetcode (etiquetados en las principales preguntas de la entrevista) usando ChatGPT para verificar lo mismo.

Puede encontrar los problemas aquí: Conjunto de problemas . Algunos de estos incluyen problemas famosos como atrapar agua de lluvia y ventanas corredizas.

No perderé su tiempo en este artículo que muestra todas las indicaciones, el código y las respuestas que da ChatGPT. En cambio, condensaré mis observaciones y aprendizajes de la experiencia general. El enfoque básico es dar la totalidad o parte de la pregunta de Leetcode como aviso a ChatGPT.

Aquí hay un resumen de los resultados.

1. Mediana de dos matrices ordenadas : primer intento, solución directa, no se requiere cambio de código/análisis adicional. Esta era una pregunta fácil, de cualquier manera. Terminado en un minuto.
2. Coincidencia de expresiones regulares : primer intento, proporcionó un código en ejecución. Sin embargo, pasó solo 287/353 casos de prueba. El código falló en un escenario de borde donde el patrón es más largo que la cadena. Eso también es bastante impresionante. Luego volví a intentarlo con ChatGPT, incluidos todos los ejemplos, y busqué una solución optimizada. Se le ocurrió un enfoque utilizando programación dinámica y pasó todos los casos de prueba sin ningún cambio de código. Terminé en ~15 minutos, mientras intentaba diferentes modificaciones para llegar a una solución de DP. Tenga en cuenta que no lo mencioné para usar DP en ninguna parte.
3. Fusionar k listas ordenadas : los primeros tres intentos, no da la solución correcta. También hubo errores de sintaxis. Inicialmente, trató de dar una solución usando montones. Luego actualizo y modifico el indicador y lo mantengo breve y directo. Así, obtengo una solución en la que primero crea una función auxiliar para fusionar dos listas y la usa para fusionar todas las listas. No se requirió ningún cambio de código. Todos los casos de prueba pasaron. Terminado en ~ 10 minutos.
4. Primer positivo faltante : quinto reintento, ¡y funciona! No se requirió ningún cambio de código. Todos los casos de prueba pasaron. Terminado en ~6 minutos. Las primeras soluciones que dio estaban por todas partes, con errores de sintaxis o no pasando los casos de prueba. Luego actualizo todo y trato de agregar la pregunta completa en el aviso con las restricciones, y boom, obtengo una solución elegante.
5. Atrapar el agua de lluvia : esta es una de las preguntas más famosas y complicadas. ¡Y adivina qué! Primer intento, sin cambio de código y TODOS LOS CASOS DE PRUEBA PASADOS. Terminado en menos de 1 minuto. Lo esperaba ya que es un problema famoso y podría decirse que puede tener mucha información en los datos de entrenamiento. Aquí hay una idea general del enfoque de dos puntos que utiliza:
   “Para resolver este problema, podemos usar un enfoque de dos puntos. Mantendremos dos punteros al principio y al final de la matriz y los moveremos hacia adentro hasta que se encuentren. En cada paso, calcularemos la cantidad de agua que pueden atrapar las dos barras en los punteros.
   Para calcular la cantidad de agua que puede quedar atrapada, tomaremos el mínimo de las dos barras en los punteros y restaremos la altura de la barra en el puntero inferior. Esto nos dará la altura del agua que puede quedar atrapada. Luego multiplicaremos esto por la distancia entre los dos punteros para obtener la cantidad total de agua que puede quedar atrapada”.
6. Coincidencia de comodines : segundo intento, ofrece una elegante solución recursiva que supera los casos de prueba 1616/1811. Luego arroja un error de límite de tiempo excedido. Le pedí a ChatGPT que ideara una solución más optimizada. Genera una solución mediante programación dinámica. Todos los casos de prueba pasan sin necesidad de cambiar el código. Terminado en aproximadamente ~ 3 minutos. Parece que ChatGPT es bastante bueno con la programación dinámica.
7. Subcadena de ventana mínima : esta es una locura. Terminado en ~20 segundos. Ni siquiera leí todo el problema o la solución. 1er intento, todos los casos de prueba pasaron. Las cosas se están poniendo interesantes. Pensé que tendría que afinar mi enfoque para problemas más desafiantes. Parece que ese no es el caso.
8. El rectángulo más grande del histograma : la racha continúa. Generó una solución usando una pila con más de 40 líneas de código. 1er intento, pasó todos los casos de prueba. Terminó en menos de un minuto.
9. Suma máxima de la ruta del árbol binario : primero proporciona una solución recursiva. Le pido que intente optimizar usando DP directamente. lo hace Sin embargo, la solución pasa solo 62/94 casos de prueba. Esta vez, actualizo la conversación, vuelvo a plantear la pregunta y le pido explícitamente que la resuelva en DP. Lo hace, y el código pasa todos los casos de prueba. Terminado en 5 minutos.
10. Escalera de palabras : segundo intento, y genera una solución usando deque. Solo tuve que cambiar algunos nombres de variables para ejecutar el código. Todos los casos de prueba pasaron. Terminado en ~3 minutos.

• Para algunas preguntas, es efectivo dar ejemplos de entradas, salidas y restricciones en el aviso. Para algunas otras preguntas, solo funciona la pregunta directa. Si uno no funciona, actualice y pruebe el otro.
• Puede generar las respuestas requeridas más rápido si comprende la técnica que puede usar para una declaración de problema determinada. Por ejemplo, si sabe que DP o BFS pueden resolver un problema, puede pedirle a ChatGPT que use esas técnicas de inmediato.
• Es posible resolver errores o modificar código para casos extremos solicitando explícitamente lo mismo en el chat.
• Si entiende el código, probablemente pueda saber de un vistazo si funcionaría. Si siente que va en la dirección equivocada, puede actualizar rápidamente la conversación y empujarla correctamente. Es probable que llegue a dar una respuesta correcta.
• Una cosa que encuentro bastante intuitiva es cómo trata de dar explicaciones y escribe comentarios de código. Me ayuda inmensamente a entender la lógica y verificar si es plausible.

Tal vez probaré las aguas con codificación competitiva y Google Code Jam.