Comment by Analemma_

Comment by Analemma_ 13 hours ago

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.

qnleigh 12 hours ago

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.

Reply View 3 replies

bluGill 11 hours ago

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)

Reply View | 2 replies
- chipsrafferty 7 hours ago
  
  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
  
  Reply View | 0 replies
- LPisGood 6 hours ago
  
  Constraint solvers (or MILP solvers) while not asymptotically optimal are often as fast or faster than other methods.
  
  Reply View | 0 replies

PartiallyTyped 13 hours ago

It’d be a positive in my book if they used a constraint solver.

Reply View 0 replies

YetAnotherNick 13 hours ago

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.

Reply View 10 replies

nextos 12 hours ago

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.

Reply View | 2 replies
- kragen 7 hours ago
  
  You can implement DPLL in 30 lines of code? Not for SMT, I assume.
  
  Reply View | 1 reply
  
  nextos 2 hours ago
  
  You'd need a fancy encoding for SAT to use a small DPLL implementation.
  Otherwise, customize DPLL for this particular problem.
  
  Reply View | 0 replies
OutOfHere 13 hours ago

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.

Reply View | 0 replies
NoahZuniga 13 hours ago

O(10^6) = O(1)

Reply View | 5 replies
- dekhn 13 hours ago
  
  no, the "O" here is "on the order of", not Big O notation.
  
  Reply View | 4 replies
  
  harperlee 12 hours ago
  
  I believe NoahZuniga is perfectly aware of the intent and denouncing an abuse of (unneeded) notation.
  
  Reply View | 0 replies
  
  anonymars 11 hours ago
  
  What is "Big O" if not literally "order of"?
  
  Reply View | 2 replies