## Collective Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be solved using DP.

initilize 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i=k
C[k]=min(C[i]+C[k-i)
i=0

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

How can we do it if we had a limited supply of coins??

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.