Medium

Google-styleAmazon-style

Minimum Coins to Reach an Amount DSA Interview

Given a set of coin denominations and a target amount, find the minimum number of coins (with unlimited supply of each denomination) needed to make exactly that amount, or report it is impossible.

Mock Interview with AI

1. Problem Statement

You are given a list of coin denominations and a target amount. Each denomination has unlimited supply. Find the minimum number of coins needed to make exactly the target amount, or -1 if it cannot be made.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify coin supply, denomination properties, and impossible-case behavior before coding.
✓Explain a naive recursive baseline and improve to bottom-up dynamic programming.
✓Think aloud while implementing careful DP state transitions.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies that coin supply is unlimited, confirms denominations are positive integers, and asks what to return for an amount of zero or when no combination works.
✓Confirms whether denominations can repeat in the input list.

Staff-level signals

◆Asks about the expected magnitude of the target amount to gauge the DP table size.

Common red flags

×Codes immediately while assuming a greedy largest-coin-first approach always works without confirming or justifying it.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive recursive baseline that tries every denomination at every remaining amount without caching, identifies the exponential re-computation bottleneck, and improves to bottom-up dynamic programming over amounts 0 through the target.
✓Explains why a greedy largest-coin-first strategy can fail for arbitrary denomination sets and why DP is the safe conventional choice.

Staff-level signals

◆Discusses when greedy would actually be correct (e.g., canonical coin systems) and why that assumption should not be relied on generally.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Insists greedy is always optimal without acknowledging counterexamples when prompted.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the DP recurrence and table-filling order while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct bottom-up DP where dp[amount] is the minimum coins to make that amount, initialized appropriately (dp[0] = 0, unreachable amounts marked with a sentinel) and updated by trying each denomination.
✓Handles amount zero, an unreachable amount, denominations larger than the amount, and a single denomination.
✓Provides a convincing invariant argument for why the recurrence produces the true minimum.

Common red flags

×Uses a greedy approach without justification and produces a wrong answer on a denomination set where greedy fails.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with a clear DP array, sentinel value for unreachable amounts, and a well-structured update loop.

Common red flags

×Contains off-by-one errors in the DP indices or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, showing DP table values as they fill in.
✓Covers amount zero, an unreachable amount, and a case where greedy would give a suboptimal answer.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States time complexity proportional to amount times number of denominations and auxiliary space proportional to the amount, comparing it with the exponential recursive baseline.

Staff-level signals

◆Discusses memory implications for a very large target amount and whether a rolling structure could help.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Naive recursion without memoization recomputes the same subproblems repeatedly, costing exponential time in the worst case.
Top-down memoized recursion and bottom-up tabulation both achieve pseudo-polynomial time proportional to amount times denominations, with bottom-up typically preferred for iterative clarity.
A greedy largest-coin-first approach is fast but incorrect for general denomination sets, only working for specific canonical coin systems.

Practice follow-up questions

1.Coding follow-up: modify the solution to also return one valid combination of coins achieving the minimum count, not just the count itself.
2.Verbal extension: how would the approach change if you needed the minimum coins for many different target amounts against the same fixed denomination set?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Dynamic ProgrammingArraysComplexity Analysis