FWIW, the OP's problem is not linear. It's an integer programming problem given that coins are discrete.

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.

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"?

In 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...

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.

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.