Denominations are fixed but payout amounts reach 10^9 - do you ship largest-first or the exact method?
answer
- Which input is big, and which is fixed?
- Cost tracks the value, not the digit count
- Do the expensive reasoning once, offline
- Canonical sets make largest-first exact
- Who chose the denominations in the first place?
basics
~10 sThe exact method's cost scales with the amount's numeric value, so it is unusable at 10^9. Prove the fixed denomination set greedy-optimal offline, ship largest-first, and guard that proof with an automated check.
solid answer
~50 sAt 10^9 the exact per-amount method is not on the table: its work grows with the numeric value of the amount, not with the number of digits, so it is pseudo-polynomial and needs on the order of a billion steps and comparable memory per request. Since the denomination set is fixed and small, I would move the hard work offline: test once whether that set is greedy-optimal - a finite check, because the smallest counterexample is bounded by the largest denominations - and if it is, ship largest-first, which is a handful of integer divisions per request. The organisational half matters more: that proof is an assumption about a value product owns, so I encode it as a test that reruns whenever the set changes, not as a comment. If the set is not greedy-optimal, the cheapest fix is usually to negotiate the set rather than build a heavier algorithm.
go deeper
Take away the core fact: a method costing amount times denominations is fast for small amounts and hopeless for huge ones, because its work follows the number's value rather than its digit count.
Explain why that is called pseudo-polynomial and what makes the denomination set different from the amount - one is small and fixed, so expensive checks over it can run once offline.
Show the design move: certify the fixed configuration offline, keep the per-request path to a few integer operations, validate input ranges at the boundary, and emit the coin count so a distribution shift is visible.
Own two things the code cannot: that a proof about configuration must be enforced by the build, and that the denomination set is a product input you can renegotiate. Be ready to price an exact method's maintenance burden against a bounded-suboptimality answer.
## Why the exact method is not merely slow The exact minimum-coin computation over an amount costs on the order of the amount multiplied by the number of denominations, in both time and memory. That is *pseudo-polynomial*: polynomial in the numeric **value** of the input, exponential in its **encoding length**. The number 1,000,000,000 is ten characters long; the computation it triggers is a billion steps. Doubling the digit count multiplies the work by ten, not by two. This is why "it is polynomial" is a misleading defence of such a method - it is polynomial in the wrong measure, and the wrong measure is the one that grows in production. So at 10^9 the question is not tuning. It is which of a small set of structurally different answers you are willing to defend. ## Option 1: make the cheap algorithm provably correct The denomination set is fixed and small; only the amount is large. That asymmetry is the lever. Largest-first change-making is optimal for exactly those denomination sets that are canonical, and canonicity is decidable: if a counterexample exists at all, the smallest one is bounded in terms of the two largest denominations, so a finite offline search settles the question, and polynomial-time tests are known. So run the expensive reasoning once, offline, over the set - not per request over the amount. If the set passes, largest-first is exact, runs in a handful of integer divisions, uses constant memory, and is trivially reviewable. This is the answer to reach for, and it is worth saying explicitly why: you have not approximated anything and you have not weakened the guarantee. You have moved the cost from a per-request axis that scales badly to a per-configuration axis that barely scales at all. ## Option 2: change the denomination set If the set is not canonical, the instinct is to build a bigger algorithm. Usually the better move is to ask who chose the numbers. Denomination sets for payouts, vouchers, chip stacks or packaging units are product decisions, and a set that is a few units different is often equally acceptable to the business and canonical. Trading an unusual denomination for a neighbouring one can convert an intractable per-request computation into a provable division - the cheapest engineering win available, and one that is invisible if you treat the input as fixed. This is the part of the answer that reads as principal rather than senior: recognising that a constraint labelled "given" in the problem statement is owned by a person you can talk to. ## Option 3: bound the exact work, and price the proof If the set must stay non-canonical, the remaining honest routes all carry a proof obligation. You might precompute exact answers up to some threshold and argue that above that threshold one denomination is always safe to take, which would cap the table at the threshold. That argument is real work, it must be established for the specific set, and it must be re-established every time the set changes. Weigh that against what the organisation can carry. A structure whose correctness depends on a bound only one engineer understands is a liability that outlives that engineer. If the amounts are large but the tolerance is loose, a documented bounded-suboptimality answer may be the better product decision than an exact method nobody can maintain. If the tolerance is not loose - payouts usually are not - then the cost of the proof is the cost of the requirement, and that is a conversation to have explicitly rather than to absorb silently. ## What not to say - **"Just cache it."** With 10^9 possible amounts the cache is the table you were avoiding; only a heavily skewed amount distribution rescues this, and that is a claim requiring data. - **"Add memory."** A billion-entry structure per request is not a provisioning problem. - **"Counterexamples are rare, ship greedy."** Rare is not absent, and for money the failure is a silently wrong payout that nothing alerts on. - **"Greedy is an approximation of the exact method."** On a canonical set it is not an approximation at all; on a non-canonical set it is not a controlled approximation either, since plain largest-first carries no error bound. ## Engineering details that belong in the answer At 10^9 amounts, coin counts and running totals need integer widths chosen deliberately; a total accumulated across many payouts overflows a 32-bit accumulator long before the business notices. Validate the amount range at the boundary rather than trusting callers. And make the fast path observable: emit the coin count so that a distribution shift - counts creeping up after a denomination change - is visible without anyone re-deriving the proof. ## The shape of a strong answer Name the pseudo-polynomial trap; separate the fixed small input (the denominations) from the huge one (the amount); move the reasoning offline onto the fixed one; make the resulting assumption executable in the build; and treat the denomination set as a negotiable product input rather than an immovable constraint. That sequence is the judgment being tested, and none of its steps is a data-structure choice.
- You proved the denomination set greedy-optimal. How do you stop that proof from quietly going stale?Make it executable. Put the canonicity check in the build as a test over the configured denomination set, so any change to that set fails the pipeline until someone re-establishes the property. A proof recorded in a design document or a code comment is an assumption nobody re-validates; a proof recorded as a test is one the system re-validates on every change, including one made by a product owner editing configuration.
- Product insists on a denomination set that is not greedy-optimal. What do you propose?First, quantify: run the offline search, find the smallest failing amounts and how far off greedy is there, and check whether those amounts occur in real traffic. Often the failures cluster in a range the product never pays out, which turns this into a validated input constraint. If they do occur, the choices are an exact method with a proven bound on the table size, or an explicitly accepted suboptimality - and that acceptance is product's decision to make with the numbers in front of them, not an engineering shortcut.
- Why is caching results per amount a weak answer here?Because the amount space has 10^9 members, so a cache that covers it is the capacity-scaled table under another name. It only helps if real amounts concentrate on a small set of values, and that is a claim to verify against traffic before designing around it. Even then you need a correct answer for the first request at each new amount, which is the original problem unchanged.
Rather than re-measuring a doorway for every delivery, you certify the doorway once and then check only that nobody has rebuilt it.
saying these in an interview costs you the question
- Calls the exact method polynomial and therefore fine
- Proposes caching across a billion distinct amounts
- Ships greedy because counterexamples seem rare
- Treats the denomination set as immovable
- Records the correctness proof only as a comment
- Ignores integer width for totals at 10^9 scale