Viele schwierige LeetCode-Probleme sind einfache Constraint-Probleme

(buttondown.com)

6 Punkte von GN⁺ 2025-09-13 | 2 Kommentare | Auf WhatsApp teilen

Selbst schwierige LeetCode-Probleme lassen sich mit einem Constraint-Solver deutlich leichter lösen
Statt komplexer dynamischer Programmierung oder eigener Algorithmen können mit Constraint-Solvern wie MiniZinc mathematische Optimierungsprobleme einfach gelöst werden
Traditionelle Programmiersprachen eignen sich nur schwer dazu, solche mathematischen Optimierungsprobleme auszudrücken, weshalb ein constraint-basierter Ansatz hier seine Stärken ausspielt
Selbst wenn Sonderfälle oder zusätzliche Constraints hinzukommen, sind bei einem Constraint-Solver nur minimale Änderungen am Modell nötig
Die Laufzeitkomplexität kann zwar schlechter sein als bei einem handoptimierten Algorithmus, aber bei Flexibilität und Entwicklungsgeschwindigkeit gibt es viele Vorteile

LeetCode-Probleme mit einem Constraint-Solver lösen

Das richtige Werkzeug wählen

Der Autor bekam in seinem ersten Bewerbungsgespräch nach dem Uniabschluss das "Coin Change Problem"
- Gegeben sind Münzwerte, gesucht ist die minimale Anzahl von Münzen, um einen bestimmten Betrag herauszugeben
- Er verwendete einen einfachen Greedy-Algorithmus, der jedoch nicht in allen Fällen die optimale Lösung garantiert
- Dynamische Programmierung wäre die richtige Antwort gewesen, aber weil er sie nicht implementieren konnte, scheiterte das Gespräch
Mit einem Constraint-Solver wie MiniZinc lässt sich das Problem aber sehr einfach lösen, ohne den Algorithmus selbst zu implementieren
- Beispielcode:
```
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);
```
- Das Beispiel lässt sich online direkt in MiniZinc ausführen
- Der Solver findet schrittweise die optimale Lösung

Verschiedene Optimierungs-/Erfüllungsprobleme

Mathematische Optimierungsprobleme, wie sie auf LeetCode häufig vorkommen (Maximierung/Minimierung einer Zielfunktion unter mehreren Constraints), sind in Programmiersprachen wegen der Low-Level-Implementierung oft schwer auszudrücken, passen aber gut zu Constraint-Solvern
Dazu gehören zum Beispiel verschiedene Probleme der folgenden Art

Beispiel 1: Problem des maximalen Aktiengewinns

"Gegeben ist eine Liste von Aktienkursen. Bestimme den maximalen Gewinn, der durch einmaliges Kaufen und späteres Verkaufen erzielt werden kann"
- Traditionell braucht man dafür entweder O(n²)-Brute-Force oder einen optimalen O(n)-Algorithmus
- In MiniZinc lässt sich das einfach als Constraint-Problem formulieren
```
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;
```

Beispiel 2: Mit Addition/Subtraktion bestimmter Zahlen 0 erzeugen (Erfüllbarkeitsproblem)

"Kann man aus einer Liste drei Zahlen addieren oder subtrahieren, sodass 0 entsteht?"

Es muss kein optimaler Wert gefunden werden, sondern nur eine erfüllbare Lösung

In einem Constraint-Solver kann man das so ausdrücken

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;

Beispiel 3: Größte Rechteckfläche in einem Histogramm

"Gegeben ist ein Histogramm mit den Höhen seiner Balken. Bestimme die größte mögliche Rechteckfläche"

Traditionell braucht man dafür komplexe Algorithmen und die Verwaltung vieler Zustände

Mit Constraints allein lässt sich die Lösung kompakt beschreiben

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

Ist der Constraint-Solver-Ansatz wirklich besser?

In Bewerbungsgesprächen hat dieser Ansatz Schwächen, etwa bei Fragen zur Zeitkomplexität
- Die Laufzeit eines Constraint-Solvers ist schwer vorherzusagen und meist langsamer als ein maßgeschneiderter optimaler Algorithmus
- Trotzdem ist er besser als ein fehlerhaft implementierter schlechter Algorithmus, und die meisten Programmierer können nicht jedes Mal die optimale Lösung selbst schreiben

Die eigentliche Stärke ist die Flexibilität, wenn neue Constraints hinzukommen

Wenn man im Aktienbeispiel etwa nicht nur einmal, sondern mehrfach kaufen und verkaufen darf, steigt die algorithmische Komplexität stark an

In einem Constraint-Modell in MiniZinc lassen sich solche deutlich komplexeren Anforderungen mit nur kleinen Codeänderungen abbilden

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

Online-Beispiele für Constraint-Probleme drehen sich oft um Rätsel wie Sudoku, doch tatsächlich lässt sich der Ansatz interessanter und praktischer für Business-Logik oder Optimierungsanforderungen nutzen
- Zum Beispiel ist auch der Einsatz fortgeschrittener Optimierungstechniken wie symmetry breaking gut möglich

Abschluss und Hinweise

Dieser Text stammt aus dem wöchentlichen Newsletter des Autors und behandelt Softwaregeschichte, formale Methoden, neue Technologien und Theorien des Software Engineering
Bei Interesse kann man den Newsletter abonnieren oder die Hauptwebsite des Autors besuchen
Das neue Buch des Autors "Logic for Programmers" ist ebenfalls erschienen

2 Kommentare

kohs100 2025-09-15

Haben algorithmische Probleme normalerweise nicht Vorgaben für Zeit-/Speicherkomplexität? Wenn man sie mit einem Constraint-Solver lösen kann, zeigt das im Grunde nur, dass man das Problem in Nebenbedingungen übersetzen kann … Ich bin mir nicht sicher, ob das wirklich eine Fähigkeit ist, die man im Arbeitsalltag braucht …

GN⁺ 2025-09-13

Hacker-News-Kommentare

Das größte Problem bei Interviewfragen vom Leetcode-Typ ist, dass man keine zusätzlichen Erklärungen erfragen kann. Da meine Denkweise von der üblichen abweicht, scheint Leetcode stark darauf zu beruhen, richtige Antworten auswendig zu lernen. Bei Aufgaben mit genügend Kontext kann ich sie realistisch verstehen, aber bei den meisten fehlt die Erklärung, sodass ich das Problem nicht richtig erfasse. Deshalb lehne ich Leetcode oder KI-automatisierte Interviewstufen inzwischen grundsätzlich ab. Aufgaben, 1:1-Gespräche oder Screen-Sharing-Interviews sind für mich okay. Wenn es auf der Leetcode-Seite ordentliche Erläuterungen und Lösungen gäbe, wäre Selbststudium auch viel einfacher, aber in der Praxis ist es viel zu schwer. Es ist nicht einfach nur eine Frage des Könnens, sondern meine Denkweise passt nicht zu diesem Problemtyp. Immer nur Multiple-Choice-artige Aufgaben zu lösen, ohne Fragen stellen zu dürfen, wirkt wie ein System, das auf Scheitern ausgelegt ist. Ich spreche dabei besonders über KI-/Leetcode-artige Aufgaben für Vorabinterviews. Ein echtes Interview mit einer realen Person, in dem Fragen hin und her gehen, halte ich dagegen für völlig in Ordnung.
- LC-(Leetcode-)Interviews sind ein bisschen so, als würde man die trainierte Geschwindigkeit auf 100 Metern testen. Die eigentliche Arbeit ist eher ein langer Marathon mit vielen Stopps und Umwegen. Trotzdem muss man dieses Spiel spielen, wenn man heute bei Großunternehmen wie SMEGMA ein hohes Gehalt bekommen will. Ich habe zum Beispiel selbst eine 2D-Game-Engine gebaut, aber ich würde wohl kein LC-Interview bestehen, bei dem man mehrere schwere LC-Probleme inklusive Rückwärtssalto lösen muss. Das habe ich inzwischen akzeptiert. Meine Engine
- Es geht nicht nur darum, Lösungen auswendig zu lernen. Selbst wenn man sie auswendig kann, kann man bei Nachfragen scheitern. Wenn man aber auswendig gelernt hat und auch die Zusatzfragen gut löst, dann hat man meiner Meinung nach kein Problem mit Aufgaben im Leetcode-Stil. Problemlösefähigkeit ist Mustererkennung, und je mehr Muster man kennt, desto besser wird man beim Lösen von Problemen. Jetzt, da GPT sowohl Aufgaben lösen als auch Erklärungen liefern kann, lässt sich diese Fähigkeit leichter aneignen. Ich denke, es ist besser, sie sich ab jetzt noch anzueignen.
- Das fühle ich sehr. Ich hatte kürzlich ein Interview, bei dem ich bei der Aufgabe die Bestnote bekam und sowohl die Engineers als auch der CEO einen guten Eindruck von mir hatten, aber dann setzte der CTO plötzlich ein Live-Coding-Interview an und am Ende wurde ich abgelehnt. Elf Wochen Interviewprozess waren damit umsonst. Es ist frustrierend, dass es diesen idiotischen Prozess immer noch gibt. Die Demo/Aufgabe, die ich gemacht habe, ist hier der Link zu Monumental und dem Ergebnis, GitHub-Code
- Ist nicht genau die Fähigkeit, keine klaren Fragen stellen zu können, das, was man eigentlich prüfen will? Also wie ein Kandidat beim Lösen eines Problems vorgeht. Wenn man Leute nur zu einem bestimmten, eindeutigen Zugang zwingt, wird jede Software am Ende eher komplexer und chaotischer. Das wirklich Schwierige ist nicht, Codezeilen zu schreiben, sondern der Prozess, ein Problem zu lösen.
- Bei den Stellen, bei denen ich interviewt wurde, gab es zwar ein oder zwei LC-Probleme, aber sobald man um eine Erklärung bat, ging es direkt in ein Gespräch mit Live-Coding über. Der Nachteil daran ist, dass der psychologische Druck von echtem Live-Coding größer wird.
Wenn ich solche Interviewaufgaben sehe, habe ich das Gefühl, dass man nicht will, dass man einen Constraint Solver „benutzt“, sondern dass man einen auf das begrenzte Problem zugeschnittenen Constraint Solver „selbst schreibt“.
- Genau, und deshalb halte ich diesen Interviewansatz im Kern für unbeholfen. In einer echten Engineering-Situation würde man Kaffee trinken, Papers lesen, in die Bibliothek schauen, spazieren gehen und nachdenken und dabei vorhandene Tools heranziehen, etwa Constraint Solver oder LLMs, um das Problem zu 100 % zu lösen. In einer Interviewsituation hätte ich dagegen das Gefühl, nicht einmal 0 % zu schaffen. Ich habe nie auch nur daran gedacht, zu einer Firma zu gehen, die so interviewt.
- Das stimmt wirklich. Die meisten NP-Probleme lassen sich in Constraint-Probleme umwandeln. Ob ein Constraint Solver tatsächlich die richtige Antwort ist, hängt in der Praxis stark vom Anwendungsbereich ab. Und in Interviews ist er fast nie die richtige Antwort. Solche Solver sind oft deutlich langsamer als einfache Dynamic Programming-Lösungen.
- In manchen Unternehmensinterviews mag das zutreffen, in vielen aber nicht. Allgemein wurde LC in Interviews oft aus genau einem Grund eingesetzt: wegen ineffizienter Einstellungsprozesse. Sogar die Beteiligten wissen, dass das System reformiert werden müsste, haben aber entweder nicht genug Macht oder sind zu verstreut, um etwas zu ändern. In großen Unternehmen verteilt HR zur „Standardisierung“ oft dieselben Fragen an verschiedene Teams, und kleine Unternehmen haben keine Zeit, eigene Aufgaben vorzubereiten, und kopieren deshalb etwas aus dem Internet. In solchen Situationen sind selbst technische Interviewer oft kritisch gegenüber LC-Interviews und versuchen praktisch eher, Kandidaten zu finden, die positiv herausstechen. In so einem Umfeld reicht es oft schon für eine ziemlich gute Bewertung, Interesse an Constraint Solvern oder Wissen darüber zu zeigen.
- Wenn jemand ein LC-Hard-Problem mit einem Constraint Solver gelöst hat und dann nicht eingestellt wird, ist der Interviewer selbst dumm. Leute, die überhaupt wissen, was ein Constraint Solver ist, und ihn durch Problemformulierung einsetzen können, sind extrem selten. Ich habe so etwas im dritten Studienjahr benutzt, und schon das Formulieren der Constraints war kompliziert genug, um einem den Kopf zu verdrehen.
- Dieser Punkt ist zugleich richtig und falsch. Ich habe solche Fragen selbst in Interviews gestellt, und wenn ein Bewerber auf die Idee eines Constraint Solvers kam, gab ich dafür eine gute Bewertung. Im echten Engineering sind Constraint Solver unterschätzt, und sie zeigen, ob jemand in der Lage ist, schnell zu einer sauberen Antwort zu kommen. Natürlich würde ich danach noch Whiteboard-Folgefragen stellen, um die eigentliche Coding-Kompetenz zu prüfen. Aber einen Constraint Solver als Antwort vorzuschlagen, ist aus meiner Sicht nicht schlecht.
Ein cooler Einblick, aber ich glaube nicht, dass das gut zu realen Interviews passt. Im Kern dieser Probleme geht es darum, beim Bewerber die Fähigkeit zum „Nachdenken“ zu prüfen. Etwas einfach als Constraint-Formulierung zu lösen zeigt nur Erfahrungs- und Wissensstand, aber nicht unbedingt, ob jemand wirklich „den Kopf benutzt“ hat.
- Interviewer neigen dazu, oft „Array String“-Probleme aus Leetcode „Top Interview 150“ zu stellen. Für mich als Backend-Python-Entwickler fühlen sich diese Aufgaben weit von meiner eigentlichen Arbeit entfernt an. Meist verlangen sie In-Place-Array-Operationsalgorithmen, die man normalerweise nur in performanceorientierten Sprachen wie C oder Rust braucht. „Hashmap“-Typ-Aufgaben sind dagegen nützlicher, weil sie zeigen, wie man sprachgerechte Werkzeuge einsetzt. Außerdem gibt es viele Aufgaben mit schlecht abgestufter Schwierigkeit, sodass Probleme der Kategorie „Easy“ (zum Beispiel Majority Element) in Wirklichkeit historische Algorithmen wie Boyer–Moore voraussetzen. Das ist schwer als „leicht“ zu sehen.
- Die letzte Runde, die ich kürzlich bei Meta gesehen habe, diente ausschließlich dazu zu prüfen, wie oft man genau ihre speziellen Aufgaben wiederholt auswendig gelernt hat. Wenn man anders als die Lehrbuchantwort antwortet, sind sie eher irritiert. Es fühlt sich nicht so an, als wäre „Cleverness“ besonders wichtig.
- Bottom-up-DP-Algorithmen verlangen bis zu einem gewissen Grad echtes Nachdenken, aber die meisten Probleme lassen sich top-down lösen, also mit Rekursion plus Memoization. Das Coin-Change-Problem zum Beispiel lässt sich mit A*-Suche besser lösen. In der Realität werden die meisten Programmierer solche Algorithmen aber kaum jemals wirklich einsetzen. Viel wichtiger ist es, zu merken, wenn man versehentlich Code mit O(n^2)-Zeitkomplexität schreibt. Auf accidentallyquadratic.tumblr.com sieht man, dass selbst sehr fähige Leute in bekannten Projekten solche Fehler häufig machen. Deshalb ist die Fähigkeit, in einem Test einen Algorithmus zu entwickeln, etwas anderes als die Fähigkeit, bei der Arbeit algorithmische Fehler zu erkennen.
- Wenn ich in Interviews Problemlösefähigkeit prüfe, lege ich Wert auf Denkprozess, Kommunikationsweise und Problemzerlegung. Viel wichtiger ist es, Fragen vorzubereiten, deren Schwierigkeit sich steuern lässt, damit alle Bewerber die Chance haben, ihre Fähigkeiten zu zeigen. Ob jemand sofort eine Antwort herausruft oder lange feststeckt, liefert dem Interviewer in Wirklichkeit oft nur sehr begrenzt verwertbare Informationen. Deshalb können problemlösungsorientierte Interviewfragen sehr nützlich sein, aber es ist schade, dass sie in der Praxis so selten gut eingesetzt werden.
- Diese Aufgaben testen nicht wirklich „Cleverness“, sondern ob man ungefähr ein Dutzend standardisierte Muster auswendig gelernt hat. Bei fast allen Bewerbern entscheidet eher die vorbereitete Merkfähigkeit als kreatives Problemlösen darüber, ob sie bestehen. Leetcode-Probleme sind so stark gamifiziert, dass es sich anfühlt, als prüften sie nur noch die Bereitschaft zur Vorbereitung.
Die meisten Interviews scheinen davon auszugehen: „Wenn ein Diabetiker nicht selbst zu Hause Insulin synthetisieren kann, ist das im Spiel des Lebens Schummeln.“ So wie meine Frau Insulin spritzt, wenn ihr Blutzucker steigt, sollte man bei einem Constraint-Problem eben einen Solver benutzen. Wenn das Unternehmen keine Constraint-Solver-Software entwickelt, verstehe ich nicht, warum man extra voraussetzt, dass es solche Software nicht gibt, und verlangt, alles wieder von Grund auf neu zu bauen.
- Im Kern geht es nicht darum, die Fähigkeit zu testen, in einer Krise Insulin zu synthetisieren, sondern um einen vorgelagerten Eignungstest: Kann jemand innerhalb einer Woche den Lehrstoff auswendig lernen und ihn im Telefoninterview gut aufsagen?
- Wenn man einen effizienten Weg findet, ein Problem mit einem Constraint Solver zu lösen, dann kann man auch problemlos zwei for-Schleifen und eine Hilfsrekursionsfunktion schreiben und damit jedes Spielzeugproblem lösen.
- (kein inhaltlich relevanter Beitrag)
- Zur Verteidigung von Coding-Tests: Die meisten Leute, die nicht einmal ein einfaches DP-Problem lösen können, sind auch in der realen Arbeit oft nicht besonders gut. Natürlich gibt es Ausnahmen, aber meiner Erfahrung nach war das so.
Wenn das Thema Constraint-Programmiersprachen aufkommt, muss man immer Håkan Kjellerstrand erwähnen. Er betreibt eine großartige Website mit unzähligen Beispielen und Problemen, darunter viel zu MiniZinc. hakank minizinc
- Und er hat nicht nur eine gute Website gemacht, sondern ist tatsächlich auch ein ausgesprochen freundlicher Mensch.
Vor sehr langer Zeit, als ich noch ein unerfahrener Student war, der im Informatikstudium noch nichts über Constraint Solver gelernt hatte, stieß ich auf dieses Problem, als mich ein Freund bat, eine App zur Terminplanung für einen Sportverein zu bauen. Anfangs sah es leicht aus, aber als ich es wirklich versuchte, merkte ich nicht einmal, dass ich in ein riesiges Problem hineingeraten war. Erst später wurde es zu einer guten Lektion über meine eigene Arroganz, und diese Erfahrung hilft mir bis heute sehr bei Gesprächen über Zeitpläne, Fristen und Erwartungen.
- Vielleicht eine Anfängerfrage, aber könnte man das statt mit einem Constraint Solver nicht leichter mit „linearer Optimierung“ lösen? Aus eigener Erfahrung ist ein Vorteil der linearen Optimierung, dass man Konflikte zwischen Regeln als Gewichtungen behandeln und so eine Lösung mit minimalen „Nebenwirkungen“ finden kann.
- Vor 25 Jahren, in meiner Highschool-Zeit, als ich gerade anfing, TI-Basic und VB6 zu lernen, jobbte ich in einem Burgerladen. Ich hörte, wie sich der Manager darüber beklagte, dass die wöchentliche Einsatzplanung für die Mitarbeiter so schwer sei, und sagte: „Ich kenne mich etwas mit Computern aus, ich schreibe Ihnen ein Planungsprogramm!“ Kurz darauf merkte ich, wie schwierig es wirklich ist, einen Scheduler zu schreiben, und gab sofort wieder auf.
„Die Behauptung des Autors ist, dass man mit so einer Aufgabe im Interview aufgeschmissen wäre, wenn der Interviewer fragt: ‚Wie ist die Laufzeitkomplexität dieses Algorithmus?‘“ Das heißt: Auch ein Constraint Solver ist keine Antwort auf ein Leetcode-Hard-Problem, wenn er es nicht schnell genug lösen kann. Wenn die Laufzeitanforderungen locker sind, mag ein einfacher Ansatz genügen, aber eine effiziente Lösung zu finden, ist ein großer Teil der gesamten Herausforderung.
- In der Praxis geht es viel häufiger darum, „schnell eine Lösung für neue Anforderungen zu entwerfen“ als „die effizienteste aller Lösungen“ zu finden. Deshalb ist fraglich, wie sinnvoll Interviews mit wirklichkeitsfernen Effizienzmaßstäben sind, auch wenn das natürlich je nach Rolle unterschiedlich sein kann. Ich stimme der Sicht des Autors zu, dass die effizienteste Lösung nicht unbedingt reale Arbeitsfähigkeit widerspiegelt. Das ist auch ein Kontext, in dem Leetcode kritisiert wird. Selbst beim selben Problem wäre es objektiver, darauf zu schauen, wie flexibel jemand mit neuen Anforderungen umgehen kann.
Constraint Solver? Gute Idee, schon davon gehört. Aber in Interviews will man in der Praxis meist einfach sehen, wie jemand es direkt in Python implementiert und dabei denkt. (Ich habe das Gefühl, es ist fast unmöglich, im Interview den Einsatz eines Constraint Solvers durchzusetzen.)
- Hast du das dem Interviewer tatsächlich schon einmal so gesagt, oder ist das nur eine Vermutung?
- import z3
Wenn du es erst mit DP (Dynamic Programming) löst und dann sagst: „Jetzt mache ich es auch noch mit einem Constraint Solver“, dann bist du sofort eingestellt.
- +1
Die eigentliche Stärke von Constraint Solvern in der Praxis ist, wie leicht sie sich an „neue Anforderungen“ anpassen lassen. Ich habe diesen Vorteil auch selbst stark erlebt, als ich bei Google an der Optimierung von Rechenzentren gearbeitet habe: Solche generalisierten Solver können bei geänderten Anforderungen sehr flexibel reagieren.