Beaucoup de problèmes difficiles sur LeetCode sont en réalité de simples problèmes à contraintes

(buttondown.com)

6 points par GN⁺ 2025-09-13 | 2 commentaires | Partager sur WhatsApp

Même les problèmes difficiles de LeetCode peuvent être résolus bien plus facilement avec des solveurs de contraintes
Au lieu d’une programmation dynamique complexe ou d’un algorithme maison, on peut utiliser un solveur de contraintes comme MiniZinc pour résoudre simplement des problèmes d’optimisation mathématique
Les langages de programmation traditionnels expriment mal ce type de problèmes d’optimisation mathématique, ce qui fait la force de l’approche fondée sur les contraintes
Même lorsque des cas particuliers ou des contraintes supplémentaires apparaissent, les modifications du modèle restent minimes dans un solveur de contraintes
La complexité à l’exécution peut être moins bonne qu’avec un algorithme optimisé écrit à la main, mais cette approche offre de nombreux avantages en souplesse et en productivité de développement

Résoudre des problèmes LeetCode avec un solveur de contraintes

Choisir le bon outil

Lors de son premier entretien après l’université, l’auteur a reçu le problème de la « monnaie à rendre »
- Étant donné un ensemble de pièces, il faut trouver le nombre minimal de pièces nécessaire pour rendre un montant donné
- Il a utilisé un simple algorithme glouton, sans pouvoir garantir une solution optimale dans tous les cas
- La bonne réponse était la programmation dynamique, mais il n’a pas su l’implémenter et a échoué à l’entretien
Pourtant, sans implémenter directement l’algorithme, on peut résoudre cela très facilement avec un solveur de contraintes comme MiniZinc
- Exemple de code :
```
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);
```
- On peut essayer directement l’exemple MiniZinc en ligne
- Le solveur trouve progressivement la solution optimale

Divers problèmes d’optimisation et de satisfaction

Les problèmes d’optimisation mathématique courants sur LeetCode, avec fonction objectif à maximiser/minimiser et multiples contraintes,
sont difficiles à résoudre en langage de programmation à cause du niveau d’implémentation bas, mais conviennent bien aux solveurs de contraintes
Par exemple, les types de problèmes suivants en font partie

Exemple 1 : profit maximal sur une action

« À partir d’une liste de prix d’actions, trouver le profit maximal qu’on peut obtenir en achetant une fois puis en revendant plus tard »
- Traditionnellement, il faut un brute force en O(n²) ou un algorithme optimal en O(n)
- Dans MiniZinc, on peut le définir simplement comme un problème à contraintes
```
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;
```

Exemple 2 : obtenir 0 en additionnant/soustrayant certains nombres (problème de satisfaction)

« Peut-on obtenir 0 en additionnant ou soustrayant trois nombres d’une liste ? »

Il ne s’agit pas de trouver une valeur optimale, seulement une solution satisfaisante

Dans un solveur de contraintes, cela s’exprime ainsi

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;

Exemple 3 : aire maximale d’un rectangle dans un histogramme

« Dans un histogramme dont on connaît la hauteur de chaque barre, trouver l’aire du plus grand rectangle possible »

Traditionnellement, cela demande un algorithme complexe et beaucoup de gestion d’état

Avec de seules contraintes, on peut décrire la solution de façon concise

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)"]

L’approche par solveur de contraintes est-elle meilleure ?

En entretien, cela présente des faiblesses sur des questions comme la complexité temporelle
- Le temps d’exécution d’un solveur de contraintes est difficile à prévoir, et il est généralement plus lent qu’un algorithme optimal sur mesure
- Mais cela reste préférable à un algorithme mal implémenté de mauvaise qualité, et la plupart des programmeurs n’écrivent pas facilement la solution optimale eux-mêmes à chaque fois

Sa vraie force est la souplesse face à l’ajout de nouvelles contraintes

Par exemple, dans le cas des actions, passer d’un seul achat/vente à plusieurs fait exploser la complexité algorithmique

Dans un modèle de contraintes MiniZinc, on peut accepter des exigences bien plus complexes avec de petits changements de code

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)"];

Les exemples de problèmes à contraintes en ligne sont souvent centrés sur des puzzles comme Sudoku, mais cette approche peut être plus intéressante et plus utile en pratique pour de la logique métier ou des besoins d’optimisation réels
- Par exemple, elle se prête aussi à l’application de techniques d’optimisation avancées comme le symmetry breaking

Conclusion et références

Cet article est issu de la newsletter hebdomadaire de l’auteur, consacrée à l’histoire du logiciel, aux méthodes formelles, aux nouvelles technologies et à la théorie de l’ingénierie logicielle
Si cela vous intéresse, vous pouvez vous abonner ou consulter le site principal de l’auteur
Son nouveau livre, "Logic for Programmers", est également en cours de publication

2 commentaires

kohs100 2025-09-15

En général, les problèmes d’algorithmique ne viennent-ils pas avec des contraintes de complexité en temps/espace ? Dire qu’on peut les résoudre avec un solveur de contraintes revient au fond à montrer uniquement sa capacité à transformer le problème en système de contraintes… Je ne suis pas vraiment sûr que ce soit une compétence réellement nécessaire dans le travail au quotidien...

GN⁺ 2025-09-13

Commentaire Hacker News

Le plus gros problème des questions d’entretien de type Leetcode, c’est qu’on ne peut pas demander de précisions. Comme ma façon de réfléchir diffère de la norme, j’ai l’impression que Leetcode repose surtout sur la mémorisation des bonnes réponses. Quand un problème a assez de contexte, je peux en avoir une compréhension réaliste, donc ça me va, mais la plupart manquent d’explications et je n’arrive pas à bien cerner le problème. Du coup, maintenant, je refuse carrément les étapes d’entretien basées sur Leetcode ou sur l’automatisation par IA. Les exercices à rendre, les entretiens en 1:1 ou en partage d’écran me conviennent. S’il y avait sur le site Leetcode de vraies explications et de vraies solutions, l’autoformation serait bien plus facile, mais en pratique c’est trop difficile. Ce n’est pas simplement un problème de niveau : c’est surtout que ma manière de penser s’accorde mal avec ce type de problème. Enchaîner des QCM sans pouvoir poser de questions ressemble à un système conçu pour faire échouer les gens. Je parle surtout ici des problèmes de type IA/Leetcode utilisés en présélection ; dans un vrai entretien avec une personne en face et des échanges de questions, je trouve ça tout à fait correct.
- Les entretiens LC (Leetcode), c’est un peu comme tester une vitesse entraînée sur 100 mètres. Le vrai travail, c’est plutôt un long marathon avec des arrêts et des reprises. Cela dit, aujourd’hui, si on veut un gros salaire dans une grande entreprise façon SMEGMA, il faut jouer à ce jeu. Par exemple, j’ai moi-même créé un moteur de jeu 2D, mais je ne pense pas pouvoir réussir un entretien LC où il faut enchaîner plusieurs problèmes Hard, même en faisant des saltos arrière. Je l’ai déjà accepté. Le moteur que j’ai créé
- Tout ne se résume pas à mémoriser des solutions. Même en les apprenant par cœur, on peut bloquer sur les questions de relance. En revanche, si vous avez mémorisé et que vous gérez aussi bien les relances, alors à mon avis vous n’avez pas de problème avec les questions de style Leetcode. La résolution de problèmes, c’est de la reconnaissance de motifs, et plus on connaît de motifs, meilleur on devient. Maintenant que GPT peut aussi résoudre les problèmes et fournir des explications, ce type de compétence est plus facile à acquérir. Autant s’y mettre dès maintenant.
- Je compatis vraiment. Moi aussi, dans un entretien récent, j’ai obtenu la meilleure note sur l’exercice à rendre, les ingénieurs comme le CEO avaient une bonne impression, mais le CTO a soudain imposé un entretien de live coding, et j’ai fini recalé. Onze semaines d’entretiens pour rien. C’est désespérant que ce processus idiot existe encore. La démo/le devoir que j’avais fait : lien monumental et résultat, code GitHub
- On peut aussi se demander si le fait de ne pas pouvoir poser une question claire n’est pas justement la compétence qu’ils cherchent à vérifier : voir comment le candidat aborde un problème quand il le résout. Si on pousse les gens à n’aborder les choses que de façon catégorique, tous les logiciels finiront par devenir plus complexes et plus bancals. Le plus difficile, ce n’est pas d’écrire des lignes de code, c’est le processus de résolution du problème.
- Les endroits où j’ai passé des entretiens donnaient un ou deux problèmes LC, mais dès qu’on demandait des explications, on passait immédiatement à un échange en direct avec discussion et code. L’inconvénient, c’est que la pression psychologique du live coding en temps réel devient alors plus forte.
Quand on reçoit ce genre de problème en entretien, on a l’impression qu’on ne veut pas que vous « utilisiez » un solveur de contraintes, mais que vous en « écriviez un vous-même » adapté à un problème limité.
- Oui, et c’est pour ça que je trouve cette approche de l’entretien fondamentalement maladroite. En situation réelle d’ingénierie, on peut boire un café, lire des articles, aller à la bibliothèque, réfléchir en marchant, s’appuyer sur des outils existants (solveurs de contraintes ou LLM) et résoudre le problème à 100 %. En entretien, j’aurais l’impression de ne pas pouvoir en résoudre 0 %. Je n’ai même jamais envisagé de rejoindre une entreprise qui mène ce type d’entretien.
- Je pense vraiment que c’est vrai. La plupart des problèmes NP peuvent être convertis en problèmes à contraintes. En pratique, savoir si un solveur de contraintes est la bonne réponse ou non dépend énormément du domaine d’application. Et en entretien, ce n’est presque jamais la bonne réponse. Ces solveurs sont souvent bien plus lents qu’une simple programmation dynamique.
- Dans certaines entreprises, c’est effectivement vrai, mais pas partout. En général, l’usage de LC en entretien venait souvent d’une seule raison : un processus de recrutement inefficace. Même les participants savent qu’il faudrait revoir le système, mais ils n’ont pas le pouvoir nécessaire, ou il est trop dispersé pour que ça change. Dans les grandes entreprises, les RH font parfois circuler les mêmes questions entre différentes équipes pour des raisons de « standardisation », et les petites n’ont pas le temps de préparer leurs propres problèmes et récupèrent donc des questions sur Internet. Dans ces cas-là, même les intervieweurs techniques sont critiques envers les entretiens LC et essaient en pratique de repérer les candidats qui sortent du lot. Dans ce contexte, simplement montrer qu’on s’intéresse aux solveurs de contraintes ou qu’on en connaît l’existence peut déjà rapporter pas mal de points.
- Si quelqu’un a résolu un problème LC Hard avec un solveur de contraintes et qu’on ne l’embauche pas, c’est l’intervieweur qui est idiot. Très peu de gens savent ce qu’est un solveur de contraintes, encore moins définir un problème pour l’utiliser. J’en ai utilisé un en troisième année, et rien que formuler les contraintes était déjà une tâche assez compliquée pour donner mal à la tête.
- Sur ce point, c’est à la fois vrai et faux. J’ai déjà posé ce type de question en entretien, et si un candidat pensait à un solveur de contraintes, je lui mettais une bonne note. En ingénierie réelle, les solveurs de contraintes sont sous-estimés tout en étant un bon indicateur de la capacité à produire rapidement une bonne réponse. Bien sûr, ensuite je poserais des questions de whiteboard de suivi pour évaluer les vraies compétences en code. Mais proposer un solveur de contraintes comme réponse n’est pas, selon moi, une mauvaise chose.
C’est une belle intuition, mais je pense que ça colle mal aux entretiens réels. Le cœur de ce type de problème, c’est de vérifier la capacité du candidat à « se creuser la tête ». Le résoudre juste avec des contraintes ne montre que son niveau d’expérience et de connaissances ; ça ne dit pas vraiment s’il a « réfléchi ».
- Les intervieweurs ont tendance à poser souvent les problèmes « Array String » du « Top Interview 150 » de Leetcode. En tant que développeur backend Python, j’ai le sentiment que ces problèmes sont loin de mon travail quotidien. La plupart exigent des algorithmes de manipulation de tableaux in-place, ce qui n’est généralement utile qu’en C, Rust ou dans d’autres langages orientés performance. À l’inverse, les problèmes de type « Hashmap » sont plus utiles pour montrer l’usage d’outils adaptés au langage. Il y a aussi beaucoup de problèmes dont la difficulté est mal calibrée : certains classés « Easy » (par exemple Majority Element) demandent en réalité de connaître un algorithme historique comme Boyer–Moore. Difficile alors de les considérer comme vraiment « faciles ».
- Le dernier round que j’ai vu chez Meta consistait uniquement à vérifier à quel point les candidats avaient répété et mémorisé leurs problèmes spécifiques. Du coup, si on répond différemment de la solution scolaire, ça les déstabilise au contraire. J’ai l’impression que l’« intelligence » en soi n’a pas tant d’importance.
- Les algorithmes de DP bottom-up demandent un certain effort de réflexion, mais la plupart des problèmes peuvent se résoudre en top-down (récursion + mémoïsation). Par exemple, le problème du rendu de monnaie peut être mieux résolu avec une recherche A*. Mais en pratique, la majorité des programmeurs n’auront presque jamais besoin d’utiliser ce genre d’algorithmes. Ce qui compte vraiment, c’est de repérer quand on écrit par erreur du code en O(n^2). En regardant accidentallyquadratic.tumblr.com, on voit que même des gens très compétents sur des projets célèbres font souvent ce genre d’erreur. Donc la capacité à inventer un algorithme dans un test est distincte de la capacité à repérer des erreurs algorithmiques dans le vrai travail.
- Quand j’évalue la capacité de résolution de problèmes en entretien, j’accorde de l’importance au raisonnement, à la communication et à la décomposition du problème. Il est bien plus important de préparer des questions dont on peut ajuster la difficulté, afin que chaque candidat ait l’occasion de montrer ses compétences. Si quelqu’un crie immédiatement la réponse qui lui vient à l’esprit, ou reste bloqué pendant longtemps, en réalité l’intervieweur n’apprend pas grand-chose. C’est pour ça que les questions de résolution de problèmes peuvent être très utiles, mais c’est dommage qu’en pratique elles soient mal utilisées.
- Ces problèmes ne testent pas vraiment l’« intelligence », mais plutôt la mémorisation d’une douzaine de schémas standardisés. Chez presque tous les candidats, l’issue dépend moins de leur résolution créative de problème que de ce qu’ils ont mémorisé en préparation. Les problèmes LeetCode sont devenus tellement gamifiés qu’on a l’impression qu’ils servent surtout à mesurer la volonté de se préparer.
La plupart des entretiens semblent partir du principe suivant : « si un patient diabétique ne peut pas synthétiser lui-même son insuline chez lui, alors c’est de la triche dans le jeu de la vie ». De la même manière que ma femme s’injecte de l’insuline quand sa glycémie monte, si c’est un problème à contraintes, il est normal d’utiliser un solveur. Sauf si l’entreprise développe elle-même un logiciel de solveur de contraintes, je ne vois pas pourquoi elle exigerait qu’on fasse comme si ce logiciel n’existait pas et qu’on le recrée depuis zéro.
- L’essentiel n’est pas de tester la capacité à synthétiser de l’insuline en situation de crise, mais plutôt un test d’aptitude préalable visant à évaluer si l’on peut mémoriser un manuel en une semaine et bien le réciter lors d’un entretien téléphonique.
- Si vous êtes capable de trouver comment résoudre efficacement un problème avec un solveur de contraintes, alors vous pouvez facilement écrire deux boucles for et une petite fonction récursive auxiliaire pour résoudre n’importe quel problème jouet.
- (aucun contenu significatif)
- Pour défendre un peu les tests de code, la plupart des gens qui ne savent pas résoudre même un simple problème de DP ont aussi souvent un niveau insuffisant dans le travail réel. Il y a bien sûr des exceptions, mais c’est ce que j’ai constaté dans mon expérience.
Quand on parle de langages de programmation par contraintes, il faut toujours mentionner Håkan Kjellerstrand. Il tient un excellent site rassemblant d’innombrables exemples et problèmes, notamment pour MiniZinc : hakank minizinc
- Et en plus de faire un bon site web, c’est aussi une personne extrêmement gentille.
Il y a très longtemps, quand j’étais encore un bleu qui n’avait pas appris les solveurs de contraintes dans le cursus d’informatique à l’université, je suis tombé sur ce problème lorsqu’un ami m’a demandé de créer une application de planification pour un club de sport. Au début, ça paraissait simple, mais en essayant vraiment, je n’ai pas réalisé tout de suite que je me heurtais à un énorme problème. Plus tard, ça m’a servi de bonne leçon sur mon arrogance, et cette expérience m’aide encore beaucoup quand il faut discuter de planning, d’échéances et d’attentes.
- C’est peut-être une question naïve, mais je me demande si une « optimisation linéaire » ne permettrait pas de résoudre ça plus facilement qu’un solveur de contraintes. D’après mon expérience, l’avantage de l’optimisation linéaire est qu’on peut traiter les conflits entre règles sous forme de pondérations et chercher une solution qui minimise les « effets secondaires ».
- Il y a 25 ans, au lycée, alors que je commençais à peine à apprendre TI-Basic et VB6, je travaillais dans un fast-food et j’ai entendu le manager se plaindre de la difficulté à établir les plannings du personnel chaque semaine. Je lui ai dit : « Je m’y connais un peu en informatique, je vais vous faire un programme de planning ! » J’ai très vite compris à quel point écrire un ordonnanceur était difficile, et j’ai immédiatement abandonné.
« L’auteur dit que si on pose ce genre de problème en entretien, on est démuni si le candidat demande : “Quelle est la complexité en temps d’exécution de cet algorithme ?” » Autrement dit, un solveur de contraintes n’est pas non plus la réponse à un problème Leetcode Hard s’il n’arrive pas à le résoudre assez vite. Si les exigences de runtime sont larges, une méthode simple peut suffire, mais trouver une solution efficace fait partie intégrante du défi.
- En pratique, on demande bien plus souvent de « concevoir rapidement une solution qui s’adapte à de nouvelles exigences » que de trouver « la solution la plus efficace possible ». C’est pourquoi je doute de la pertinence d’entretiens fondés sur des critères d’efficacité aussi éloignés du réel, même si cela peut dépendre du poste. Je partage l’idée de l’auteur selon laquelle la solution la plus efficace ne reflète pas forcément la vraie compétence en production. C’est aussi l’un des angles de la critique de Leetcode : pour un même problème, il serait plus objectif d’évaluer à quel point quelqu’un sait s’adapter de façon flexible à de nouvelles exigences.
Un solveur de contraintes ? Bonne idée, j’en ai déjà entendu parler. Mais en entretien, en réalité, ils veulent surtout vous voir l’implémenter vous-même en Python pour observer votre cheminement de pensée. (J’ai l’impression qu’il est presque impossible de convaincre quelqu’un d’utiliser un solveur de contraintes en entretien.)
- Je me demande si tu en as vraiment parlé à un intervieweur, ou si c’est seulement une supposition.
- import z3
Si vous le résolvez d’abord avec de la DP (programmation dynamique), puis dites « maintenant je vais aussi le faire avec un solveur de contraintes », vous êtes embauché sur-le-champ.
- +1
La vraie force des solveurs de contraintes, c’est à quel point ils s’adaptent facilement à de « nouvelles exigences ». J’en ai moi-même fait largement l’expérience chez Google, en travaillant sur l’optimisation de datacenters, où ces solveurs généralisés apportaient un énorme bénéfice en restant flexibles face aux changements de besoins.