Collective Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Working Java solution using dynamic programming.
import java.util.HashMap;
public class MakeChange {
public static int[] makeChange(int value, int[] coinValues) {
HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();
return makeChangeHelper(value, coinValues, map);
}
public static int[] makeChangeHelper(int value, int[] coinValues, HashMap<Integer, int[]> map) {
if (map.containsKey(value)) return map.get(value);
if (value == 0) return new int[coinValues.length];
if (value < 0) return null;
int minCoins = Integer.MAX_VALUE;
int[] minResult = null;
for (int coinIdx = 0; coinIdx < coinValues.length; coinIdx++) {
int coinValue = coinValues[coinIdx];
int[] result = makeChangeHelper(value - coinValue, coinValues, map);
if (result != null) {
int nCoins = sumArray(result);
if (nCoins < minCoins) {
minResult = result;
minResult[coinIdx]++;
minCoins = nCoins;
}
}
}
map.put(value, minResult.clone());
return minResult;
}
public static int sumArray(int[] array) {
int sum = 0;
for (int value : array)
sum += value;
return sum;
}
public static void main(String[] args) {
int value = Integer.parseInt(args[0]);
int[] coinValues = new int[args.length - 1];
for (int i = 0; i < coinValues.length; i++)
coinValues[i] = Integer.parseInt(args[i+1]);
int[] change = makeChange(value, coinValues);
System.out.print("Best way to make change for " + value + " is: ");
for (int i = 0; i < coinValues.length; i++) {
System.out.println(coinValues[i] + ": " + change[i]);
}
}
}
There was a small bug in the above code which I fixed below:
import java.util.HashMap;
public class MakeChange {
public static int[] makeChange(int value, int[] coinValues) {
HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();
return makeChangeHelper(value, coinValues, map);
}
public static int[] makeChangeHelper(int value, int[] coinValues, HashMap<Integer, int[]> map) {
if (map.containsKey(value)) return map.get(value);
if (value == 0) return new int[coinValues.length];
if (value < 0) return null;
int minCoins = Integer.MAX_VALUE;
int[] minResult = null;
for (int coinIdx = 0; coinIdx < coinValues.length; coinIdx++) {
int coinValue = coinValues[coinIdx];
int[] result = makeChangeHelper(value - coinValue, coinValues, map);
if (result != null) {
int nCoins = sumArray(result);
if (nCoins < minCoins) {
minResult = result.clone();
minResult[coinIdx]++;
minCoins = nCoins;
}
}
}
map.put(value, minResult);
return minResult;
}
public static int sumArray(int[] array) {
int sum = 0;
for (int value : array)
sum += value;
return sum;
}
public static void main(String[] args) {
int value = Integer.parseInt(args[0]);
int[] coinValues = new int[args.length - 1];
for (int i = 0; i < coinValues.length; i++)
coinValues[i] = Integer.parseInt(args[i+1]);
int[] change = makeChange(value, coinValues);
System.out.println("Best way to make change for " + value + " is: ");
for (int i = 0; i < coinValues.length; i++) {
System.out.println(coinValues[i] + ": " + change[i]);
}
}
}
int dp[n+1];
dp[0]=0;
int i,j;
for(i=1;i<=amount;i++)
{
for(j=0;j<n;j++)
{
if(den[j]>i) break;
if(dp[i]==-1) {
dp[i]=dp[i-den[j]]+1;
}else{
dp[i]=min(dp[i],dp[i-den[j]+1);
}
}
}
cout<<"Min no. of coins: "<<dp[amount]<<endl;
//Code to produce the coins used
int val=amount;
while(val)
{
for(i=0;i<n;i++)
{
if(den[i]<=val && dp[val]=1+dp[val-den[i]]) {cout<<den[i]<<" "; val-=den[i]; break;}
}
}
It can be solved using DP.
- Anonymous April 27, 2014initilize array C[n] with 1 for C[1-n]
then using following formula
C[0]=0
and
k0
C[k]=min(C[i]+C[k-i])
i=0
C[v] will be the minimum coins required for V value.