Resolvendo problemas difíceis do Leetcode com o ChatGPT?

Embora o ChatGPT seja impressionante, parece que não fornece respostas corretas facilmente para problemas complexos. Tentei resolver os primeiros 10 problemas difíceis do Leetcode (marcados nas principais perguntas da entrevista) usando o ChatGPT para verificar o mesmo.

Você pode encontrar os problemas aqui: Conjunto de problemas . Alguns deles incluem problemas famosos como retenção de água da chuva e janela deslizante.

Não vou perder seu tempo neste artigo mostrando todos os prompts, códigos e respostas que o ChatGPT fornece. Em vez disso, vou condensar minhas observações e aprendizados da experiência geral. A abordagem básica é fornecer toda ou parte da pergunta do Leetcode como um prompt para o ChatGPT.

Aqui está um resumo dos resultados.

1. Mediana de duas matrizes classificadas — Primeira tentativa, solução direta, nenhuma alteração de código/análise adicional necessária. Esta foi uma pergunta fácil, de qualquer maneira. Terminado em um minuto.
2. Correspondência de expressão regular — Primeira tentativa, deu um código em execução. No entanto, passou apenas 287/353 casos de teste. O código falhou para um cenário de borda em que o padrão é maior que a string. Isso é bastante impressionante também. Então tentei novamente com o ChatGPT, incluindo todos os exemplos, e procurei uma solução otimizada. Ele criou uma abordagem usando programação dinâmica e passou em todos os casos de teste sem nenhuma alteração de código. Concluído em cerca de 15 minutos, enquanto tentava diferentes modificações para chegar a uma solução de DP. Observe que eu não mencionei usar DP em qualquer lugar.
3. Mesclar k listas classificadas — As três primeiras tentativas não fornecem a solução correta. Houve erros de sintaxe também. Inicialmente, tentou dar uma solução usando heaps. Em seguida, atualizo e modifico o prompt e o mantenho curto e direto. Assim, obtenho uma solução em que primeiro cria uma função auxiliar para mesclar duas listas e a usa para mesclar todas as listas. Nenhuma alteração de código foi necessária. Todos os casos de teste passaram. Terminou em ~ 10 minutos.
4. Primeiro positivo perdido - 5ª tentativa e funciona! Nenhuma alteração de código foi necessária. Todos os casos de teste passaram. Terminou em ~ 6 minutos. As primeiras soluções que ele deu estavam todas acabadas, com erros de sintaxe ou não passando nos casos de teste. Em seguida, atualizo tudo e tento adicionar a pergunta inteira no prompt com as restrições e, bum, obtenho uma solução elegante.
5. Capturando a água da chuva — Esta é uma das perguntas mais famosas e complicadas. E adivinha! Primeira tentativa, nenhuma mudança de código e TODOS OS CASOS DE TESTE PASSADOS. Terminou em menos de 1 minuto. Eu esperava, pois é um problema famoso e pode ter muitas informações nos dados de treinamento. Aqui está um resumo da abordagem de dois ponteiros que ele usa:
   “Para resolver esse problema, podemos usar uma abordagem de dois ponteiros. Vamos manter dois ponteiros no início e no final da matriz e movê-los para dentro até que se encontrem. A cada passo, calcularemos a quantidade de água que pode ser retida pelas duas barras nos ponteiros.
   Para calcular a quantidade de água que pode ser retida, vamos pegar o mínimo das duas barras nos ponteiros e subtrair a altura da barra no ponteiro inferior. Isso nos dará a altura da água que pode ser retida. Em seguida, multiplicaremos isso pela distância entre os dois ponteiros para obter a quantidade total de água que pode ser retida.”
6. Correspondência curinga — Na segunda tentativa, oferece uma solução recursiva elegante que passa nos casos de teste 1616/1811. Em seguida, ele lança um erro de limite de tempo excedido. Pedi ao ChatGPT que apresentasse uma solução mais otimizada. Ele gera uma solução usando programação dinâmica. Todos os casos de teste passam sem nenhuma alteração de código necessária. Terminou em cerca de ~ 3 minutos. Parece que o ChatGPT é muito bom com programação dinâmica.
7. Substring mínima da janela — Essa é uma loucura. Terminou em ~ 20 segundos. Eu nem li todo o problema ou a solução. 1ª tentativa, todos os casos de teste passaram. As coisas estão ficando interessantes. Achei que teria que ajustar minha abordagem para problemas mais desafiadores. Parece que não é o caso.
8. Maior retângulo no histograma — A sequência continua. Gerou uma solução usando uma pilha com mais de 40 linhas de código. 1ª tentativa, passou em todos os casos de teste. Terminou em menos de um minuto.
9. Soma máxima do caminho da árvore binária — primeiro fornece alguma solução recursiva. Peço que tente otimizar usando DP diretamente. Ele faz isso. No entanto, a solução passa em apenas 62/94 casos de teste. Desta vez, atualizo a conversa, faço a pergunta novamente e peço explicitamente para resolver em DP. Sim, e o código passa em todos os casos de teste. Terminado em 5 minutos.
10. Word ladder — Segunda tentativa, e gera uma solução usando deque. Eu apenas tive que mudar alguns nomes de variáveis ​​para obter o código em execução. Todos os casos de teste passaram. Terminou em ~ 3 minutos.

• Para algumas perguntas, é eficaz fornecer exemplos de entradas, saídas e restrições no prompt. Para algumas outras perguntas, apenas a pergunta direta funciona. Se um não funcionar, atualize e tente o outro.
• Você pode gerar as respostas necessárias mais rapidamente se entender a técnica que pode usar para uma determinada declaração de problema. Por exemplo, se você sabe que DP ou BFS podem resolver um problema, pode pedir ao ChatGPT para usar essas técnicas imediatamente.
• É possível resolver erros ou modificar o código para casos extremos solicitando explicitamente o mesmo no chat.
• Se você entender o código, provavelmente poderá dizer rapidamente se funcionaria. Se você sentir que está indo na direção errada, pode atualizar rapidamente a conversa e empurrá-la corretamente. Provavelmente virá para dar uma resposta correta.
• Uma coisa que acho bastante intuitiva é como ele tenta dar explicações e escrever comentários de código. Isso me ajuda imensamente a entender a lógica e verificar se ela é plausível.

Talvez eu teste as águas com codificação competitiva e Google Code Jam.