Coin Change
Medium · Phone screen · Onsite · Full-time
Classic DP problem. Given coin denominations and a target amount, find the fewest coins to make it. I built up a table from 0 to the target, trying each coin at each step. The interviewer asked about the difference between the top-down memo approach and bottom-up, and whether the greedy approach would always work.
