Find Minimum Number of coins

Please be brutal, and treat this as a top 5 technical interview. I am trying to follow Google's way of writing Java code, as per their .pdf file online of code review. (Side note: do any of you see any improvement in me?)

Suppose I am asked to find the minimum number of coins you can find for a particular sum. That is, say, coins are 1, 3, 5, the sum is 10, so the answer should be 2, since I can use the coin 5 twice.

• Time Complexity = \$O(n^2)\$

• Space Complexity = \$O(n)\$

private static int findMinCoins(final int[]coins, final int sum){
    int[] calculationsCache = new int[sum+1];
    for(int i = 0; i = coins[j] && i - coins[j] >= 0 && calculationsCache[i-coins[j]]+1 < calculationsCache[i]){
                calculationsCache[i] = calculationsCache[i-coins[j]]+1;
            }
        }
    }
    return calculationsCache[sum];
}

You could change the innermost loop to foreach-style to make it slightly more readable:

for (int coin : coins) {
    if (i >= coin && i - coin >= 0 && calculationsCache[i - coin] + 1 < calculationsCache[i]) {
        calculationsCache[i] = calculationsCache[i - coin] + 1;
    }
}

Considering you do:

for (int i = 0; i <= sum; i++) {
    calculationsCache[i] = Integer.MAX_VALUE;
}
calculationsCache[0] = 0;

You could start the count in the loop from 1, since you're overwriting the first element right after anyway.

If coins[] doesn't contain a coin with value 1, then your function will return incorrect result:

// actual: -2147483646 (Integer.MAX_VALUE)
Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));

As you yourself found, the cause of this was the integer overflow in calculationsCache[i] = Integer.MAX_VALUE;, and you correctly fixed it by changing to calculationsCache[i] = Integer.MAX_VALUE - 1;.

For reference, an alternative implementation with unit tests:

private int findMinCoins(int[] coins, int sum, int index, int count) {
    if (sum == 0) {
        return count;
    }
    if (index == coins.length) {
        return 0;
    }
    if (sum < 0) {
        return 0;
    }
    int countUsingIndex = findMinCoins(coins, sum - coins[index], index, count + 1);
    int countWithoutUsingIndex = findMinCoins(coins, sum, index + 1, count);
    if (countUsingIndex == 0) {
        return countWithoutUsingIndex;
    }
    if (countWithoutUsingIndex == 0) {
        return countUsingIndex;
    }
    return Math.min(countUsingIndex, countWithoutUsingIndex);
}

private int findMinCoins(int[] coins, int sum) {
    return findMinCoins(coins, sum, 0, 0);
}

@Test
public void testExample() {
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 10));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 11));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 4));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 8));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 5, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 1, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 2, 1}, 9));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 3));
    Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 7}, 15));
}

StackExchange Code Review Q#47397, answer score: 11