9 ms·
Many hard LeetCode problems are easy constraint problems
- teleforce 1y agoConstraint programming complement ML/AI/LLM nicely in system solving real world problems [1],[2],[3],[4]. One of the highest stakes and hardest engineering problems namely wireless spectrum frequency allocation was solved by constraint programming and presented in [1]. Now anyone can try to solve the problem in a MiniZinc tutorial. Fun fact, there's also Knuth in the presentation audience trying to get some info on the subject matter perhaps for his next book. [1] Logic, Optimization, and Constraint Programming: A Fruitful Collaboration - John Hooker - CMU (2023) [video]: https://www.youtube.com/live/TknN8fCQvRk https://www.youtube.com/live/TknN8fCQvRk [2] "We Really Don't Know How to Compute!" - Gerald Sussman - MIT (2011) [video]: https://youtube.com/watch?v=HB5TrK7A4pI https://youtube.com/watch?v=HB5TrK7A4pI [3] Google OR-Tools: https://developers.google.com/optimization https://developers.google.com/optimization [4] MiniZinc: https://www.minizinc.org/ https://www.minizinc.org/
- taylodl 1y agoUse the right tool for the right job!
- holden_nelson 1y agoI 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.
- Analemma_ 1y agoYes 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 to make sure they do actually know how to code. But just giving a constraint solver as an answer definitely wouldn't be bad.
- YetAnotherNick 1y agoGeneral 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.
- OutOfHere 1y agoOkay, but who says you need to use a simple constraint solver? There are various sophisticated constraint solvers that know how to optimize. At this point, job interviews are so far removed from actual relevance. Experience and aptitude still matter a lot, but too much experience at one employer can ground people in rigid and limiting ways of thinking and solving problems.
- NoahZuniga 1y agoO(10^6) = O(1)
- dekhn 1y agono, the "O" here is "on the order of", not Big O notation.
- harperlee 1y agoI believe NoahZuniga is perfectly aware of the intent and denouncing an abuse of (unneeded) notation.
- anonymars 1y agoWhat is "Big O" if not literally "order of"?
- NoahZuniga 1y agoThe O stands for "Ordnung", the German word for order. So it does literally mean that, except mathematicians think that the order of f(x)=1 is the same as the order of f(x)=10^6, because "clearly" f(x)=x gets way bigger than any constant function.
- _alternator_ 1y agoThis. 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.
- jojomodding 1y agoLeetCode problems typically are in P. The challenge is finding out why.
- mcmoor 1y agoYeah I think the trivial solution is always harder complexity and the main challenge is to lower it. Either from NP to P or from n*2 to n log n.
- zahlman 1y ago> or from n*2 to n log n. I guess you mean n^2 (or maybe n**2, if you're a fellow Pythonista). Many of these — especially the ones where the intended solution is characterized as using a "dynamic programming" technique — are reducible to n.
- Der_Einzige 1y agoIf someone solves a leetcode hard with a constraint solver and you don't hire them, you are an idiot. Do you know how few people in this world even know what a constraint solver is, let alone how to correctly define the problem into one? I used a constraint solver to solve a homework problem once in my CS degree 3rd year. My god just writing the damn constraints was a huge cognitive load!
- hackingonempty 1y agoI did this, wrote an Essence-prime program to generate Minion solver code for a simple instance of the knapsack problem, as part of a startups "solve one of these and get an interview" challenges. Because I had used those tools recently for a contract job (and wrote/presented a paper on invitation of the solver authors,) I thought it would be fun and didn't really want the job. Got an interview but every dev was like "why did you use a cannon to swat a fly?" and were clearly concerned that without strict supervision I would create baroque towers of garbage for them to clean up.
- skydhash 1y agoI would like to believe that most people capable of writing a solver would appreciate simple code. It's like when looking at ffmpeg or some physic engine code. You know you'll forget the details easily so you make sure everything is as simple as they can be.
- xenocratus 1y ago> If someone solves a leetcode hard with a constraint solver and you don't hire them, you are an idiot. I do hope you're exagerating here, but in case you aren't: this is an extremely simplistic view of what (software) engineers have to do, and thus what hiring managers should optimize for. I'd put "ability to work in a team" above "raw academic/reasoning ability" for the vast majority of engineering roles, any day. Not that the latter doesn't matter, of course, but it's by no means the one and only measure.
- Der_Einzige 1y ago
- gnfargbl 1y agoYou're right, but that just shows how fundamentally silly this interview approach is. In any real engineering situation I can solve 100% of these problems. That's because I can get a cup of coffee, read some papers, look in a textbook, go for a walk somewhere green and think hard about it... and yes, use tooling like a constraint solver. Or an LLM, which knows all these algorithms off by heart! In an interview, I could solve 0% of these problems, because my brain just doesn't work that way. Or at least, that's my expectation: I've never actually considered working somewhere that does leetcode interviews.
- koakuma-chan 1y agoI haven't been asked leetcode questions in a while and when I was asked, it was an easy level problem. I don't know where they ask hard leetcode problems, I also never solved a hard leetcode problem on my own.
- bradlys 1y agoI'm routinely asked LC Hard questions in interviews. Sometimes more than one in one 45 minute interview. That said, I interview in silicon valley and I'm a mixed race American. (extremely rare here) I think a lot of people just don't want me to pass the interview and will put up the highest bar they can. Mind you, I often still give optimal solutions to everything within good time constraints. But I've practiced 1000+ problems and done several hundred interviews.
- koakuma-chan 1y agoDo you interview at startups?
- bradlys 1y agoYes. I interview at everything from pre-seed to FAANG.
- ninja3925 1y ago
- lucideer 1y agoThis will be true in some interviews, but not in all. I'm generally against using leetcode in interviews, but wherever I've seen it used it's usually for one reason & one reason alone: known dysfunctional hiring processes. These are processes where the participants in the hiring process are aware of the dysfunction in their process but are either powerless or - more often - too disorganised to properly reform the process. Sometimes this is semi-technical director level staff leveraging HR to "standardise" interview techniques by asking the same questions across a wide range of teams within a large corp. Other times this is a small underresourced team cobbling together interview questions from online resources in a hurry, not having the cycles to write a tailored process for themselves. In these cases, you're very likely to be dealing with a technical interviewer who is not an advocate of leetcode interviewing & is attempting to "look around" the standardised interview scoring approach to identify innovative stand out candidates. In a lot of cases I'd hazard even displaying an interest in / some knowledge of solvers would count significantly in your favour.
- kccqzy 1y agoGreat 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 knowledge is great. It doesn't show any cleverness.
- theflyinghorse 1y agoThe point is to test whether or not you put in the time to sharpen common patterns and also to test your communication ability
- ebiester 1y agoSuper common patterns like dynamic programming?
- tomas789 1y agoYes. It is common on leetcode.
- theflyinghorse 1y agoYes. Common LC patterns such as 1D and 2D dynamic programming. I'm not defending leetcode style interviews, in fact I think they are actually bad, I'm simply stating their intent as observed by me. In my notes I have roughly 30 patterns to leetcode questions btw.
- corimaith 1y ago>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.
- hermannj314 1y agoMost interviews are based on the premise that if a diabetic can't synthesize their own insulin in their basement, they are somehow cheating at the game of life. If my wife's blood sugar is high, she takes insulin. If you need to solve a constraint problem, use a constraint solver. If your company doesn't make and sell constraint solving software, why do you need me to presume that software doesn't exist and invent it from scratch?
- joelthelion 1y agoIn defense of coding tests, most people who can't solve simple dynamic programming problems generally turn out to be pretty poor programmers IRL. At least that's been my experience. I'm sure there are exceptions.
- mepiethree 1y agoIt’s explicitly not testing if you can synthesize insulin in a crisis, it’s a general aptitude test for “if we tell you you need to cram this textbook on how to synthesize insulin by next week and then ask you how to do it on a call, can you coherently repeat that back to us?”
- carabiner 1y agoWhat?
- henry2023 1y agoIf you can figure out that a problem can be efficiently solved with a constraint solver then you can also write the two for loops and maybe some auxiliary recursive function to solve the given toy instance.
- faangguyindia 1y agoI avoided all this just by becoming a contractor, i ship solution, no me tests me for leetcode ability
- shutupnerd0002 1y ago[flagged]
- never_inline 1y ago> faangguyindia > contractor Do FAANG hire contractor in India?
- monknomo 1y agoI mean, yeah, they do.
- the_af 1y ago> 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.
- x187463 1y agoI 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.
- SJC_Hacker 1y agoThe bar is so high nowadays that simply being able to talk intelligentyly about the problem, ask clarifying questions, getting an inefficient solution and coding it up well does not pass muster. Even getting an efficient algorithm basically right, is no guarantee. In some cases there might be alternative solutions which have some tradeoffs, and you might have to come up with those, as well Miss a counterexample? Even if you get it after a single hint?. Fuck you, you're out. I can find someone who doesn't need the hint
- the_af 1y agoIt might be true in the general case, I haven't interviewed for a job for some years, so I may be out of touch. All I can say is that I do conduct interviews, and that I follow the above philosophy (at least for my round).
- Herring 1y agoReminder that the research says the interview process should match the day to day expectations as closely as possible, even to a trial day/week/month. All these brain teasers are low on signal, not to mention bad for women and minorities.
- ripped_britches 1y agoI would be blown away if a candidate solved it using DP and then said “but let me show you how to use a constraint solver”. Immediate hire.
- henry2023 1y ago+1
- cadamsdotcom 1y agoThis. Jump through their hoops first.
- thomasahle 1y agoInterview: > We can solve this with a constraint solver Ok, using your favorite constraint solver, please write a solution for this. > [half an hour later] Ok, now how would you solve it if there was more than 100 data points? E.g. 10^12?
- dataflow 1y agoMy 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 away critical details. Had they provided a handwritten solution from scratch with the same characteristics, it would've exhibited the same problems. This doesn't mean they can't provide a constraint solver solution, but if they do, they'd better be prepared to address the obvious follow-ups. If they're prepared to give an efficient solution afterward in the time left, then more power to them.
- Der_Einzige 1y ago[flagged]
- CamperBob2 1y agoThat's an en-dash, not an em-dash
- Der_Einzige 1y ago"It's not X, It's Y"
- graynk 1y agoI don't think someone with an account from 2012 and 20k karma would be posting LLM-generated comments. It also doesn't read as one. It doesn't even use the "it's not x it's y" formula, it contraposes things against each other. Like I just did.
- dataflow 1y ago> First of all, Nice ChatGPT response What the heck are you talking about? I didn't even visit ChatGPT today.
- qnleigh 1y agoI agree with the other comments here that using a constraint solver defeats the purpose of the interview. But this seems like a good case for learning how to use a constraint solver! Instead of spending hours coding a custom solution to a tricky problem, you could use a constraint solver at first and only write a custom solution if it turns out to be a bottleneck.
- jameslai 1y agoTerrible 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-technical-interviews/ https://socialengineering.fm/episodes/the-problem-with-techn...
- avgDev 1y agoMy 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 1y agoThis 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 1y agoI'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.
- cobbzilla 1y agoHere’s my empirical evidence based on several recent “coding session” interviews with a variety of software companies. Background: I have been developing software for over 30 years, I hold a few patents, I’ve had a handful of modestly successful exits. I kind of know a little bit about what I am doing. At this stage in my career, I am no longer interested in the super early stage startup lifestyle, I’m looking at IC/staff engineer type roles. The mature, state-of-the-art software companies do not give me leetcode problems to solve. They give me interesting & challenging problems that force me to both a) apply best practices of varying kinds and yet b) be creative in some aspects of the solution. And these problems are very amenable to “talking through” what I’m doing, how I’m approaching the solution, etc. Overall, I feel like they are effective and give the company a good sense of how I develop software as an engineer. I have yet to “fail” one of these. It is the smaller, less mature companies that give me stupid leetcode problems. These companies usually bluntly tell me their monolithic codebase (always in a not-statically-typed language), is a total mess and they are “working on domain boundaries”. I fail about 50% of these leetcode things because I don’t know the one “trick” to yield the right answer. As a seasoned developer, I often push back on the framing and tell them how I would do a better solution by changing one of the constraints, where the change would actually better match the real world problem they’re modeling. And they don’t seem to care at all. I wonder if they realize that their bullshit interviewing process has both a false positive and a false negative problem. The false negatives exclude folks like myself who could actually help to improve their codebase with proper, incremental refactorings. The false positives are the people who have memorized all the leetcode problems. They are hired and write more shitty monolithic hairball code. Their interviewing process reinforces the shittiness of their codebase. It’s a spiral they might never get out of. The next time I get one of these, I think I’m going to YOLO it, pull the ripcord early and politely tell them why they’re fucked.
- fern_ 1y agoThere is something to be said for being senior in a way where the people interviewing you are junior enough that they don't necessarily have the experience to necessarily "click" with the nuance that comes with said problems. That being said, from a stoicism point of view, the interview ends up becoming a meta-challenge on how you approach a problem that is not necessarily appropriately framed, and how you'd go about doing and/or gently correcting things as well. And if they're not able to appreciate it, then success! You have found that it is not the right organization for you. No need to burn the door down on the way out, just feel relief in that you dodged a bullet (hopefully).
- itissid 1y agoLong time ago, just for fun, I wrote a constraint solver problem that could figure out which high yield banks to put money into that were recommended on doctor of credit(https://www.doctorofcredit.com/high-interest-savings-to-get/ https://www.doctorofcredit.com/high-interest-savings-to-get/) based on <= `X` money and <= `Y` # of transactions on debit cards maximize the yield and other constraints(boolean and real valued) I played it for a while when interest rates were really low and used the thing for my own rainy day savings(I did get tired changing accounts all the time)
- toomuchtodo 1y agoRepo?
- cratermoon 1y agoI'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.
- meindnoch 1y agoAny problem can be solved by a sufficient number of nested for loops. (if you have enough time)
- scotty79 1y agoAnd a stack.
- 6510 1y agoOne level of nested for loop for each type of coin. (Run them until i*coin is larger than the input) Populate a 2d lookup array. $7,50 becomes arr[750] = [7,1,0,0,0,0] which represents [7x100,1x50,0x25,0x10,0x5,0x1] With each loop check if the array entry exists, if so check if that number of coins is larger. [7,1,0... is better than [7,0,2...] because 8 is a better solution than 9!
- binarymax 1y agoA loonnngggg time ago when I was green, and wasn't taught about constraint solving in my State University compsci program, I encountered the problem when trying to help a friend with his idea. He wanted to make an app to help sports club owners schedule players for the day based on a couple simple rules. I thought this was going to be easy, and failed after not realizing what I was up against. At the time I didn't even know what I didn't know. I often look back on that as a lesson of my own hubris. And it's helped me a lot when discussing estimates and timelines and expectations.
- 542458 1y agoThis might be a dumb question (as I'm not familiar with constraint solvers) but would a linear optimization approach be better? I've used linear optimization for scheduling in the past. The nice thing is that linear optimization handles rule conflicts well, because you just set weights on all your rules and the optimizer will find the "least bad" solution to the conflicts.
- j2kun 1y agoThis is what major sports leagues use for season scheduling (source: https://mathstodon.xyz/@j2kun/108975072813565989 https://mathstodon.xyz/@j2kun/108975072813565989)
- cerved 1y agoWell if your using MiniZinc you're free to use a CP solver, MIP solver, SAT solver, CP-SAT-LP solver. In general the model is roughly the same, even though some formulations work better for some solvers than others. But CP (and CP-SAT) solvers tend to do very well on scheduling problems
- ninkendo 1y ago> I thought this was going to be easy, and failed after not realizing what I was up against. At the time I didn't even know what I didn't know This reminds me of high school ~25 years ago when I just started learning TI-Basic on my calculator and was dabbling in VB6 on my PC, and I was flipping burgers at Steak n Shake as my part time job. The manager moaned about how hard it was to write the employee schedules out each week (taking into account requested days off, etc) and I thought “ooh, I know how to write software now, I’ll make a scheduling program!” I told the manager I bet I could do it. … it took a very short time for 16 year old me to realize writing scheduling software to solve for various constraints is pretty damned hard. I never brought it up after that.
- drob518 1y agoSAT, 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.
- LegionMammal978 1y agoAt least personally, I've been very underwhelmed by their performance when I've tried using them. Usually past a few dozen variables or so is when I start hitting unacceptable exponential runtimes, especially for problem instances that are unsatisfiable or barely-satisfiable. Maybe their optimizations are well-suited for knapsack problems and other classic OR stuff, but if your problem doesn't fit the mold, then it's very hit-or-miss.
- drob518 1y agoWell, they aren’t magic. You have to use them correctly and apply them to problems that match how they work. Proving something is unsat is worst case NP. These solvers don’t change that.
- LegionMammal978 1y agoOf course they aren't magic, but people keep talking about them as if they're perfectly robust and ready-to-use for any problem within their domain. In reality, unless you have lots of experience in how to "use them correctly" (which is not something I think can be taught by rote), you'd be better off restricting their use to precisely the OR/verification problems they're already popular for.
- drob518 1y agoHence my statement about education. All tools must be used correctly in their proper domain, that is true. Don’t try to drive screws with a hammer. But I'm curious what problems you tried them on and found them wanting and what your alternative was? I actually find that custom solutions work better for simple problems and that solvers do a lot better when the problem complexity grows. You’re better off solving the Zebra puzzle and its ilk with brute force code, not a solver, for instance.
- LordDragonfang 1y ago> This was a question in a different interview (which I thankfully passed): > Given a list of stock prices through the day, find maximum profit you can get by buying one stock and selling one stock later. It was funny to see this, because I give that question in our interviews. If someone suggested a constraint solver... I don't know what I'd have done before reading this post (since I had only vaguely even heard of a constraint solver), but after reading it... Yeah, I would still expect them to be able to produce a basic algorithm, but even if their solution was O(n^2) I would take it as a strong sign we should hire them, since I know there are several different use cases for our product that require generalized constraint solving (though I know it by other names) and having a diverse toolset on hand is more important in our domain than writing always-optimal code.
- tracker1 1y agoSomething that works poorly is often better than something that doesn't work in an instant. This is what I have to tell myself every time I step into a massive, excessively complex mess of a codebase. Many business rules aren't clearly defined ahead of time in a way that always translates well to the code and starting over is a mistake more often than not imo. Update... refactor... update... break off... etc. A lot of times, I'm looking at something where the tooling is 8+ years old, and the first order of business should be to get it working on a current and fully patched version of whatever is in place... replacing libraries that are no longer supported, etc. From there, refactor what you can, break off what makes sense into something new, refactor again. This process, in my experience, has been far more successful than ground up, new versions. I say this while actively working on a "new" version of a software. New version being web based, "old" version being a winforms VB.Net app from over a decade ago. Old version has bespoke auth, new verion will rely on Azure Entra... Sometimes, starting over is the answer, but definitely not always.
- atilimcetin 1y agoWhenever constraint programming languages come up, you can’t miss mentioning Håkan Kjellerstrand. He’s put together an amazing collection of problems and examples—including plenty for MiniZinc—on his site: https://www.hakank.org/minizinc/ https://www.hakank.org/minizinc/
- cerved 1y agoNot only has he made a great website, he's also a super nice guy
- tracker1 1y agoMy 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 question/assignment. Because of this, I've just started rejecting outright leetcode/ai interview steps... I'll do homework, shared screen, 1:1, etc, but won't do the above. I tend to fail them about half the time. It only feels worse in instances, where I wouldn't even mind the studying on leetcode types sites if they actually had decent explainers for the questions and working answers when going through them. I know this kind of defeats the challenge aspect, but learning is about 10x harder without it. It's not a matter of skill, it's just my ability to take in certain types of problems doesn't work well. Without any chance of additional info/questions it's literally a setup to fail. edit: I'm mostly referring to the use of AI/Automated leetcode type questions as a pre-interview screening. If you haven't seen this type of thing, good for you. I've seen too much of it. I'm fine with relatively hard questions in an actual interview with a real, live person you can talk to and ask clarifying questions.
- lawlessone 1y agoThe one's i've gotten have all seemed more like tests of my puzzle solving skills than coding. The worst ones i've had though had extra problems though: one i was only told about when i joined the interview and that they would be watching live. One where they wanted me streaming my face the whole time (maybe some people people are fine with that) And one that would count it against me if i tabbed to another page. So no documentation because they assume i'm just googling it. Still it's mostly on me to prepare and expect this stuff now.
- another_twist 1y agoYou can make up API calls which you can say you'd implement later. As long as these are not tricky blocks, you'll be fine.
- swiftcoder 1y ago> Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Maybe it's my graphics programmer brain firing on all cylinders, but isn't this just a linear scan, maintaining a list of open rectangles?
- deleted 1y ago[deleted]
- mattmcal 1y agoYes, you just need to maintain a stack of rectangles ordered from lowest to highest. You only ever have to push and pop the top of the stack, so the runtime is O(n).
- garrettgarcia 1y ago"Follow-up question since you solved that so quickly: implement a constraint solver."
- krosaen 1y agoI find this post interesting independent of the question of whether leetcode problems are a good tool for interviews. It's: here are some kinds or problems constraint solvers are useful for. I can imagine a similar post about non-linear least squared solvers like ceres.
- smj-edison 1y agoYeah, especially for learning how to use a solver! > Most constraint solving examples online are puzzles, like Sudoku or "SEND + MORE = MONEY". Solving leetcode problems would be a more interesting demonstration. He's exactly right about what tutorials are out there for constraint programming (I've messed around with it before, and it was pretty much Sudoku). Having a large body of existing problems to practice against is great.
- guluarte 1y agoMost 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.
- CamperBob2 1y agoI 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.
- Planktonne 1y agoThe 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 1y agoThere 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 1y ago> 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).
- deleted 1y ago[deleted]
- CamperBob2 1y ago
- Gunax 1y agoInternally, 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.
- cerved 1y agoNo. 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
- non_aligned 1y agoI think LeetCode tests two things. First, your willingness to grind to pass an exam, which is actually a good proxy for some qualities you need to thrive in a corporate environment: work is often grungy and you need to push through without getting distracted or discouraged. Second, it's a covert test for culture fit. Are you young (and thus still OK with grinding for tests)? Are you following industry trends? Are you in tune with the Silicon Valley culture? For the most part, a terrible thing to test, but also something that a lot of "young and dynamic" companies want to select for without saying so publicly. An AI startup doesn't want people who have family life and want to take 6 weeks off in the summer. You can't put that in a job req, but you can come up with a test regime that drives such people away. It has very little to do with testing the skills you need for the job, because quite frankly, probably fewer than 1% of the SWE workforce is solving theoretical CS problems for a living. Even if that's you, that task is more about knowing where to look for answers or what experiments to try, rather than being able to rattle off some obscure algorithm.
- j2kun 1y ago> 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.
- shoo 1y agoAgreed - 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 <discovery of additional requirements>". 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.
- bradlys 1y agoEveryone misunderstands what LC focuses on. It focuses on - did you grind like everyone else that did to get into this company/region/tech? It allows for people who didn't go to the most specific schools (e.g. Cal, Stanford, etc.) to still get into silicon valley companies if they show they are willing to fit the mold. It's about showing you are a conformist and are willing to work very hard to do something that you won't realistically use much in your day to day job. It's about signaling. That's all it is. At least it's not finance where it's all dictated by if you were born into the right family that got you into the elite boarding schools for high school, etc. I would've never made it into finance unless I did a math phd and became a quant.
- whatever1 1y agoI tried a couple of times long time ago to solve them with cp/integer programming. The interviewers were clueless so after 10 minutes of trying to explain to them I quit and fell back to just writing the freaking algo they were expecting to see.
- zzzeek 1y agoI'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 1y agoIt'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 1y ago> 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.
- notemap 1y agohttps://codeforces.com/problemset/problem/1889/D https://codeforces.com/problemset/problem/1889/D
- techlatest_net 1y ago[dead]
- RomanPushkin 1y ago- Constraint solvers? That's a nice concept, I heard about this once. However, for the purposes of the interview, let's just write some Python code, I wanna see your way of thinking... (I think it's almost impossible to convince your interviewer into constraint solvers, while the concept itself is great)
- aaronblohowiak 1y agoimport z3
- cerved 1y agofrom ortools.sat.python import cp_model
- henry2023 1y agoHave you ever tried or this is your assumption of what the interviewer would say.
- gnarlouse 1y agoBeen 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 expiration, models your pantry, estimates grocery prices, meets your nutritional goals. Constraint solvers are black magic.
- cerved 1y agoWhich solver do you use?
- gnarlouse 1y agoGoogle ORTools’ CpSolver, with IntervalVars for the calendar portion.
- cerved 1y agoPresumably 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
- gnarlouse 1y agoWow 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.
- phendrenad2 1y agoSo LeetCode has fallen into the same trap as ProjectEuler (anyone remember that?)
- afro88 1y agoA little off topic, but I don't know much about greedy algorithms or dynamic programming. I got curious. This conversation was very insightful and now it's very clear in my mind: https://chatgpt.com/share/68c46d0b-8858-8004-aa03-f7ce321988da https://chatgpt.com/share/68c46d0b-8858-8004-aa03-f7ce321988...
- tbmbob 1y ago> Now if I actually brought these questions to an interview the interviewee could ruin my day by asking "what's the runtime complexity?" This completely undermines the author's main point. Constraint solvers don't solve hard leetcode problems if they can't solve large instances quickly enough. Many hard leetcode problems can be solved fairly simply with more lax runtime requirements -- coming up with an efficient solution is a large part of the challenge.
- floatrock 1y ago> coming up with an efficient solution is a large part of the challenge More of my work tends to be "rapidly adopting solution to additional and changing requirements" than "come up with most efficient solution", so why are we interviewing for something where in practice we just throw a couple extra instances at it? (Your specific job role may vary, of course, but I usually just increase the scaling factor) Author's point is that coming up with the most efficient solution might not actually be a good measure of your real-world performance. And that's been a longrunning critique of leetcode, of course. However, this is a neat framing where you can still use the same problems but give solutions that perform better when measured by "how adaptable is this to new requirements?"
- chipsrafferty 1y agoWould love to know how to actually assess the runtime complexity of constraint solvers like this.
- wolvesechoes 1y agoWhoever agrees to do LC problems during interview has zero dignity.
- BhavdeepSethi 1y agoIt's insane how many of these new "AI" companies don't let you use AI or even your own IDE for coding interviews. And most questions from such companies are LC type problems so they know any AI tool can one shot it.
- IshKebab 1y agoWhy is that insane? Seems logical to me.
- BhavdeepSethi 1y agoDefinitely not insane. Ironic is the correct term. The field is evolving, a lot of these companies talk about replacing outdated practices using AI. Asking software engineers to not use their own tools to solve problems falls under the same bucket.
- henry2023 1y agoI discourage it but I let them use it and then give them a specific problem that I know your average Claude 4 or GPT 5 will just not get it right. Actually people perform worse in an interview using AI because they spend time trying to understand what the tool is proposing and then time to figure out why that doesn’t work.
- BhavdeepSethi 1y agoMy experience has been quite different. With Cursor/Claude code, I've ended up writing full fledge solutions (running cli/web servers with loggers and unit tests for each functionality). We're talking crawlers, cab booking service like uber, search engines with seed data. All within the hour.
- cerved 1y agoMiniZinc is a really great modeling language for constraint programming. Back in August I gave a talk at NordConstNet25 on how we used it to build a product configurator in what's (probably) the worlds largest MiniZinc model https://pierre-flener.github.io/research/NordConsNet/NordConsNet25/WorldsLargestMiniZincModel.pdf https://pierre-flener.github.io/research/NordConsNet/NordCon...
- aeternum 1y agoYou: Oh I know, I can use a constraint solver for this problem! Interviewer: You can't use a constraint solver
- tannhaeuser 1y agoHere'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.html https://quantumprolog.sgml.net/browser-demo/browser-demo.htm... [2]: https://news.ycombinator.com/item?id=45205030 https://news.ycombinator.com/item?id=45205030
- 6gvONxR4sf7o 1y agoOf course, the challenge is that the next question after solving a leetcode problem is often to explain and optimize the performance characteristics, which in prolog can get stupidly hairy.
- skydhash 1y agoI've actually used pseudo-prolog to explain how to solve leetcode problems to a friend. Write the facts, then write the constraints, and then state your problem. Close to the last part, they've already understood how to solve it, or at least how to write the program that can answer the question.
- amai 1y agoThe documentation for Googles OR tools comes with many interesting examples of constraint problems, e.g. https://developers.google.com/optimization/lp/stigler_diet https://developers.google.com/optimization/lp/stigler_diet
- SCLeo 1y agoDoes using a constraint solver actually solve the question under the time ... constraints? If not, how can you claim you have solved the problem?
- scotty79 1y agoAll problems cited are about testing if you can write if's, loops and recursion (or a stack/queue). They aren't testing if you can write a solver. They are testing if you can use bricks that solvers are built out of because other software when it gets interesting is built out of the same stuff.
- Jun8 1y agoAn 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 1y agoIsn't it trivially [1]?
- zahlman 1y agoPerhaps what is meant is "maximize the difference between the optimal result and the one calculated by the naive greedy algorithm".
- Jun8 1y agoThanks 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?
- RagnarD 1y agoNice post, I wasn't aware that there were so many dedicated constraint solving systems.
- theendisney 1y agocoins = [100,50,25,10,5,1] change = 1234; result = [0,0,0,0,0,0]; for(i=0:i<coins.length;i++){ while(change>coins[i]){ result[i]++; change-=coins[i]; } } //[12,0,1,1,4] Coudnt help myself sorry
- efortis 1y agome neither function coin_change(change) { const coins = [25, 10, 5, 1] for (const coin of coins) { const n = change / coin | 0 change -= n * coin console.log(coin, n) } } coin_change(25+10+5+1)
- theendisney 1y agoOr.... [100,500,25,10,5,1].map(coin=>{ n = change / coin | 0 change %= coin; return n }) Coding on a Phone is hell
- 6510 1y agochange = 12345; console.log( [100,500,25,10,5,1].map( coin=>[change/coin|0,change%=coin][0] ) )
- gnatman 1y ago“Many hard problems are, to me, quite easy”
- deepsun 1y agoAs an interviewer, I gave one pretty simple task (people solved it in as little as 8 minutes), wasn't using any real CS, even though I'm good at it. The reason was that aboint 70% of candidates couldn't write a simple loop -- to filter those out. The actual solution didn't matter much, I gave a binary decision. The actual conversation matters more.
- Tade0 1y agoThis. Main point of giving candidates CS problems was always to weed out those who couldn't program at all, but somehow were still in the industry. I worked with such people - it's unpleasant. Somehow someone figured that giving harder problems should result in better candidates. Personally, despite having passed most of the tests I've been subjected to, I don't see the connection.
- jcul 1y agoI've never used constraint solvers, seems like black magic. Need to fill that gap in my knowledge. But how do they work, what is the complexity of the solution, for example for the stock prices, is it O(n^2)?
- coarise 1y agoGeneral constraint satisfaction problem is NP-hard.
- FilosofumRex 1y agoSAT & 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
- treenode 1y agoIt would have been worthwhile if this article had briefly touched upon how the constraint solvers are implemented, rather than avoiding this altogether
- torginus 1y agoVery 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 python library that carries 30MB of native dependencies around. These solutions are often lacking in many ways, since mentally offloading some of the work means you don't have to understand the problem in depth or how the designated tool solves it, which can lead to nasty surprised in production. We see this everywhere - people pulling in questionable npm packages to save themselves 30 mins of thinking or 20 mins of reading docs - people convinced that you do need that huge 3D framework that comes with an editor to make a WebGL widget on your landing page etc. You are more willing to accept bloat of others, just because they pulled in Electron, because they were too afraid to learn how native UI works. People need to be more curious, and strive to be more knowledgeable.
- jvanderbot 1y agoWait 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?
- mmis1000 1y agoYou 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.
- komali2 1y agoWhat, 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.
- jongjong 1y agoMy 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.
- liqilin1567 1y ago[flagged]
- MichaelZuo 1y agoIt seems like a moot point since there are already too many people who can clear leetcode hard than there are available positions that require it. It’s like scoring over 2 standard deviations on an IQ test, great, but by definition millions of people can do that. Edit: I’ve heard HFT firms are now moving to doing it on paper in person to prevent any kind of cheating for their interviews, which would make it a better signal.
- liqilin1567 1y agoYes,that is better. From my own experience, LeetCode does indeed enhance one's logical thinking and coding skills. I believe this is the reason why FAG has always tested algorithm and data structure skills in interviews over the years.
- supriyo-biswas 1y agoI understand that this is an advertisement for your product, but please do not do this here. Thank you.
- coherentpony 1y agoHonestly, I didn’t realise it was an advert until you told me it was.
- liqilin1567 1y agoYou're right to point that out, thanks for keeping things honest. My intention was simply to offer a helpful TL;DR for a very long thread, as it's a feature of a project I'm working on (mentioned in my profile). I'm trying to contribute value without being spammy. If this crosses a line for the community, I'm happy to listen and adjust.
- 1y ago
- Stevvo 1y agoThe first example doesn't make a lot of sense, because coins only ever exist in "well-behaved" denominations. There is no currency with a nine unit coin.
- wvlia5 1y agoGröbner basis is an interesting way to solve the 1st problem.