Salesforce·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Salesforce SWE interview that came down to a classic DP problem. Nothing too surprising but the details matter more than you'd think.

Questions Asked (1)

Given an array of distinct coin denominations and a target amount, return the minimum number of coins needed to reach that amount. Return -1 if it's not possible. Coins can be reused.

Algorithms & Data Structures

Author's notes

The core insight is framing dp[i] around the amount, not some index into the coins array.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use dynamic programming to compute the minimum coins for each amount from 0 to target, building up from smaller subproblems. For each amount, consider each coin and take the minimum of 1 + dp[amount - coin] if that subproblem is solvable. Return dp[target] or -1 if unreachable.

Pro tip: Mention that this is the classic unbounded knapsack/coin change problem, and that BFS on the amount graph can also solve it in O(target * number of coins) time. Also note that if the coin system is canonical (like US coins), a greedy approach works, but it's not guaranteed for arbitrary denominations.

1. Clarify and confirm

Restate the problem to ensure understanding: distinct denominations, unlimited reuse, return minimum coins or -1. Ask about constraints (e.g., target size, number of coins) to guide algorithm choice.

2. Choose DP approach

Decide between top-down memoization and bottom-up tabulation. Explain that DP is needed because greedy fails for arbitrary denominations.

3. Define state and recurrence

Let dp[i] be the minimum coins to make amount i. Initialize dp[0]=0 and dp[i]=infinity for i>0. For each i from 1 to target, dp[i] = min(dp[i - coin] + 1) over all coins ≤ i.

4. Implement and handle edge cases

Code the DP iteratively. After filling, return dp[target] if it's not infinity, else -1. Handle target=0 (return 0) and empty coins array.

5. Analyze complexity and test

State time complexity O(target * number of coins) and space O(target). Walk through a small example to verify correctness.

Key Points to Mention

Dynamic programming is required because greedy algorithm does not always yield optimal solution for arbitrary coin denominations.
State definition: dp[i] = minimum coins to make amount i.
Recurrence relation: dp[i] = min(dp[i - coin] + 1) for all coin ≤ i.
Base case: dp[0] = 0; initialize other entries to infinity (or a large number).
Time complexity: O(target * n) where n is number of coin denominations; space complexity: O(target).
Alternative approach: BFS on the amount graph, treating each coin as an edge, which also gives O(target * n) time.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.