6 ms·
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 fo
by holden_nelson 1y ago
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.
- 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.
- dekhn 1y agoIn physics "order of" means "approximately" using something like a taylor series, which typically start with a constant, then move to higher polynomial terms which add smaller and smaller corrections. Similar, but different, I think...
- nextos 1y agoFWIW, the OP's problem is not linear. It's an integer programming problem. A trick if you can't do a custom algorithm and using a library is not allowed during interview could be to be ready to roll your own DPLL-based solver (can be done in 30 LOC). Less elegant, but it's a one-size-fits-all solution.
- PartiallyTyped 1y agoIt’d be a positive in my book if they used a constraint solver.
- qnleigh 1y agoYes, especially if the interviewee said something like 'this may not be asymptomatically optimal, but if it's not a known bottleneck, then I might start with constraint solver to get something working quickly and then profile later.' Especially if it's a case where even the brute-force solution is tricky. Otherwise penalizing interviewees for suggesting quick-and-dirty solutions reinforces bad habits. "Premature optimization is the root of all evil," after all.
- bluGill 1y agoUsing a bad algorithm when a good algorithm that is known to exist is premature pessimization and should be avoided. There is some debate about what premature optimization is, but I consider it about micro optimizations that often are doing things a modern compiler will do for you better than you can. All too often such attempts result in unreadable code that is slower because the optimizer would have done something different but now it cannot. Premature optimization is done without a profiler - if you have a profile of your code and can show a change really makes a difference then it isn't premature. On the other hand job interviews imply time pressure. If someone isn't 100% sure how to implement the optimization algorithm without looking it up brute force is faster and should be chosen then. In the real world if I'm asked to do something I can spend days researching algorithms at times (though the vast majority of the time what I need is already in my language's standard library)
- chipsrafferty 1y agoIBO premature optimization is normally one of two things: 1. Any optimization in a typical web development file where the process is not expected to be particularly complex. Usually a good developer will not write something very inefficient and usually bottlenecks come from other areas 2. Doing stuff like replacing a forEach with a for loop to be 0.5% faster
- LPisGood 1y agoConstraint solvers (or MILP solvers) while not asymptotically optimal are often as fast or faster than other methods.
- 1y ago
- _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.