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

-
Can you provide the link to that pdf ? –  konijn Apr 16 '14 at 22:05
–  bazang Apr 16 '14 at 22:28
Please do not edit the question in a way that invalidates an answer. I've rolled back your question to Rev 4. You may post the correction as an answer to your own question instead. –  200_success Apr 17 '14 at 0:52
findMinCoins(new int[]{2}, 1) == Integer.MAX_VALUE but correct answer is: "Can't be done." Also Are you given the method signature? (I think not on account of private) –  abuzittin gillifirca Apr 17 '14 at 6:24
You don't define what you mean by n. Your algorithm looks like it has runtime O(sum * coins.length) and space O(sum). –  CodesInChaos Apr 17 '14 at 11:08

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));
}

-
It does enter the inner if statement; the problem is somewhere else. –  bazang Apr 16 '14 at 23:49
I figured it out -- my algorithm is correct, the issue is overflows. Integer.MAXVALUE < Integer.MAXVALUE is true; so I changed it to MAXVALUE-1(i.e a val that would not overflow, and voila, it works, –  bazang Apr 17 '14 at 0:25
@bazang ah, you're right, on both counts. I fixed that point in my answer, thanks! –  janos Apr 17 '14 at 5:16

Your dynamic programming algorithm is basically correct (except for the bug that @janos found). That's a good start.

You've declared the function as static, which is an improvement over your previous questions. However, it's private, which makes the function not so useful. I'm not a fan of the final keywords for the parameters, as they add noise without adding much protection. It doesn't guarantee to the caller that your function won't modify the contents of coins, for example. If you're going to declare coins final, why not declare calculationsCache final as well? I personally prefer to leave final off for all parameters and local variables, though I understand that some other programmers like them.

Your code completely violates the Google Style Guide when it comes to horizontal whitespace. In general, you need to be more generous with spaces next to punctuation. That includes a space next to (, ), int[], =, +, -.

As for the code itself…

calculationsCache is a pretty good name, but I think it would be even better if it were named minCoins, as it would make the code read smoothly. I also suggest using s instead of i as the name of the iteration variables, so that it mentally suggests a relationship with sum.

In the conditional, i >= coins[j] and i - coins[j] >= 0 are redundant. For readability and to reduce repetition, I suggest taking advantage of Math.min().

public static int findMinCoins(final int[] coins, final int sum) {
int[] minCoins = new int[sum + 1];
for (int s = 1; s <= sum; s++) {
minCoins[s] = Integer.MAX_VALUE - 1;
}

for (int s = 1; s <= sum; s++) {
for (int coin : coins) {
if (s >= coin) {
minCoins[s] = Math.min(minCoins[s], minCoins[s - coin] + 1);
}
}
}
return minCoins[sum];
}


As for the complexity, it would be more accurate to say that the time is O(S C) and the space is O(S).

-
I wholeheartedly agree about final. I use it only for fields and variables used in anonymous inner classes (I.e. where the compiler requires it). It can be exceedingly misleading on parameters, implying arrays and objects cannot be modified, which you rightly point out is not the case. –  David Harkness Apr 17 '14 at 1:48
@200_success to be honest, I never used final in actual code that I wrote. It was here, that someone yelled at me for not using final for variables, and I figured before I show up at my interview, perhaps it's a blunder on my part that I have to fix. –  bazang Apr 18 '14 at 2:01

Style

• Surround all binary operators with spaces.
• Put a space before every open brace.
• Favor for (x : xs) over manual index management.
• Break up your methods so each does one thing. It sounds crazy at first, but 3-to-5 lines is the sweet spot. Small methods tend to be self-documenting.

Code

The expression

i >= coins[j] && i - coins[j] >= 0


is equivalent to

i >= coins[j]


Sorry, a deeper review will have to wait til I'm not on my phone. I will say that my gut says a recursive approach will yield a cleaner solution. Start with clean and clear and only refractor once you have good test coverage and can identify a measurable problem.

-
The problem with a recursive approach is that it can easily run out of stack. So it's a good idea to take a look at the sizes you need to support to see if a particular recursive approach causes a stackoverflow before actually implementing it. –  CodesInChaos Apr 17 '14 at 11:18
@David Harkness what do you mean by surround all binary operators with spaces? –  bazang Apr 18 '14 at 1:56
And if I am writing this at a Google interview, I'm sure the interviewer would probably not like a bunch of sub functions for something that could be done in 6-7 lines in general? Wouldn't that be an overkill? –  bazang Apr 18 '14 at 1:57
@bazang Put whitespace around operators for readability and because it matches Google's style guide,that's , x = y + 2 vs. x=y+2. In an interview, your process will be watched. If you demonstrate early how to decompose functions, that's one less thing the company will need to teach you. –  David Harkness Apr 18 '14 at 2:21
@bazang Keep in mind that the process is more about seeing your reaction and progression. This site is about reviewing working, real-world code. At least touch on these subjects in an interview, but be prepared to demonstrate that you can do it--not just speak to it. I won't care about 6 vs. 15 minutes. I will be inferring your abilities from the little code you write. Take your time and do it right! Ask questions. Be precise. Point out deficiencies you'd correct with more time and offer to do it right there. –  David Harkness Apr 18 '14 at 2:21