Amazon Interview Question Senior Software Development Engineers
Country: United States
Interview Type: Written Test
Thank you very much. I add a condition, I think it can reduce the nest, is that OK?
if(n < denom)
#include "stdafx.h"
#include <stdio.h>
int makeChange2(int n, int denom);
int getNextDenom(int denom);
int _tmain(int argc, _TCHAR* argv[])
{
int n = 6, change = 0;
change = makeChange2(n, 1);
printf("input = %d, output = %d\n",n,change);
n = 11;
change = makeChange2(n, 1);
printf("input = %d, output = %d\n",n,change);
n = 26;
change = makeChange2(n, 1);
printf("input = %d, output = %d\n",n,change);
n = 76;
change = makeChange2(n, 1);
printf("input = %d, output = %d\n",n,change);
getchar();
return 0;
}
int makeChange2(int n, int denom)
{
//Base condition
if(0 == n)
return 1;
if(n < 0 || 0 == denom)
return 0;
if(n < denom)
return 0;
int nextDenom = getNextDenom(denom); //get the next denominator
//either take the current denominator or eliminate it
return makeChange2(n - denom, denom) + makeChange2(n, nextDenom);
}
//Utility function to get the next denominator
int getNextDenom(int denom)
{
if(1 == denom)
return 5;
else if(5 == denom)
return 10;
else if(10 == denom)
return 25;
else
return 0;
}
private static void checkForOptions(int value, int[] coinArray,
ArrayList<Integer> selectedCoins, int headNumberPassed) {
if (headNumberPassed > 0) {
selectedCoins.add(headNumberPassed);
}
for (int i = 0; i < coinArray.length; i++) {
int headNumber = coinArray[i];
if (headNumber < value) {
int newNumber = value - headNumber;
checkForOptions(newNumber, coinArray, new ArrayList<Integer>(
selectedCoins), headNumber);
} else if (headNumber == value) {
selectedCoins.add(headNumber);
printSelectedCoin(selectedCoins);
} else {
return;
}
}
}
private static void checkForOptions(int value, int[] coinArray,
ArrayList<Integer> selectedCoins, int headNumberPassed) {
if (headNumberPassed > 0) {
selectedCoins.add(headNumberPassed);
}
for (int i = 0; i < coinArray.length; i++) {
int headNumber = coinArray[i];
if (headNumber < value) {
int newNumber = value - headNumber;
checkForOptions(newNumber, coinArray, new ArrayList<Integer>(
selectedCoins), headNumber);
} else if (headNumber == value) {
selectedCoins.add(headNumber);
printSelectedCoin(selectedCoins);
} else {
return;
}
}
}
This is known as coin problem. It has two variations. One is concerned with the possibility of maximum number of ways to make a particular sum out of given number of values. The other attempts to find the minimum number of coins. Here, we have the minimum number of required coins. We can create an array that has 1...n-1 elements, where n denotes the sum we are interested in, along with a hash that keeps track of minimum combination so far (i.e., a DP as mentioned above).
int FindMinimumNumberOfCoins(int LumpSum)
{
if(LumpSum <= 0)
return 0;
int *a=new int[LumpSum-1];
for(i=1;i<=Sum-1;i++)
a[i-1]=i;
int sum=6,p,min,indx,i,n=sizeof(a)/sizeof(a[0]);
int *c=new int[sum+1];
memset(c,0,sizeof(c)*(sum+1));
c[0]=0;
for(i=0;i<n;i++)
c[a[i]]=1; //c[a[i]]++; is better
printf("\n");
for(p=1;p<=sum;p++)
{
if(c[p]!=1) //include this if MINIMUM NUMBER OF COINS/WAYS is needed
{
min=inf;
indx=-1;
for(i=0;i<n;i++)
{
if(a[i]<=p)
{
if(c[p-a[i]]<min)
{
min=c[p-a[i]];
indx=p-a[i];
}
}
}
if(indx!=-1)
c[p]=c[indx]+1;
}
}
printf("%d\n",c[sum]);
delete [] c;
delete [] a;
}
public static int getCombinationNumbers(int value){
if(value < 0) return -1;
if(value == 0) return 0;
List<Integer> coins = new ArrayList<Integer>();
coins.add(1);
coins.add(5);
coins.add(10);
coins.add(25);
return getCombs(value, coins);
}
public static int getCombs(int value, List<Integer> coins) {
if(value < 0) return 0;
if(value == 0 || coins.size() == 1) return 1;
List<Integer> currentCoins = new ArrayList<Integer>(coins);
int largestCoinIndex = coins.size() - 1;
if(value < currentCoins.get(largestCoinIndex)) {
currentCoins.remove(largestCoinIndex);
return getCombs(value, currentCoins);
}
int count = 0;
int coinNumber = value / currentCoins.get(largestCoinIndex);
int largestCoinsValue = currentCoins.remove(largestCoinIndex);
for(int i = 0; i <= coinNumber; i++) {
count += getCombs(value - i * largestCoinsValue, currentCoins);
}
return count;
}
import java.util.HashMap;
public class Combinations {
public static HashMap<Integer,Integer> lookup = new HashMap<Integer,Integer>() ;
public static Integer[] currency = {25,10,5};
public static void main(String[] argv)
{
countCombinations(13);
}
public static boolean check()
{
int dimCount= lookup.get(10);
int nickleCount = lookup.get(5) ;
int quarterCount = lookup.get(25);
if((dimCount>1)||(nickleCount>1)||(quarterCount>1))
{
return true;
}
return false;
}
public static void countCombinations(int input)
{
int totalcount=1;
lookup.put(25,0);
lookup.put(10,0);
lookup.put(5,0);
lookup.put(1,0);
for(Integer x : currency)
{
if(x<=input)
{
lookup.put(x, input/x);
int reminder = input%x;
if(reminder>=10)
{
lookup.put(10,reminder/10);
reminder = reminder %10;
if(reminder>5)
{
lookup.put(5, reminder/5);
lookup.put(1, reminder%5);
}
}else if((reminder>=5)&&(reminder<10))
{
lookup.put(5,reminder/5);
lookup.put(1,reminder%5);
}else if(reminder<5)
{
lookup.put(1,reminder);
}
boolean flag= check();
while(flag)
{
if(lookup.get(25)>1)
{
lookup.put(25,lookup.get(25)-1);
lookup.put(10,lookup.get(10)+2);
lookup.put(5,lookup.get(5)+1);
totalcount+=1;
}
else if(lookup.get(10)>1)
{
lookup.put(10,lookup.get(10)-1);
lookup.put(5,lookup.get(5)+2);
if(lookup.get(5)>1)
{
totalcount+=lookup.get(5);
}
else
{
totalcount+=1;
}
}else if(lookup.get(5)>1)
{
totalcount+=lookup.get(5)-1;
lookup.put(5, 1);
}
flag = check();
}
totalcount+=1;
lookup.put(25,0);
lookup.put(10,0);
lookup.put(5,0);
lookup.put(1,0);
}
}
System.out.println(totalcount);
}
}
import java.util.HashMap;
public class Combinations {
public static HashMap<Integer,Integer> lookup = new HashMap<Integer,Integer>() ;
public static Integer[] currency = {25,10,5};
public static void main(String[] argv)
{
countCombinations(13);
}
public static boolean check()
{
int dimCount= lookup.get(10);
int nickleCount = lookup.get(5) ;
int quarterCount = lookup.get(25);
if((dimCount>1)||(nickleCount>1)||(quarterCount>1))
{
return true;
}
return false;
}
public static void countCombinations(int input)
{
int totalcount=1;
lookup.put(25,0);
lookup.put(10,0);
lookup.put(5,0);
lookup.put(1,0);
for(Integer x : currency)
{
if(x<=input)
{
lookup.put(x, input/x);
int reminder = input%x;
if(reminder>=10)
{
lookup.put(10,reminder/10);
reminder = reminder %10;
if(reminder>5)
{
lookup.put(5, reminder/5);
lookup.put(1, reminder%5);
}
}else if((reminder>=5)&&(reminder<10))
{
lookup.put(5,reminder/5);
lookup.put(1,reminder%5);
}else if(reminder<5)
{
lookup.put(1,reminder);
}
boolean flag= check();
while(flag)
{
if(lookup.get(25)>1)
{
lookup.put(25,lookup.get(25)-1);
lookup.put(10,lookup.get(10)+2);
lookup.put(5,lookup.get(5)+1);
totalcount+=1;
}
else if(lookup.get(10)>1)
{
lookup.put(10,lookup.get(10)-1);
lookup.put(5,lookup.get(5)+2);
if(lookup.get(5)>1)
{
totalcount+=lookup.get(5);
}
else
{
totalcount+=1;
}
}else if(lookup.get(5)>1)
{
totalcount+=lookup.get(5)-1;
lookup.put(5, 1);
}
flag = check();
}
totalcount+=1;
lookup.put(25,0);
lookup.put(10,0);
lookup.put(5,0);
lookup.put(1,0);
}
}
System.out.println(totalcount);
}
}
Here's a solution I played with while reading about this:
- Jack September 11, 2013public class coin { private static int[] values = { 1, 5, 10, 25, 50, 100 }; public static int numCoinCombo(int value) { return findNumSolUnder(value, 0); } private static int findNumSolUnder(int value, int place) { if (place >= values.Count() || value < 0) return 0; if (value == 0) return 1; return findNumSolUnder(value - values[place], place) + findNumSolUnder(value, place + 1); } }