Comment by 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.
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.
The 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.
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.