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 &lt;= sum; i++){
        calculationsCache[i] = Integer.MAX_VALUE;
    }
    calculationsCache[0]=0;/*sum 0 , can be made with 0 coins*/
    for(int i = 1; i &lt;= sum; i++){
        for(int j = 0; j &lt; coins.length; j++){
            if(i &gt;= coins[j] &amp;&amp; i - coins[j] &gt;= 0 &amp;&amp; calculationsCache[i-coins[j]]+1 &lt; 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 &gt;= coin &amp;&amp; i - coin &gt;= 0 &amp;&amp; calculationsCache[i - coin] + 1 &lt; calculationsCache[i]) {
        calculationsCache[i] = calculationsCache[i - coin] + 1;
    }
}




Considering you do:


for (int i = 0; i &lt;= 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 &lt; 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));
}