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

301–310 of 551 posts

Re: Many hard LeetCode problems are easy constraint problems

#301

Post by drob518 »

LegionMammal978 wrote: post #292
sigbottle wrote: post #216

Earlier quoted context omitted.

I think they're saying that the types of counter-examples are so pathological in most cases that if you're doing any kind of auto-generation of constraints - for example, a DSL backed by a solver - should have good enough heuristics. Like it might even be the case that certain types of pretty powerful DSLs just never generate "bad structures". I don't know, I've not done research on circuits, but this kind of analysi…

Idk, I also thought so once upon the time. "Everyone knows that you can usually do much better than the worst case in NP-hard problems!" But at least for the non-toy problems I've tried using SAT/ILP solvers for, the heuristics don't improve on the exponential worst case much at all. It's seemed like NP-hardness really does meet the all-or-nothing stereotype for some problems. Your best bet using them is when you hav…

For some problems, there is not much you can do. But for many, it works.

Re: Many hard LeetCode problems are easy constraint problems

#302

Post by dataflow »

Der_Einzige wrote: post #30
dataflow wrote: post #21

My beef with someone using a constraint solver here is that they almost certainly wouldn't be able to guarantee anything about their solution other than that, if it produces an output, it will be correct. They won't be able to guarantee running time, space usage, or (probably for most tools) even a useful progress indicator. The problem isn't merely that they used another tool - the problem is that they abstracted aw…

[flagged]

> First of all, Nice ChatGPT response

What the heck are you talking about? I didn't even visit ChatGPT today.

Re: Many hard LeetCode problems are easy constraint problems

#303

Post by freehorse »

tavavex wrote: post #201
bluGill wrote: post #175

Earlier quoted context omitted.

That is what people miss about interviews. Often when you interview you don't have reasonable leads on any other job and so you don't feel like there is a choice since you likely need a job (unemployment rarely pays as well as a job). However interviews are not only about the company deciding if they will hire you, they are also about do you want to work there and convincing you to take the job if one is offered. So…

People don't miss that about interviews, they just know that the balance of power is so skewed that the interests of the employer become the only relevant part. The employer can keep going through hundreds of applicants until they find someone who's literally perfect in every single way, they have nearly unlimited time. Meanwhile, the applicants need a job now, any job at all, they're on a hard time limit until their…

Unless you are really desperate to find a job, there are definitely workplaces you would want to avoid. While a power imbalance does in principle exist, that doesn’t mean you usually have no choice at all. Of course that is less of a case when you just start, but in general pp can go around doing interviews and negotiating positions rather than just accept the first offer.

Re: Many hard LeetCode problems are easy constraint problems

#304

Post by cerved »

loeg wrote: post #71
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.

In what way? They're useful for toy problems like this but they're very slow on larger problems.

Define large. We've written model which solves real business issues in 8K lines of MiniZinc and it wasn't slow.

The conventional wisdom is the larger you make an NP hard problem, the slower is going to get. Irregardless of algorithm.

Re: Many hard LeetCode problems are easy constraint problems

#305

Post by Calavar »

roncesvalles wrote: post #264
samiv wrote: post #167

Earlier quoted context omitted.

The LC interviews are like testing people how fast they can run 100m after practice, while the real job is a slow arduous never ending jog with multiple detours and stops along the way. But yeah that's the game you have to play now if you want the top $$$ at one of the SMEGMA companies. I wrote (for example) my 2D game engine from scratch (3rd party libs excluded) https://github.com/ensisoft/detonator but would not b…

>The LC interviews are like testing people how fast they can run 100m after practice Ah, but, the road to becoming good at Leetcode/100m sprint is: >a slow arduous never ending jog with multiple detours and stops along the way Hence Leetcode is a reasonably good test for the job. If it didn't actually work, it would've been discarded by companies long ago. Barring a few core library teams, companies don't really care…

> Hence Leetcode is a reasonably good test for the job. If it didn't actually work, it would've been discarded by companies long ago.

I see it differently. I wouldn't say it's reasonably good, I'd say it's a terrible metric that's very tenuously correlated with on the job success, but most of the other metrics for evaluating fresh grads are even worse. In the land of the blind the one eyed man is king.

> If you can show that you can become excellent at one thing, there's a good chance you can become excellent at another thing.

Eh. As someone who did tech and then medicine, a lot great doctors would make terrible software engineers and vice versa. Some things, like work ethic and organization, are going to increase your odds of success at nearly any task, but there's plenty other skills that are not nearly as transferable. For example, being good at memorizing long lists of obscure facts is a great skill for a doctor, not so much for a software engineer. Strong spatial reasoning is helpful for a software developer specializing in algorithms, but largely useless for, say, an oncologist.

Re: Many hard LeetCode problems are easy constraint problems

#306

Post by sigbottle »

LegionMammal978 wrote: post #292
sigbottle wrote: post #216

Earlier quoted context omitted.

I think they're saying that the types of counter-examples are so pathological in most cases that if you're doing any kind of auto-generation of constraints - for example, a DSL backed by a solver - should have good enough heuristics. Like it might even be the case that certain types of pretty powerful DSLs just never generate "bad structures". I don't know, I've not done research on circuits, but this kind of analysi…

Idk, I also thought so once upon the time. "Everyone knows that you can usually do much better than the worst case in NP-hard problems!" But at least for the non-toy problems I've tried using SAT/ILP solvers for, the heuristics don't improve on the exponential worst case much at all. It's seemed like NP-hardness really does meet the all-or-nothing stereotype for some problems. Your best bet using them is when you hav…

> Your best bet using them is when you have a large collection of smaller unstructured problems, most of which align with the heuristics.

Agreed. An algorithm right now in our company turns a directed graph problem, which to most people would seem crazy, into roughly ~m - n (m edges, n nodes) SAT checks that are relatively small. Stuffing all the constraints into an ILP solver would be super inefficient (and honestly undefined). Instead, by defining the problem statement properly and carving out the right invariants, you can decompose the problem to smaller NP-complete problems.

Definitely a balancing act of design.

Re: Many hard LeetCode problems are easy constraint problems

#307

Post by cerved »

gnarlouse wrote: post #163

Been working on a calendar scheduling app that uses a constraint solver to auto schedule events based on scheduling constraints (time of day preferences and requirements, recurrence rules), and track goal progress (are you slipping on your desired progress velocity? Get a notification). It’s also a meal planner: from a corpus of thousands of good, healthy recipes, schedule a meal plan that reuses ingredients nearing…

Which solver do you use?

Re: Many hard LeetCode problems are easy constraint problems

#308

Post by deadghost »

samiv wrote: post #167
tracker1 wrote: post #77

My biggest problem with leetcode type questions is that you can't ask clarifying questions. My mind just doesn't work like most do, and leetcode to some extent seems to rely on people memorizing leetcode type answers. On a few, there's enough context that I can relate real understanding of the problem to, such as the coin example in the article... for others I've seen there's not enough there for me to "get" the ques…

The LC interviews are like testing people how fast they can run 100m after practice, while the real job is a slow arduous never ending jog with multiple detours and stops along the way. But yeah that's the game you have to play now if you want the top $$$ at one of the SMEGMA companies. I wrote (for example) my 2D game engine from scratch (3rd party libs excluded) https://github.com/ensisoft/detonator but would not b…

>how fast they can run 100m after practice, while the real job is a slow arduous never ending jog with multiple detours and stops along the way

I've always explained it as demonstrating your ping pong skills to get on the basketball team.

Re: Many hard LeetCode problems are easy constraint problems

#309

Post by cerved »

Gunax wrote: post #111

Internally, do contraint solvers just do brute force? It's interesting how powerful contraint solvers are (Ive never used one). But actually all of these problems are fairly simple if we allow brute force solutions. They just become stacked loops.

No. They use sophisticated algorithms called propagators to prune the invalid solutions from the domains of possible solutions in conjunction with a search strategy, like branch and bound

Re: Many hard LeetCode problems are easy constraint problems

#310

Post by tannhaeuser »

Here's an easy ad-hoc Prolog program for the first problem:

    % Given a set of coin denominations,
    % find the minimum number of coins
    % required to make change.
    % IE for USA coinage and 37 cents,
    % the minimum number is four
    % (quarter, dime, 2 pennies).
    num(0). num(1). num(2).
    num(3). num(4). num(5).
    ?- num(Q), num(D), num(P),
       37 is Q * 25 + D * 10 + P
You can just paste it into [1] to execute in the browser. Using 60 as target sum is more interesting as you can enumerate over two solutions.

(Posting again what I already posted two days ago [2] here)

[1]: https://quantumprolog.sgml.net/browser-demo/browser-demo.htm...

[2]: https://news.ycombinator.com/item?id=45205030

Post reply on HN