Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Many hard LeetCode problems are easy constraint problems

buttondown.com

Post reply on HN
Print view View original

11–20 of 551 posts

Re: Many hard LeetCode problems are easy constraint problems

#11

Post by NoahZuniga »

YetAnotherNick wrote: post #6
Analemma_ wrote: post #4

Earlier quoted context omitted.

Yes and no: I've asked questions like this in interviews, and I'd count it as a plus if the candidate reached for a constraint solver. They're criminally underused in real-world software engineering and this would show the candidate probably knows how to get the right answer faster instead of wasting a bunch of time. Now, if they did answer with a constraint solver, I'd probably ask some followup whiteboard questions…

General constraint solver would be terribly inefficient for problems like these. It's a linear problem and constraint solver just can't handle O(10^6) variables without some beefy machine.

O(10^6) = O(1)

Re: Many hard LeetCode problems are easy constraint problems

#12

Post by the_af »

> The "smart" answer is to use a dynamic programming algorithm, which I didn't know how to do. So I failed the interview.

Really? This kind of interview needs to go away.

However, coding interviews are useful. It's just that "knowing the trick" shouldn't be the point. The point is whether the candidate knows how to code (without AI), can explain themselves and walk through the problem, explain their thought processes, etc. If they do a good enough reasoning job but fail to solve the problem (they run out of time, or they go on an interesting tangent that ultimately proves fruitless) it's still a "passed the test" situation for me.

Failure would mean: "cannot code anything at all, not even a suboptimal solution. Cannot reason about the problem at all. Cannot describe a single pitfall. When told about a pitfall, doesn't understand it nor its implications. Cannot communicate their thoughts."

An interview shouldn't be an university exam.

Re: Many hard LeetCode problems are easy constraint problems

#13

Post by corimaith »

kccqzy wrote: post #5

Great insight. But this is sadly not applicable to interviews. > It's easy to do in O(n^2) time, or if you are clever, you can do it in O(n). Or you could be not clever at all and just write it as a constraint problem This nails it. The point of these problems is to test your cleverness. That's it. Presenting a not-clever solution of using constraint solvers shows that you have experience and your breadth of knowledg…

>The point of these problems is to test your cleverness.

No it's just memorization of 12 or so specific patterns. The stakes are too high that virtually everyone going in will not be staking passing on their own inherent problem solving ability. LeetCode has been so thoroughly gamified that it has lost all utility of differentiability beyond willingness to prepare.

Re: Many hard LeetCode problems are easy constraint problems

#14

Post by PartiallyTyped »

Analemma_ wrote: post #4
holden_nelson wrote: post #3

I feel like if I'm being asked this in an interview, they're not asking me to use a constraint solver, they're asking me to _write_ a constraint solver. Just for a specific constraint problem, not a more general constraint solver.

Yes and no: I've asked questions like this in interviews, and I'd count it as a plus if the candidate reached for a constraint solver. They're criminally underused in real-world software engineering and this would show the candidate probably knows how to get the right answer faster instead of wasting a bunch of time. Now, if they did answer with a constraint solver, I'd probably ask some followup whiteboard questions…

It’d be a positive in my book if they used a constraint solver.

Re: Many hard LeetCode problems are easy constraint problems

#15

Post by dekhn »

NoahZuniga wrote: post #11
YetAnotherNick wrote: post #6

Earlier quoted context omitted.

General constraint solver would be terribly inefficient for problems like these. It's a linear problem and constraint solver just can't handle O(10^6) variables without some beefy machine.

O(10^6) = O(1)

no, the "O" here is "on the order of", not Big O notation.

Re: Many hard LeetCode problems are easy constraint problems

#19

Post by _alternator_ »

holden_nelson wrote: post #3

I feel like if I'm being asked this in an interview, they're not asking me to use a constraint solver, they're asking me to _write_ a constraint solver. Just for a specific constraint problem, not a more general constraint solver.

This. Literally every problem in NP can be cast as a constraint problem. The question of whether a solver is the right solution varies a lot depending on the application, and in an interview , it’s almost by definition not the right solution.

They can also be dreadfully slow (and typically are) compared to just a simple dynamic program.

Re: Many hard LeetCode problems are easy constraint problems

#20

Post by x187463 »

the_af wrote: post #12

> The "smart" answer is to use a dynamic programming algorithm, which I didn't know how to do. So I failed the interview. Really? This kind of interview needs to go away. However, coding interviews are useful. It's just that "knowing the trick" shouldn't be the point. The point is whether the candidate knows how to code (without AI), can explain themselves and walk through the problem, explain their thought processes…

I agree with this approach. With the exception of testing for specific domain knowledge relevant to the work role, the coding interview should just be about testing the applicant's problem-solving skills and grasp of their language of choice. I would even prefer a take-home style problem that we can review in-person over some high-pressure puzzle. The leetcode interview doesn't seem to correspond to anything a developer actually does day to day.
Post reply on HN