Walmart Labs·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Walmart Labs coding screen for a software engineer role. Pretty standard DP question but the discussion around it went deeper than I expected.

Questions Asked (1)

Given an integer target amount and an array of distinct coin denominations with unlimited supply, return the number of distinct combinations (not permutations) of coins that sum to the target amount.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the 1D DP setup pretty well: dp[0] = 1, then for each coin iterate the amount forward and accumulate.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that this is a classic dynamic programming problem (coin change 2) where order doesn't matter. Explain that you'll use a 1D DP array where dp[i] represents the number of ways to make amount i, iterating over coins in the outer loop and amounts in the inner loop to avoid counting permutations. Then discuss time and space complexity, and mention possible optimizations or trade-offs.

Pro tip: Emphasize that iterating coins in the outer loop and amounts in the inner loop ensures combinations, not permutations—this is a common pitfall. Also, mention that you can optimize space to O(target) and that the problem is equivalent to counting integer partitions with restricted part sizes.

1. Clarify the problem

Confirm that order doesn't matter and that coins can be used unlimited times. Ask if the target can be 0 or if denominations can be empty.

2. Define the DP state

Let dp[i] be the number of ways to make amount i. Initialize dp[0] = 1 (one way to make 0: use no coins).

3. Determine iteration order

Iterate over each coin in the outer loop, and for each coin, iterate over amounts from coin to target in the inner loop. This ensures each combination is counted once.

4. Implement the transition

For each coin and amount, update dp[amount] += dp[amount - coin]. This accumulates the number of ways using the current coin.

5. Analyze complexity and edge cases

Time complexity O(n * target), space O(target). Handle edge cases: target = 0 returns 1, no coins returns 0 (unless target=0).

Key Points to Mention

Dynamic programming approach with 1D array
Iteration order: coins outer, amounts inner to avoid permutations
Time complexity O(n * target) and space O(target)
Base case: dp[0] = 1
Edge cases: target = 0, empty denominations, unreachable amounts
Comparison with recursive or memoization approaches and their trade-offs

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