✳flâneur — a map of the web's best reading

Many Hard Leetcode Problems are Easy Constraint Problems • Buttondown

buttondown.com · 1,499 words · saved by 1 readers

Given a set of coin denominations, find the minimum number of coins required to make change for a given number. IE for USA coinage and 37 cents, the minimum number is four (quarter, dime, 2 pennies). I implemented the simple greedy algorithm and immediately fell into the trap of the question: the greedy algorithm only works for "well-behaved" denominations. If the coin values were [10, 9, 1], then making 37 cents would take 10 coins in the greedy algorithm but only 4 coins optimally (10+9+9+9). The "smart" answer is to use a dynamic programming algorithm, which I didn't know how to do. So I failed the interview. But you only need dynamic programming if you're writing your own algorithm. It's really easy if you throw it into a constraint solver like MiniZinc and call it a day. You can try this online here. It'll give you a prompt to put in total and then give you successively-better solutions: Lots of similar interview questions are this kind of mathematical optimization problem, where

September 10, 2025 Many Hard Leetcode Problems are Easy Constraint Problems Use the right tool for the job. In my first interview out of college I was asked the change counter problem: Given a set of coin denominations, find the minimum number of coins required to make change for a given number. IE for USA coinage and 37 cents, the minimum number is four (quarter, dime, 2 pennies). I implemented the simple greedy algorithm and immediately fell into the trap of the question: the greedy algorithm only works for "well-behaved" denominations. If the coin values were [10, 9, 1] , then making 37 cen

Explore this link on the map →

saved by

related reading