Comment by YetAnotherNick
21 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.
21 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.
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.
You can implement DPLL in 30 lines of code? Not for SMT, I assume.
You'd need a fancy encoding for SAT to use a small DPLL implementation.
Otherwise, customize DPLL for this particular problem.
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.
O(10^6) = O(1)
no, the "O" here is "on the order of", not Big O notation.
I believe NoahZuniga is perfectly aware of the intent and denouncing an abuse of (unneeded) notation.
What is "Big O" if not literally "order of"?
2 replies →