search

mission-peace / interview

Interview questions
Apache License 2.0
11.08k stars 5.17k forks source link

Coin change solution fails simple test cases #29

Closed rbaral closed 8 years ago

mission-peace commented 8 years ago

It is working as expected. If you look at code its pretty clear if solution is not possible it returns Integer.MAX_VALUE which is 2147483647 . I never said it will return -1 if solution is not possible.

Second for cases like [186, 419, 83, 408]for amount:6249 . It is returning 20. I dunno what code you are running. I ran it right now and it returns 20 without any problem. https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java Are you talking about this code??

Bottom up also returns Integer.MAX_VaLUE if solution is not possible. I have updated the docs to say that.
https://github.com/mission-peace/interview/commit/73384e088a5a21625c3430970807893fb19b892a

rbaral commented 8 years ago

Thanks for the response, yes I am referring to the code you pointed. Yes, I agree for the case of -1, we can change it. I just tried the code for the topdown approach, it failed for the following cases, where the expected return is not -1: coins:[1, 2, 5]...for amount:11..expected return coins:3...got:2147483647 coins:[186, 419, 83, 408]...for amount:6249..expected return coins:20...got:2147483647 coins:[1, 2, 3]...for amount:5..expected return coins:2...got:2147483647

These are the just few test cases that I tried.

mission-peace commented 8 years ago

[186, 419, 83, 408]...for amount:6249 Got 20 [1, 2, 5]...for amount:11 Got 3 [1, 2, 3]...for amount:5 Got 2

Code is running as expected. Are you sure you have exact same code as on github?

rbaral commented 8 years ago

Used this code https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java

The bottomup approach is good for me. No worries about the other approaches for now.