Muitos problemas difíceis do LeetCode são problemas fáceis de programação com restrições

(buttondown.com)

6 pontos por GN⁺ 2025-09-13 | 2 comentários | Compartilhar no WhatsApp

Até os problemas difíceis do LeetCode podem ser resolvidos com muito mais facilidade usando solvers de restrições
Em vez de programação dinâmica complexa ou algoritmos próprios, é possível usar solvers de restrições como o MiniZinc para resolver problemas de otimização matemática de forma simples
Linguagens de programação tradicionais têm dificuldade para expressar esse tipo de problema de otimização matemática, o que destaca a força da abordagem baseada em restrições
Mesmo quando surgem casos de exceção ou restrições adicionais, a mudança no modelo dentro de um solver de restrições é mínima
A complexidade em tempo de execução pode ser pior do que a de um algoritmo otimizado escrito à mão, mas há muitas vantagens em flexibilidade e produtividade de desenvolvimento

Problemas do LeetCode resolvidos com um solver de restrições

Escolhendo a ferramenta certa

O autor recebeu o problema do "troco com moedas" em sua primeira entrevista após se formar na universidade
- Dadas denominações de moedas, o objetivo era encontrar a quantidade mínima de moedas necessária para devolver um valor específico
- Ele usou um algoritmo guloso simples, mas isso não garantia a solução ótima em todos os casos
- A resposta correta era programação dinâmica, mas ele não conseguiu implementá-la e foi reprovado na entrevista
Mas, em vez de implementar o algoritmo manualmente, é possível resolver isso com muita facilidade usando um solver de restrições como o MiniZinc
- Exemplo de código:
```
int: total;
array[int] of int: values = [10, 9, 1];
array[index_set(values)] of var 0..: coins;

constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
solve minimize sum(coins);
```
- É possível testar diretamente o exemplo no MiniZinc online
- O solver encontra progressivamente a solução ótima

Vários problemas de otimização/satisfação

Problemas de otimização matemática comuns em plataformas como o LeetCode, com maximização/minimização de função objetivo e várias restrições,
costumam ser difíceis de resolver em linguagens de programação por exigirem implementação de baixo nível, mas se encaixam bem em solvers de restrições
Por exemplo, vários problemas com as características abaixo entram nessa categoria

Exemplo 1: problema do lucro máximo com ações

"Dada uma lista de preços de ações, encontre o lucro máximo que pode ser obtido comprando uma vez e vendendo depois"
- Tradicionalmente, isso exige brute force O(n²) ou um algoritmo ótimo O(n)
- No MiniZinc, pode ser definido de forma simples como o problema de restrições abaixo
```
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
var int: buy;
var int: sell;
var int: profit = prices[sell] - prices[buy];

constraint sell > buy;
constraint profit > 0;
solve maximize profit;
```

Exemplo 2: chegar a 0 somando/subtraindo números específicos (problema de satisfação)

"É possível chegar a 0 somando ou subtraindo três números de uma lista?"

Basta encontrar uma solução satisfatória, não um valor ótimo

Em um solver de restrições, isso pode ser expresso assim

include "globals.mzn";
array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array[index_set(numbers)] of var {0, -1, 1}: choices;

constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
constraint count(choices, -1) + count(choices, 1) = 3;
solve satisfy;

Exemplo 3: maior área retangular em um histograma

"Dado um histograma com a altura de cada barra, encontre a maior área retangular possível"

Tradicionalmente, isso exige algoritmos complexos e gerenciamento de vários estados

Com restrições apenas, é possível descrever a solução de forma concisa

array[int] of int: numbers = [2,1,5,6,2,3];

var 1..length(numbers): x; 
var 1..length(numbers): dx;
var 1..: y;

constraint x + dx <= length(numbers);
constraint forall (i in x..(x+dx)) (y <= numbers[i]);

var int: area = (dx+1)*y;
solve maximize area;

output ["(\(x)->\(x+dx))*\(y) = \(area)"]

A abordagem com solver de restrições é melhor?

Em uma entrevista, há fragilidades em perguntas sobre complexidade de tempo e afins
- Solvers de restrições têm tempo de execução difícil de prever e normalmente são mais lentos do que algoritmos ótimos sob medida
- Ainda assim, costumam ser melhores do que um algoritmo mal implementado, e a maioria dos programadores não consegue escrever manualmente a solução ótima toda vez

A principal vantagem real é a flexibilidade para adicionar novas restrições

Por exemplo, no caso das ações, mudar de uma única compra e venda para várias operações faz a complexidade algorítmica disparar

Em um modelo de restrições no MiniZinc, isso pode ser acomodado com pequenas mudanças no código, mesmo com requisitos muito mais complexos

include "globals.mzn";
int: max_sales = 3;
int: max_hold = 2;
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array [1..max_sales] of var int: buy;
array [1..max_sales] of var int: sell;
array [index_set(prices)] of var 0..max_hold: stocks_held;
var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);

constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
constraint profit > 0;

constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
constraint alldifferent(buy ++ sell);
solve maximize profit;

output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];

Exemplos online de problemas com restrições costumam se concentrar em quebra-cabeças como Sudoku, mas eles podem ser usados de forma mais interessante e prática em problemas com lógica de negócio ou requisitos de otimização
- Por exemplo, também há grande potencial para aplicar técnicas avançadas de otimização como symmetry breaking

Encerramento e referências

Este texto faz parte da newsletter semanal do autor, que trata de história do software, métodos formais, novas tecnologias e teoria da engenharia de software
Se tiver interesse, você pode assinar ou consultar o site principal do autor
O novo livro do autor, "Logic for Programmers", também está sendo publicado

2 comentários

kohs100 2025-09-15

Normalmente, problemas de algoritmo não vêm com restrições de complexidade de tempo/espaço? Dizer que dá para resolver com um solver de restrições, no fim das contas, só mostra a capacidade de converter o problema em expressões de restrição... não tenho certeza se isso é mesmo uma habilidade necessária no trabalho do dia a dia...

GN⁺ 2025-09-13

Comentários do Hacker News

O maior problema das perguntas de entrevista no estilo Leetcode é que você não pode pedir esclarecimentos; como meu jeito de pensar difere do normal, o Leetcode parece depender de decorar respostas. Problemas com contexto suficiente são aceitáveis porque permitem um entendimento mais realista, mas a maioria carece de explicação e eu acabo nem entendendo direito o problema. Por isso, hoje em dia eu simplesmente recuso etapas de entrevista com Leetcode ou automação por IA. Tarefas, entrevistas 1:1 ou com compartilhamento de tela tudo bem. Se o site do Leetcode tivesse explicações e respostas realmente boas, estudar sozinho seria muito mais fácil, mas na prática é difícil demais. Não é só uma questão de habilidade; meu modo de pensar simplesmente não combina com esse tipo de problema. Ficar resolvendo múltipla escolha sem poder fazer perguntas parece um sistema montado para te fazer falhar. Estou falando especialmente de problemas no estilo IA/Leetcode usados em pré-entrevistas; em entrevistas com uma pessoa de verdade, onde há troca de perguntas, acho o ambiente perfeitamente bom
- Entrevistas LC (Leetcode) são meio como testar sua velocidade treinada nos 100 metros rasos; o trabalho real parece mais uma maratona longa em que você para e retoma várias vezes. Mesmo assim, hoje em dia, para ganhar um salário alto em empresas grandes tipo SMEGMA, é preciso jogar esse jogo. Por exemplo, eu construí um engine 2D do zero, mas acho que não passaria numa entrevista LC em que você precisa fazer vários problemas hard e ainda dar um mortal para trás. Já aceitei isso o engine que eu fiz
- Não é tudo questão de decorar soluções; mesmo decorando, você pode travar nas perguntas de acompanhamento. Mas, se a pessoa decorou e ainda resolve bem as perguntas extras, então eu acho que ela não terá problemas com questões no estilo Leetcode. Resolver problemas é capacidade de fazer correspondência de padrões, e quanto mais padrões você conhece, maior sua capacidade de resolver problemas. Agora o GPT resolve os problemas e ainda explica, então ficou mais fácil adquirir essa habilidade. Acho melhor aprender isso a partir de agora
- Concordo demais. Numa entrevista recente, tirei a nota máxima na tarefa, os engenheiros e até o CEO gostaram de mim, mas o CTO de repente me colocou numa entrevista de live coding e no fim fui rejeitado. Onze semanas de processo seletivo jogadas fora. É frustrante que esse processo idiota ainda exista. O demo/tarefa que eu fiz está aqui no link da Monumental e o resultado, código no GitHub
- Acho que o fato de você não poder fazer perguntas claras é justamente a habilidade que querem verificar de verdade: observar como o candidato aborda a resolução do problema. Se fizerem as pessoas abordarem tudo de forma categórica, todo software vai acabar ficando mais complexo e bagunçado. O realmente difícil não é escrever linhas de código, é o processo de resolver o problema
- Os lugares onde entrevistei davam um ou dois problemas de LC, mas se eu pedia explicações, eles imediatamente transformavam aquilo em conversa em tempo real e codificação ao vivo. Fazendo assim, uma desvantagem é que a carga psicológica do live coding aumenta bastante
Quando recebo esse tipo de problema de entrevista, tenho a sensação de que querem que você não apenas “use” um solver de restrições, mas que “implemente” você mesmo um solver de restrições adequado para um problema limitado
- Isso mesmo, e por isso acho que esse tipo de abordagem de entrevista é fundamentalmente mal-ajambrada. Numa situação real de engenharia, você toma café, lê artigos, vai à biblioteca, pensa andando, consulta ferramentas existentes (solver de restrições ou LLM) e consegue resolver o problema 100%. Mas numa entrevista eu provavelmente não conseguiria resolver nem 0%. Nunca nem considerei entrar numa empresa que faz esse tipo de entrevista
- Concordo totalmente. A maioria dos problemas NP pode ser convertida em problemas de restrição. Se um solver de restrições será ou não a resposta certa varia muito conforme o domínio de aplicação. E, em contexto de entrevista, quase nunca é a resposta certa. Esses solvers muitas vezes são muito mais lentos do que uma programação dinâmica simples
- Em entrevistas de algumas empresas isso pode ser verdade, mas em muitas outras não. Em geral, o uso de LC em entrevistas muitas vezes acontece por um único motivo: processos de contratação ineficientes. Até quem participa sabe que o sistema precisa ser reformulado, mas não tem poder para mudar ou está disperso demais. Em empresas grandes, o RH às vezes repassa as mesmas perguntas para vários times em nome da “padronização”, e empresas pequenas não têm tempo de preparar seus próprios problemas, então copiam da internet. Nessas situações, até os entrevistadores técnicos costumam ser críticos das entrevistas LC e tentam, na prática, encontrar candidatos que se destaquem. Nesse contexto, só demonstrar interesse ou conhecimento sobre solvers de restrições já costuma render uma boa pontuação
- Se alguém resolveu um problema LC hard com um solver de restrições e mesmo assim não foi contratado, então o entrevistador é que é burro. É raríssimo alguém saber o que é um solver de restrições e como definir um problema para usá-lo. Eu mesmo usei isso no terceiro ano da faculdade, e só escrever as restrições já era uma tarefa complicada o bastante para dar dor de cabeça
- Essa parte está certa e errada ao mesmo tempo. Já fiz esse tipo de pergunta em entrevista e, se o candidato pensasse em um solver de restrições, eu daria uma boa nota. Em engenharia real, solvers de restrições são subestimados, e pensar neles mostra que a pessoa sabe chegar rápido a uma resposta adequada. Claro, depois eu ainda faria perguntas adicionais no quadro para entender a capacidade real de programação. Mas propor um solver de restrições como resposta, por si só, não me parece ruim
É um insight interessante, mas acho que não se encaixa bem em entrevistas reais. O cerne desses problemas é verificar se o candidato consegue “pensar”. Resolver apenas por restrições mostra só nível de experiência e conhecimento; não revela se a pessoa realmente “pensou”
- Os entrevistadores tendem a usar muito os problemas de “Array String” do Leetcode “Top Interview 150”. Do ponto de vista de alguém como eu, desenvolvedor backend em Python, esses problemas parecem distantes do trabalho do dia a dia. A maioria exige algoritmos de operações in-place em arrays, algo normalmente necessário só em linguagens voltadas a performance como C ou Rust. Já problemas do tipo “Hashmap” são mais úteis para mostrar o uso de ferramentas adequadas à linguagem. Além disso, muitos problemas têm dificuldade mal calibrada, então problemas de nível “fácil” (por exemplo, Majority Element) na prática exigem algoritmos históricos como Boyer–Moore, o que torna difícil chamá-los de “fáceis”
- A última rodada que vi recentemente na Meta foi puramente um processo para verificar o quanto a pessoa tinha repetido e memorizado os problemas específicos deles. Então, se você responde de forma diferente da resposta de livro, eles ficam até sem graça. Dá a sensação de que “esperteza” em si não importa muito
- Algoritmos de DP bottom-up exigem algum raciocínio, mas a maioria dos problemas pode ser resolvida no estilo top-down (recursão + memoização). Por exemplo, o problema de troca de moedas pode ser resolvido melhor com busca A*. Mas, na prática, a maioria dos programadores quase nunca vai realmente usar esses algoritmos. O que importa de verdade é perceber quando você acidentalmente escreveu código com complexidade O(n^2). Se você olhar accidentallyquadratic.tumblr.com, até gente muito competente em projetos famosos comete esse tipo de erro com frequência. Então, a capacidade de inventar algoritmos num teste é diferente da capacidade de detectar erros algorítmicos trabalhando de verdade
- Quando avalio capacidade de resolução de problemas em entrevista, valorizo o processo de pensamento, a forma de comunicação e a decomposição do problema. É muito mais importante preparar perguntas cuja dificuldade possa ser ajustada para que todo candidato tenha a chance de mostrar sua capacidade. Se a pessoa simplesmente grita a primeira resposta que veio à cabeça ou fica travada por muito tempo, na prática o entrevistador quase não consegue extrair nada disso. Por isso, perguntas de entrevista focadas em resolução de problemas podem ser muito úteis, mas é uma pena que, na realidade, sejam mal utilizadas
- Esses problemas, na verdade, não testam “esperteza”, e sim o quanto você decorou uns 12 padrões padronizados. Quase todos os candidatos acabam aprovados ou reprovados com base não na própria criatividade para resolver problemas, mas na memória do que prepararam. As questões do LeetCode ficaram gamificadas demais e parecem ter virado um instrumento para medir apenas disposição para se preparar
A maioria das entrevistas parece partir da premissa de que “se um diabético não consegue sintetizar insulina em casa, então isso é trapaça no jogo da vida”. Assim como minha esposa toma insulina quando a glicose sobe, se o problema é de restrições, então faz sentido usar um solver. A menos que a empresa faça software de solver de restrições, não entendo por que exigir que a pessoa finja que esse tipo de software não existe e reconstrua tudo do zero
- O ponto central não é testar a capacidade de sintetizar insulina em uma crise, e sim um teste prévio de aptidão para ver se você consegue decorar o material em uma semana e recitá-lo bem numa entrevista por telefone
- Se você consegue descobrir como resolver o problema de forma eficiente com um solver de restrições, então também consegue facilmente montar uns dois for e uma função recursiva auxiliar para resolver qualquer problema de brinquedo
- (sem conteúdo significativo)
- Em defesa dos testes de programação, a maioria das pessoas que não consegue resolver nem problemas simples de DP também costuma ter pouca habilidade no trabalho real. Claro, há exceções, mas essa tem sido minha experiência
Sempre que surge o assunto de linguagens de programação por restrições, é preciso mencionar Håkan Kjellerstrand. Ele mantém um site excelente reunindo inúmeros exemplos e problemas, inclusive com MiniZinc hakank minizinc
- E ele não só criou um bom site, como também é uma pessoa extremamente gentil
Há muito tempo, quando eu ainda era um novato que não tinha aprendido sobre solvers de restrições no curso universitário de ciência da computação, encontrei esse problema porque um amigo me pediu para fazer um app de agendamento para um clube esportivo. No começo parecia fácil, mas, ao tentar de fato, eu nem percebia que tinha me metido num problemão enorme. Só depois isso virou uma boa lição sobre minha arrogância, e desde então essa experiência me ajuda muito quando discuto cronogramas, prazos e expectativas
- Pode ser uma pergunta básica, mas fico pensando se não daria para resolver mais facilmente com “otimização linear” em vez de solver de restrições. Pela minha experiência prática, uma vantagem da otimização linear é que ela permite tratar conflitos entre regras como pesos e encontrar uma solução que minimize os “efeitos colaterais” ao máximo
- Há 25 anos, no ensino médio, quando eu estava começando a aprender TI-Basic e VB6, eu trabalhava numa hamburgueria e ouvi o gerente reclamar que era difícil montar a escala semanal dos funcionários. Aí falei: “eu entendo de computador, faço um programa de escala para você!”. Logo percebi o quão difícil é escrever um escalonador e desisti na hora
“Se você usar esse tipo de problema em entrevista, o autor está dizendo que o entrevistador fica sem resposta se o candidato perguntar ‘qual é a complexidade de tempo desse algoritmo?’”, ou seja, se o solver de restrições também não resolver rápido o suficiente, então ele não é a resposta para um problema hard de Leetcode. Se as exigências de runtime forem folgadas, um método simples talvez funcione, mas encontrar uma solução eficiente é uma grande parte do desafio como um todo
- No trabalho real, quase sempre se exige muito mais “conceber uma solução que responda rapidamente a novos requisitos” do que “a solução mais eficiente possível”, então fico em dúvida sobre o sentido de entrevistas com critérios de eficiência tão distantes da realidade (embora isso possa variar conforme a função). Concordo com a visão do autor de que a solução mais eficiente nem sempre reflete a habilidade prática real. Essa também é uma das linhas de crítica ao Leetcode. Mesmo para o mesmo problema, parece mais objetivo avaliá-lo sob a ótica de “quão flexível você é para lidar com novos requisitos”
Solver de restrições? Boa ideia, já ouvi falar. Mas, numa entrevista, o que normalmente querem é que você implemente na mão em Python para ver seu fluxo de pensamento. (Tenho a sensação de que é quase impossível convencer alguém a usar um solver de restrições numa entrevista)
- Fico curioso se você já falou isso de fato para um entrevistador ou se é só uma suposição
- import z3
Se você resolver com DP (programação dinâmica) e depois disser “agora vou fazer também com solver de restrições”, é contratação imediata
- +1
A força real dos solvers de restrições está em como eles se adaptam facilmente a “novos requisitos”. Eu também senti muito esse benefício trabalhando com otimização de datacenter no Google, onde esse tipo de solver generalizado se ajustava com flexibilidade às mudanças de requisitos