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

491–500 of 551 posts

Re: Many hard LeetCode problems are easy constraint problems

#491

Post by mwcz »

komali2 wrote: post #459
mmis1000 wrote: post #457

Earlier quoted context omitted.

You probably haven't see front-end projects that pulls tons of library for a simple sorting or grouping task. Sometimes even solvable with build-in array function alone. It's a true nightmare when you have to deal with that kind of projects.

What, like lodash? Some of those hail from a time that we didn't have a good set of native methods. So the library is just legacy'd in. But I do agree, lodash performance compared to native functions is crazy bad.

Is that the case? I saw a talk by the author of lodash years ago and he touched on performance. The built-in functions are (or were?) implemented in JS, level terrain for a library like lodash to beat "native" performance. Lodash beat browser built-ins in some cases. The talk was ten years ago, though, so things may have changed. Perhaps more of the built-ins are written in C++ now.

Here's the talk: https://youtu.be/2DzaOnOyCqE?si=McCMjzGopzSCoaCi

Re: Many hard LeetCode problems are easy constraint problems

#492

Post by zahlman »

mgradowski wrote: post #337
Jun8 wrote: post #328

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.

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

Re: Many hard LeetCode problems are easy constraint problems

#493

Post by [deleted] »

deepsun wrote: post #417
tharkun__ wrote: post #351

Earlier quoted context omitted.

It's funny you mention that. That's literally what CS teaches you too. Which is what "leetcode" questions are: fundamental CS problems that you'd learn about in a computer science curriculum. It's called "reducing" one problem to another. We had an entire semester's mandatory class spend a lot of time on reducing problems. Like figuring out how you can solve a new type of question/problem with an algorithm or two tha…

I did quite a bit of competitive programming in school, and pretty much all the world-class competitive problems are reduced to well-known algorithms. It's quite hard to come up with something new (not proven to be unsolvable for its constraints). I believe problem setters just try to disguise a known algorithm as much as possible. Then comes the ability/memorization to actually code it, e.g. if I knew it needs codin…

[deleted]

Re: Many hard LeetCode problems are easy constraint problems

#494

Post by notemap »

deepsun wrote: post #417
tharkun__ wrote: post #351

Earlier quoted context omitted.

It's funny you mention that. That's literally what CS teaches you too. Which is what "leetcode" questions are: fundamental CS problems that you'd learn about in a computer science curriculum. It's called "reducing" one problem to another. We had an entire semester's mandatory class spend a lot of time on reducing problems. Like figuring out how you can solve a new type of question/problem with an algorithm or two tha…

I did quite a bit of competitive programming in school, and pretty much all the world-class competitive problems are reduced to well-known algorithms. It's quite hard to come up with something new (not proven to be unsolvable for its constraints). I believe problem setters just try to disguise a known algorithm as much as possible. Then comes the ability/memorization to actually code it, e.g. if I knew it needs codin…

Solve one of my problems :)

https://www.acmicpc.net/problem/33797

Try with an LLM too :)

Re: Many hard LeetCode problems are easy constraint problems

#495

Post by tmtvl »

joenot443 wrote: post #477
yepitwas wrote: post #203

Earlier quoted context omitted.

I agree that doing that without asking if they really mean "any" would in fact demonstrate traits that might be bad for a co-worker. If the candidate reads that this may be the case, asks for, obviously, that reason, and the interviewer confirms that they mean "any", then it's a red flag for that interviewer , at least, as a co-worker, if they go on to get upset over your choice, unless it's something where you're ob…

> If the candidate reads that this may be the case, asks for, obviously, that reason, and the interviewer confirms that they mean "any", then it's a red flag for that interviewer I think the confusing part to me is why a rational candidate would assume it'd be a good signal to use an esoteric language to solve a problem in the first place. Like my understanding is that J would be a pretty inappropriate choice if you…

If J is the right tool to use to handle a problem with, Prolog is an alright tool for that purpose, and Python is kind of a bad fit; why would you use Python instead of J or Prolog?

If I need to drive a screw I'll first grab a screwdriver. If that's not okay I suppose I could use a knife. A monkey wrench would not be among the first tools I reach for.

Re: Many hard LeetCode problems are easy constraint problems

#497

Post by torginus »

jvanderbot wrote: post #455
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…

Wait are you making the opposite claim? That one should eschew the "correct" formulation in favor of a bespoke one? Despite the stated (and hopefully obvious) difficulties that brings with maintenance, generalization, etc?

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 requirements, and the algorithms used to solve them also helps maintenance.

It's just having two dozen lines tucked of code away in a function in the repo seems infinitely more maintainable to me then using some giant framework (of possibly unknown quality) to solve the issue.

This is a general argument I'm making, not just applying to this constraint solver/

Re: Many hard LeetCode problems are easy constraint problems

#498

Post by godelski »

wst_ wrote: post #344
godelski wrote: post #277

Earlier quoted context omitted.

> you can't ask clarifying questions Which isn't that the main skill actually being tested? How the candidate goes about solving problems? I mean if all we did was measure peoples' skills at making sweeping assumptions we'd likely end up with people who oversimplify problems and all of software would go to shit and get insanely complex... Is the hard part writing the lines of code or solving the problem?

Skill? LC is testing rote memorization of artificial problems you most likely never encounter in actual work.

You didn't read my comment correctly and should have and clarifying questions

Re: Many hard LeetCode problems are easy constraint problems

#499

Post by the_af »

the_af wrote: post #316
CamperBob2 wrote: post #101

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…

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

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

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

Re: Many hard LeetCode problems are easy constraint problems

#500

Post by the_af »

Jtsummers wrote: post #330
the_af wrote: post #316

Earlier quoted context omitted.

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

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

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