Many hard LeetCode problems are easy constraint problems

Posted by mpweiher 9/12/2025

Many hard LeetCode problems are easy constraint problems(buttondown.com)

679 points | 533 commentspage 4

SCLeo 9/12/2025|

Does using a constraint solver actually solve the question under the time ... constraints?

If not, how can you claim you have solved the problem?

jameslai 9/12/2025||

Terrible question for an interview, and further highlights how our interviews are broken.

Greedy algorithms tell you nearly nothing about the candidate's ability to code. What are you going to see? A single loop, some comparison and an equality. Nearly every single solution that can be solved with a greedy algorithm is largely a math problem disguised as programming. The entire question hinges on the candidate finding the right comparison to conduct.

The author himself finds that these are largely math problems:

> Lots of similar interview questions are this kind of mathematical optimization problem

So we're not optimizing to find good coders, we're optimizing to find mathematicians who have 5 minutes of coding experience.

At the risk of self-promotion, I'm fairly opinionated on this subject. I have a podcast episode where I discuss exactly this problem (including discuss greedy algorithms), and make some suggestions where we could go as an industry to avoid these kind of bad-signal interviews:

https://socialengineering.fm/episodes/the-problem-with-techn...

avgDev 9/12/2025|

My best interview consisted of: -what projects have you done

-what tech you worked with and some questions about decisions

-debugging an issue they encountered before

-talking about interests and cultural fit

Instant green flag for me. Too bad that after receiving my offer covid happened and they had a hiring freeze.

ryanjshaw 9/12/2025|||

This is how I prefer to interview. I don’t understand the mindset of LeetCode interviewers. It’s a weak signal because it’s easily gamed (false positives), and has misses too many strong candidates who have better things to do in their spare time (false negatives, bias towards one type of candidate -> lack of diversity in experience).

scotty79 9/12/2025|||

I've seen some cases where someone bragged about projects they participated in but then struggle to write a simple loop.

You can try to sus out smooth talking faker or just tell them to write a thing and then talk only after they demonstrate basic comprehension.

cratermoon 9/12/2025||

I've always maintained that solving LeetCode is more about finding the hidden "trick" that makes the solution, if not easy, one that is already "solved" in the general sense. Look at the problem long enough and realize "oh that's a sliding window problem" or somesuch known solution, and do that.

zzzeek 9/12/2025||

I've never heard of a "dynamic programming algorithm". Read wikipedia and it seems to mean....use a recursive function? The coin problem is an easy recursive problem (I just wrote the code for it to make sure my old brain can still do it).

Jtsummers 9/12/2025||

It's usually covered in a first or second year algorithms course. It's a recursive problem definition paired with tabling to eliminate redundant work. Critically, the recursive subproblems have to be overlapping (they'll do some of the same work as the other recursive steps) to see any benefit. You can implement it top-down and add a cache (memoization) or you can implement it bottom-up and fill out the table iteratively rather than through recursion.

If you just implement it recursively without tabling then you end up re-doing work and it's often an exponential runtime instead of polynomial.

To clarify on overlapping, consider Fibonacci:

  F(n) = F(n-1) + F(n-2) # and the base cases

F(n-1) includes F(n-2) in its definition, and both F(n-2) and F(n-1) include F(n-3). If you implement this naively it produces an exponential runtime. Once you add the table, the single initial recursive call to F(n-1) will end up, through its chain of calls, storing the result of F(n-2) and now the implementation is linear instead of exponential.

joz1-k 9/12/2025|||

> Read wikipedia and it seems to mean....use a recursive function?

Yes, that's one (common) approach to dynamic programming. The recursive function call are memoized so that previous calculations are remembered for future function calls. Overlapping subproblems become trivial if you can reuse previously computed values. The recursion with memoization is top-down dynamic programming.

scotty79 9/12/2025||

So all in all pretty basic stuff. Why would anyone worth their salt should have problem with that?

dgacmu 9/13/2025||

The hard part is realizing that the problem you're solving efficiently maps to a dynamic programming algorithm. You have to spot the opportunity for sub-problem reuse, or else the solution looks something like cubic or exponential (etc.)

scotty79 9/13/2025||

> You have to spot the opportunity for sub-problem reuse

Which sounds exactly like what developers do in non boring parts of our job. If anything, the problem is that tests are being tightly timed, while time budget for real world task of this kind is usually more generous. On the other hand business time that company spends with inefficient solution or without one costs a lot of money so I can't blame companies for wanting employee who at least on toy problems can do that quick.

runeblaze 9/13/2025||

The coin problem is like the intro to it. Try some of the codeforces one :skull:

jongjong 9/13/2025||

My Leetcode ability is unpredictable. I either ace the test or I can't finish it in time. The only way to make outcomes predictable is practice, but I have too much agency and not enough time for that.

Leetcode requires a very different set of skills from software engineering. Software engineering isn't so much about solving puzzles as it is about making good decisions. It's about knowing what's important and knowing where the boundaries are. It's about anticipating problems in their broadest form; creating just the right amount of flexibility and allowing the solution to solidify as your understanding of the problem deepens.

CamperBob2 9/12/2025||

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).

That's a bad algorithm, then, not a greedy algorithm. Wouldn't a properly-implemented greedy algorithm use as many coins as possible of a given large denomination before dropping back to the next-lower denomination?

If a candidate's only options are to either use a constraint solver or to implement a naïver-than-usual greedy algorithm, well, sorry, but that's a no-hire.

Peritract 9/12/2025||

The algorithm they're using must be "Until you hit the limit, take the highest denomination coin that fits beneath the limit. If you can't hit the limit, fall back one step."

That fits your definition of "use as many coins as possible of a given large denomination before dropping back to the next-lower denomination" but will find 10-10-10-1-1-1-1-1-1-1 and stop before it even tries 10-9-anything.

smegma2 9/12/2025|||

There is no greedy solution to the problem. A greedy algorithm would start by taking 3 10-cent coins to make 37 which is wrong.

Jtsummers 9/12/2025|||

> Wouldn't a properly-implemented greedy algorithm use as many coins as possible of a given large denomination before dropping back to the next-lower denomination?

Yes, and it won't work on the problem described. The greedy algorithm only works on certain sets of coins (US coin denominations are one of those sets), and fails in at least some cases with other coin sets (as illustrated in the bit you quoted).

CamperBob2 9/12/2025|||

D'oh, that makes sense, I didn't consider the case where it would keep returning 10.

the_af 9/12/2025||

By the way, ChatGPT was able to solve this problem and give the correct solution.

Jtsummers 9/12/2025|||

It's in numerous algorithms textbooks and probably a lot of code repositories, so that's not surprising.

the_af 9/13/2025||

I didn't mean it was surprising. I meant literally what I said: I tried it, and it worked. Nothing more, nothing less.

the_af 9/13/2025|||

Interesting that an informative comment, without any implications or insinuations, got downvoted.

HN sucks sometimes. "Intellectual discourse" and "hacker curiosity" my ass.

CamperBob2 9/15/2025||

I voted you back up. It's the least I could do. :)

FilosofumRex 9/13/2025||

SAT & CSP are criminally under utilized in CS classes, because profs have no clue about them.

That's why in so many industries they prefer to hire engineers and OR grads and teach them python, than hire SWE and teach them modeling

Jun8 9/12/2025||

An interesting meta problem is to determine antagonistic set of denominations, like the [10,9,1] example given in the post, to maximize the number of coins selected by the gradient method.

mgradowski 9/12/2025|

Isn't it trivially [1]?

zahlman 9/13/2025||

Perhaps what is meant is "maximize the difference between the optimal result and the one calculated by the naive greedy algorithm".

Jun8 9/13/2025||

Thanks for clarifying my poorly worded description, that’s exactly what I meant. Like in the example given, the difference is 10-4=6, let’s call this the naive_greedy_miss_factor. Can we choose three other denominations so that NGMF is > 6?

notemap 9/12/2025||

https://codeforces.com/problemset/problem/1889/D

guluarte 9/12/2025|

Most leetcode problems fall into the same ~15 patterns, and hard problems most of the time require you to use a combination of two patterns to solve them.

More comments...