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

511–520 of 551 posts

Re: Many hard LeetCode problems are easy constraint problems

#511

Post by torginus »

bubblyworld wrote: post #508
torginus wrote: post #497

Earlier quoted context omitted.

I'm sorry but after reading your comment I can't seem to be able to decide if you favor writing the dynamic programming version or pulling in the constraint solver. Both are correct in the sense that they give the right output, and I don't think pulling in a huge library (maintained by who knows and for how long) is going to be beneficial for maintenace. And having a good understanding of both the precise requirement…

There are other aspects to maintenance, like requirements change. In this case it's trivial to change or add new constraints to a constraint solver, whereas even small changes to a typical DP problem can require a total rethink of the approach. Extending the analogy to other kinds of dependencies left as an exercise for the reader. Point being that software has many dimensions. Reducing the use of dependencies to fea…

Imo, deepending on the desired quality of the result and the amount and complexity of bespoke requirements, the more of the former are present, the more strongly I consider rolling something bespoke.

With out-of-the-box libraries, the more custom requirements I have, the more trouble I tend to have supporting them, and trying to make something do a thing it wasn't designed for, can erase initial gains very quickly. At least this has been my experience over the years.

Re: Many hard LeetCode problems are easy constraint problems

#512

Post by cerved »

gnarlouse wrote: post #507
cerved wrote: post #307

Earlier quoted context omitted.

Which solver do you use?

Google ORTools’ CpSolver, with IntervalVars for the calendar portion.

Presumably you run it with multiple workers, preferably in parallel (it's designed to run like that)

Depending on your problem and how you can solve it (single threaded & low memory vs. anything goes) it might be a good idea trying other solvers. OR-Tools CP-SAT(LP) pretty much never does bad on a any problems but there are other CP-SAT solvers like Chuffed & Huub as well as Gecode which is a pure CP solver that does great providing you can make a gif search heuristic up front. Another option is of course racing solvers.

Then there are other things like MIP solvers, CBLS solvers etc. The nice thing with MiniZinc is that it's pretty easy to compare different solver backbends for a problem

Re: Many hard LeetCode problems are easy constraint problems

#513

Post by Jun8 »

zahlman wrote: post #492
mgradowski wrote: post #337

Earlier quoted context omitted.

Isn't it trivially [1]?

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

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?

Re: Many hard LeetCode problems are easy constraint problems

#514

Post by shoo »

j2kun wrote: post #128

> The real advantage of solvers, though, is how well they handle new constraints. Well said. One of the big benefits of general constraint solvers is their adaptability to requirements changes. Something I learned well when doing datacenter optimization for Google.

Agreed - adaptability to changing requirements is a very strong advantage for real-world work.

The first attempt to formalise some practical problem into a mathematical optimisation problem is often not quite right. You discover new things that change the problem statement after reviewing example solutions with experts who exclaim "that solution couldn't possibly work, because ".

A neat dynamic programming solution is a glorious thing, but dynamic programming relies on a mathematical problem with some elegant recursive substructure that you can exploit. Sometimes such elegant recursive substructure is going to be broken by additional requirements or side constraints that you discover during the project -- so the real valuable problem you actually need to solve has no such substructure, and you need to throw out your dynamic programming approach and go back to a blank sheet of paper to design a viable attack on the real valuable messy problem.

For lower-risk delivery of useful outcomes, it probably makes the most sense to use general purpose flexible black box solvers like constraint or MIP solvers early in the project, and focus efforts on rapidly discovering and extracting all the requirements, so you zero in on the real problem quicker. You don't want to prematurely invest a lot of time and effort building a highly efficient bespoke elegant solution to the wrong problem, then discover a month before a delivery deadline that everything needs to be thrown out.

Re: Many hard LeetCode problems are easy constraint problems

#515

Post by gnarlouse »

cerved wrote: post #512
gnarlouse wrote: post #507

Earlier quoted context omitted.

Google ORTools’ CpSolver, with IntervalVars for the calendar portion.

Presumably you run it with multiple workers, preferably in parallel (it's designed to run like that) Depending on your problem and how you can solve it (single threaded & low memory vs. anything goes) it might be a good idea trying other solvers. OR-Tools CP-SAT(LP) pretty much never does bad on a any problems but there are other CP-SAT solvers like Chuffed & Huub as well as Gecode which is a pure CP solver that does…

Wow thanks, I’ll have to look at those. The CPSAT was an LLM suggestion that I just ran with after doing some very weak research—im not a constraint programming researcher by any means. Since we’re on the topic and you seem knowledgeable, any good primer literature I might check out for understanding the basis of tweaking constraint solvers? I have started running into some performance issues after integrating an optimization function, and have started to wonder how can I claim back some performance.

Re: Many hard LeetCode problems are easy constraint problems

#516

Post by Qem »

drob518 wrote: post #62

SAT, SMT, and constraint solvers are criminally underutilized in the software industry. We need more education about what they are, how they work, and what sorts of problems they can solve.

What are some good books to get started on the subject?

Re: Many hard LeetCode problems are easy constraint problems

#517

Post by mzl »

gnarlouse wrote: post #515
cerved wrote: post #512

Earlier quoted context omitted.

Presumably you run it with multiple workers, preferably in parallel (it's designed to run like that) Depending on your problem and how you can solve it (single threaded & low memory vs. anything goes) it might be a good idea trying other solvers. OR-Tools CP-SAT(LP) pretty much never does bad on a any problems but there are other CP-SAT solvers like Chuffed & Huub as well as Gecode which is a pure CP solver that does…

Wow thanks, I’ll have to look at those. The CPSAT was an LLM suggestion that I just ran with after doing some very weak research—im not a constraint programming researcher by any means. Since we’re on the topic and you seem knowledgeable, any good primer literature I might check out for understanding the basis of tweaking constraint solvers? I have started running into some performance issues after integrating an opt…

The MiniZinc Coursera courses (https://www.minizinc.org/resources/#courses-title) are useful to get a good basis for understanding constraint programming. It’s not a fast solution being full courses, but it is a very good resource.

Re: Many hard LeetCode problems are easy constraint problems

#518

Post by almostgotcaught »

antonvs wrote: post #270
almostgotcaught wrote: post #242

Earlier quoted context omitted.

It's the same exact thing - if some company makes you jump through hoops to get hired that you find distasteful just don't apply to company.

Not all of us are market extremists. The “invisible hand of the market” doesn’t care about human rights.

I don't understand what you're saying. We're not talking about the market exploiting labor because before you are hired by the company you're not labor for the company. Is this really that difficult to understand?

Re: Many hard LeetCode problems are easy constraint problems

#519

Post by DoctorOetker »

torginus wrote: post #451

Very interesting article and good points. But how about we flip the original statement around: Many problems thought to require giant software packages/libraries are very solvable locally if you know what you are doing This is why LC is actually meaningful - imagine if you faced the coin challenge problem IRLin prod and you decided to pull in a constraint solver - what would've been a 25 line function now is a giant…

hard disagree:

Given ANY problem: first ask yourself have others solved this before? that is a hard question to answer, since we don't know in which context a similar puzzle was solved before (structures in different domains can boil down to the same mathematical puzzle). A literature search would be very time costly.

The most important point is the flexibility in being able to change the puzzle (a small change in the puzzle can result in a large change in the type of solution), as the author of the article points out. The bespoke algorithm is brittle. Description of the problem itself is less brittle (you can reuse most of the problem statement).

It may sound incredibly expensive to pull in a constraint solver, but if the application warrants constraint-solver-quality results, it should afford either the dependency, or the data structures and solvers used in the solver dependency, to optimize for the application,

Its just bizarre to ask people to beat the feats of those standing on the shoulders of giants, without allowing them to stand on the shoulders of giants too.

Think about why one is recruiting employees with data structure skills (so more than just information plumbers). Is it really so strange that the most qualified people understand the reality that the state of the art is constantly changing, but understand at least the basics of how these solvers work internally?

Viewed through this lens, the ideal job candidate are those who design, implement and maintain... constraint solvers! Assuming their familiarity with the constraint-solver code-base they could profile the solver package while its solving the puzzle. Do this on many instances of the puzzle, and keep track of the dead-ends and optimal solutions, to figure out which functionality can be ripped out of the solver, and which must be kept.

So in order of preference:

1. Programmers or mathematicians (or equivalent, think physicists, etc.) familiar with 1 or more constraint solver source code bases.

2. End-users of a constraint solver package, with sufficient familiarity (as a user) with constraint solvers. WITH data structure and algorithms experience.

3. End-users of a constraint solver package as above, but without data structure and algorithms knowledge

4. People with data structure and algorithms knowledge.

If 1. is too expensive you'll have to combine skills over multiple hires.

If industry is really interested in good profiles for these criteria, it should sponsor universities / students to get familiar with constraint solver usage, and if possible constraint solver development and contributions. After a few years the candidates will pop into existence.

Re: Many hard LeetCode problems are easy constraint problems

#520

Post by nitwit005 »

saagarjha wrote: post #474
roadside_picnic wrote: post #43

Earlier quoted context omitted.

> The point of these problems is to test your cleverness. Last round I did at Meta it was clearly to test that you grinded their specific set of problems, over and over again, until you could reproduce them without thinking. It's clear because the interviewers are always a bit surprised when you answer with whatever is not the text-book approach on both leetcode and on the interview guide they studied. Cleverness is…

Interviewers are typically surprised when you do something new because they reuse questions with a lot of people and eventually you end up seeing most variations of a solution.

It's at times very clear people are following an interview guide, and just assume you're wrong if your approach isn't in the guide.
Post reply on HN