Comment by holden_nelson 13 hours 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.
I was told to use ANY language in an interview. I asked them if they were sure, so I solved it with J. They were not too pleased and asked me if I could use another language, so I did prolog and we moved on to the next question. Then the idiot had the audacity to say I should not use "J and Prolog" but any common known language. I asked if assembly was fine, and they said no. Perhaps python or javascript. I did the rest in python, needless to say I didn't get the job. :-)
Reminds me of https://aphyr.com/posts/340-reversing-the-technical-intervie... (and the follow-ups to it)
I find it hilarious when people brag about stupid shit like that. Congrats on sabotaging your own interview process I guess??
Use the right tool for the job. Thats engineering.
Instead you insist we should solve a nieche problem with a ill suited tool, while inventing a costume solution when a standard solution exist.
They dodged a bullet. It would have been hell working there.
Why would you ever want to work somewhere that clearly employs such unqualified individuals? And not only that, but allows those individuals to be the face of their company to prospective hires?
A company's interview process tells you a lot about how the company thinks and operates. This was was surely a dumpster fire.
Sabotaging? The candidate learned that their interviewers, and probably the company as a whole, isn't curious about languages or stuff that is outside of their wheelhouse.
What if the interviewers decided to ask the candidate about their language choice and trade-offs between different languages? Wouldn't that actually give them more signals into the skill of the engineer, rather than just blindly following their script?
I 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.
The purpose of coding questions should be a problem that you can solve in about 20 minutes, then they ask another, and then you get 20 minutes to either finish or talk about other things. If you ask questions where either someone knows the trick and they pass, or they don't and fail you don't learn much. You need to watch the person write code to see if they are reasonable about it.
I interviewed at an investment bank in London and they asked me pretty hard questions. One was to implement some multithreaded producer consumer thing in C++. I can't remember the details but it was... well you know how writing multithreaded C++ is. I was allowed to look up references at least. Took me maybe 20 minutes and the whole time the interviewer was just sitting on his phone while I wrote it.
Weird experience. Didn't get that job (probably for the best tbf).
If you wrote an MPSC queue (standard question) with multithreaded demo in 20 minutes in C++ you’re pretty hot shit, mate. Their loss. It’s not that it’s hard. But that speed without error is just really good. C++ is particularly unforgiving too.
I was once asked fizz buzz in an interview and it made me sad that some people don't pass it.
I'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.
This is not how it works. The interviewer knows 1-2 problems and there is no time for profiling since they are rushing through their day, probably focused on their day to day work. You are the least of their concern, believe me.
Source: we am a hiring manager.
More exactly, you can't invent algorithms on a spot which took who knows how many years for others to invent. I.e. the question ends up being more if you know about a specific algorithm, which results in "invent it if you don't know about it". It's absolutely silly to test for ability to invent one on the spot, so it's a pretty pointless interview question really.
This. 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.
LeetCode problems typically are in P. The challenge is finding out why.
This 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.
If 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!
I 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.
I 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.
> 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.
> why do you do leetcode hard interviews?
I don't. I do easy code interviews because there are people who work great on a team and know enough buzzwords to sound like they know how to write code, but cannot. Something that isn't hard to solve in about 20 minutes (I can solve in 5 - but I've seen a solution several times and so don't have to think about the solution), but is different enough that you haven't memorized the solution. If you can't solve an easy problem then you can't code.
> In this hypothetical, why do you do leetcode hard interviews?
I thought I already answered that:
>> Not that the latter doesn't matter, of course, but it's by no means the one and only measure.
OK, but obviously this presupposes a job where the hiring process is focused on leetcode.
Hey I'm with you 100% about the idea of code-interviews/leetcode being a problem and the importance of culture-fit and ability to work on a team.
I should have said "if you deemed this a fail on the code interview, you are an idiot".
I've won a couple hackathons with just CP-SAT & Linear Programming which led to my first jobs. I'm surprised not more people know/use it. Very inefficient compared to the "correct" answer but the development speed is much faster.
> If someone solves a leetcode hard with a constraint solver and you don't hire them, you are an idiot
Sometimes you just don't want someone that takes these shortcuts. I think being able to solve the problem without a constraint solver is much more impressive
This - the only downside to a constraint solver is it's usually slower. If you want them to write a fast algorithm, then specify that. Have an actual metric for it, if they can pass it with the declarative language, then great. If not, they should have written a more complicated algorithm.
Yes 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.
Yes, 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.
Using 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)
IBO 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
It’d be a positive in my book if they used a constraint solver.
General 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.
FWIW, 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.
Okay, 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.
You'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.