Amazon Interview Question
Software Engineer / DevelopersCountry: India
int f(int nCount, const vector<int>& vBasic)
{
if (nCount < 0) return -1;
if (nCount == 0) return 0;
int nMin = -1;
for (int i = 0; i < vBasic.size(); ++i)
{
int nRet = f(nCount - vBasic[i], vBasic);
if (nRet < 0) continue;
if (nMin < 0)
nMin = nRet;
else
{
if(nMin > nRet)
nMin = nRet;
}
}
return nMin + 1;
}
package com.vmware.vsf.api.vmodl.impl;
import java.util.Arrays;
public class TestMe {
static int minNumOfCoins(int sum, int coins[]) {
int dp[] = new int[sum + 1];
Arrays.fill(dp, 0, dp.length, -1);
dp[0] = 0;
Arrays.sort(coins, 0, coins.length);
for (int i = 1; i <= sum; ++i) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < coins.length && i >= coins[j]; ++j) {
if (dp[i - coins[j]] != -1) {
if (min > dp[i - coins[j]] + 1) {
min = dp[i - coins[j]] + 1;
}
}
}
dp[i] = (min == Integer.MAX_VALUE) ? -1 : min;
}
return dp[sum];
}
public static void main(String args[]) {
System.out.println(minNumOfCoins(0, new int[] { 2, 5 }));
}
}
// min coin req. for particular sum
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int *res;
int mincoin(int *a,int size,int sum)
{
int i,min=pow(2,15),temp;
if(res[sum]!=-1)
return res[sum];
else if((int*) bsearch (&sum,a,size, sizeof (int), compare)!=NULL)
{ res[sum]=1; return 1;}
else
{
for(i=0;i<size&&sum>a[i];i++)
{
if(res[a[i]]==-1)
res[a[i]]=1;
if(res[sum-a[i]]==-1)
res[sum-a[i]]=mincoin(a,size,sum-a[i]);
temp=res[a[i]]+res[sum-a[i]];
if(temp<min)
min=temp;
}
res[sum]=min;
return res[sum];
}
}
int main()
{
int *a,sum,n,i,result;
printf("enter the total denominations of coins\n");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int ));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,n,4,compare);
printf("enter the req. sum\n");
scanf("%d",&sum);
res=(int *)malloc((sum+1)*sizeof(int));
res[0]=0;
for(i=1;i<=sum;i++)
res[i]=-1;
result=mincoin(a,n,sum);
if(result==pow(2,15))
result=-1;
printf("%d\n",result);
return 0;
}
My approach is a simple div/reduce algorithm:
- Sort denominations descending
- For each denomination,
- Can div?
- If yes, reduce sum target appropriately
- If sum target reduced to 0 then finished
- Else if denominations exhausted then try next denomination
- Else return -1
The output:
Sum target is [11], seeing if we can use value [5], current coin count is [0]
- used [2] coins with denomination [5] to reduce sum target to [1]
Sum target is [1], seeing if we can use value [3], current coin count is [2]
- unable to use denomination [3] to reduce sum target
Sum target is [1], seeing if we can use value [1], current coin count is [2]
- used [1] coins with denomination [1] to reduce sum target to [0]
It took a total of [3] coins to make [11]
The program:
import java.util.Arrays;
public class Test {
public static void main(String args[]) {
int[] inputs = new int[] {5, 3, 1};
int targetSum = 11;
int numCoins = new Test().numCoins(targetSum, inputs);
System.out.println("\nIt took a total of [" + numCoins + "] coins to make [" + targetSum + "]");
}
public int numCoins(int sum, int[] denominations) {
// first ordered descending
Arrays.sort(denominations);
for(int i = 0; i < denominations.length/2; i++)
{
int temp = denominations[i];
denominations[i] = denominations[denominations.length - i - 1];
denominations[denominations.length - i - 1] = temp;
}
// run the recursive algorithm
return findNumCoins(sum, denominations, 0, 0);
}
public int findNumCoins(int sumTarget, int[] denominations, int denominationIndex, int numCoins) {
System.out.println("\nSum target is [" + sumTarget + "], seeing if we can use value [" + denominations[denominationIndex] + "], current coin count is [" + numCoins + "]");
// base case, reduced sumTarget to zero
if (sumTarget == 0) return numCoins;
// base case, index cannot be more than set of denominations
if (denominationIndex > denominations.length) {
throw new RuntimeException("DenominationIndex exceeds the size of the denomination set. Did you exhaust possibilities?");
}
// what is the current denomination?
int currentDenomination = denominations[denominationIndex];
// is the current sumTarget divisible by current denomination?
int factor = sumTarget / currentDenomination;
// if unable to reduce sum target using current denomination, fail or move to next denomination
if (factor <= 0) {
System.out.println(" - unable to use denomination [" + currentDenomination + "] to reduce sum target");
// base case
if (denominationIndex >= denominations.length) {
// return -1 to indicate that we were unable to met sum given the denomination
return -1;
}
// otherwise move to next denomination
return findNumCoins(sumTarget, denominations, ++denominationIndex, numCoins);
}
// otherwise…
// increment the number of coins
numCoins += factor;
// reduce the target
sumTarget -= factor * currentDenomination;
System.out.println(" - used [" + factor + "] coins with denomination [" + currentDenomination + "] to reduce sum target to [" + sumTarget + "]");
// satisfied?
if (sumTarget == 0) return numCoins;
// exhausted?
if (denominationIndex == denominations.length) return -1;
// otherwise keep going
return findNumCoins(sumTarget, denominations, ++denominationIndex, numCoins);
}
}
- Dynamic Programming
public static int Minimum(int[] N, int amount)
{
List<int> subAmount = new List<int>();
for (int i = 0; i < N.Length; i++)
{
if (N[i] == amount)
return 1;
else if (amount > N[i])
{
subAmount.Add(Minimum(N, amount - N[i]));
}
}
subAmount.Sort();
foreach (int count in subAmount)
{
if (count > 0)
return 1 + count;
}
return -1;
}
int FindMaxCoin(int* coinStart, int* coinEnd, int max)
{
int maxWalkCoin = -1;
int numCoins = coinEnd - coinStart;
for(int i = 0; i < numCoins; i++)
{
int currCoin = *(coinStart + i);
if(currCoin == max)
{
maxWalkCoin = currCoin;
break;
}
else if(currCoin < max && currCoin > maxWalkCoin)
{
maxWalkCoin = currCoin;
}
}
return maxWalkCoin;
}
int GetMinCoinsToSum(int* coinStart, int* coinEnd, int sum)
{
if(!coinStart || !coinEnd)
{
return -1;
}
int maxCoin = FindMaxCoin(coinStart, coinEnd, sum);
int totalCoins = -1;
if(maxCoin > 0)
{
totalCoins = sum / maxCoin;
int totalSum = totalCoins * maxCoin;
int currCoin = 1;
while(totalSum != sum && currCoin != numCoins)
{
int rem = sum - totalSum;
maxCoin = FindMaxCoin(coinStart, coinEnd, rem);
if(maxCoin > 0)
{
int numCoins = (rem / maxCoin);
totalCoins += numCoins;
totalSum += (numCoins * maxCoin);
currCoin++;
}
else
{
break;
}
}
if(totalSum != sum)
{
totalCoins = -1;
}
}
return totalCoins;
}
Here is my recursive implementation in Java. I can post a dynamic programming version as well if needed. Comments, as always, are welcome.
public class minCoins {
public static int makeChange(int[] denom,int sum, int index) {
if (sum == 0){
return 0;
}
if (sum < 0 || index < 0) {
return Integer.MAX_VALUE-1;
}
return Math.min(makeChange(denom, sum-denom[index], index)+ 1,
makeChange(denom, sum, --index));
}
public static void main(String[] args) {
int[] coins = {1, 8, 11};
int sum = 24;
System.out.print("COINS: ");
for (int i = 0; i < coins.length;++i)
System.out.print(coins[i]+ " ");
System.out.println();
System.out.println("SUM: " + sum);
System.out.println("Minimum coins needed to reach sum of "
+ sum + " is: " + makeChange(coins, sum, coins.length-1) );
}
}
I had a little extra time, so here's the dynamic programming solution. Comments/criticisms are welcome.
public static int makeChangeDP(int[] denom, int sum){
if (sum == 0){
return 0;
} else {
int[] memo = new int[sum+1];
memo[0] = 0;
for (int j = 1; j < sum+1;++j)
memo[j] = Integer.MAX_VALUE -1;
for (int p = 1; p < sum+1;++p){
int min = Integer.MAX_VALUE-1;
for (int i = 0; i < denom.length;++i){
if (denom[i] <= p){
if (1+ memo[p-denom[i]]< min){
min = 1 + memo[p-denom[i]];
}
}
}
memo[p] = min;
}
return memo[sum];
}
}
public class MinimumCoin {
public static void main(String[] args) {
int[] coinList = {2, 3, 5};
int sum = 11;
System.out.println("The no.of coins required is: " + findMinimumCoin(coinList, sum));
}
public static int findMinimumCoin(int[] coinList, int sum){
if(coinList.length ==0 || sum ==0)
return -1;
int result = 0;
ArrayList<Integer> coinArray = new ArrayList<Integer>();
for(int i = 0; i < coinList.length; i++) {
coinArray.add(coinList[i]);
}
Collections.sort(coinArray);
Collections.reverse(coinArray);
while(sum!=0){
for(int i=0;i<coinArray.size();i++){
int coinElement = coinArray.get(i);
if(sum>=coinElement){
sum = sum - coinElement;
result++;
break;
}
if(sum!=0 && i==coinArray.size()-1){
return -1;
}
}
}
return result;
}
Assuming the coins array is sorted in (ascending in this case), traverse the coins array from the largest denomination coin and check is the sum is greater than the coin.
If sum is greater than sum/coin denomination is the number of coins of this denomination required and make sum = sum%coin denomination and continue, else skip and continue to the next lower denomination coin. In the end is some is no-zero than, return -1.
The code is below;
public int numberOfRequiredCoins(int sum, int[] coins) {
if(coins == null || coins.length == 0) {
System.err.println("Empty coins array");
return -1;
}
if(sum < 0) {
System.err.println("Negative sum given");
return -1;
}
int coinCount = 0;
for(int i = coins.length -1; i >= 0; i--) {
if(sum < coins[i]) continue;
else {
coinCount += (int)sum / coins[i];
sum = sum % coins[i];
}
}
if(sum == 0) return coinCount;
return -1;
}
This is a greedy strategy and could return -1 even when there are solutions. You need to use dynamic programming to get the optimum solution.
Epic coder can you give me an example where it could return -1 when there are solutions?
Tristan
For sum = 8, coins = [2,5] it will return -1
since 1(5 coin) and 1(2 coin) = 7 and we will be left with sum =1
if(sum == 0) return coinCount;
return -1;
hence -1 will be returned, which is correct.
for sum = 8, coins = [2,5]... shouldn't the answer be 4 because you can make 8 from 4 2 cent coins.
This approach will not work with all coin combinations. Imagine you have some (strange) coins with denominations 5, 2 and 1, and the amount 14.
Then your solution will use the 10 coin and 4 of the 1 coins, where the optimal solution would use two of the 7 coins.
This is an unusual case, but since the coin denominations are given as an array (and not fixed) it's one that must be considered.
The above approach would only work if all lower-level coins are a multiple of higher-level coins (e.g. 1, 2, 5 and 10) or if all lower-level coins are at most half of the value of the higher-level coins. (e.g. 1, 4 and 9).
private static int minCoins(int sum,int arr[],int itr,int count){
if(sum==0){
return count;
}
if(itr>= arr.length-1 || sum<0 ){
return -1;
}
int x = minCoins(sum-arr[itr],arr,itr+1,count++);
int y = minCoins(sum-arr[itr],arr,itr,count++);
int z = minCoins(sum,arr,itr+1,count);
if(x==-1 && y==-1 && z==-1)
return -1;
else{
int tmpMax = (x > y ? x : y) > z ? (x > y ? x : y) : z;
if(x==-1)
x=tmpMax;
if(y==-1)
y=tmpMax;
if(z==-1)
z=tmpMax;
return (x<y ? x:y) < z ? (x<y ? x:y) : z;
}
}
This can be done by considering the following scenario:
a.First sort the whole array and start from the last element as in order to get the minimum number of coins you have to try starting from the largest denomination. Divide it by the sum required and the quotient will tell us the number of coins of this denomination required.If quotient is not zero then take the remainder as that amount of money is left and divide it by the next number from the last.If quotient is zero it means this coin's denomination cannot be taken into account and thus divide it by the next smaller number.And in the count of no of coins add the quotient value for every denomination
b.In this way increment the count value and in the end you will get the count of the minimum number of coins.
Please test the below code as it works for all scenarios:
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b)
{
return (*(int *)a-*(int *)b);
}
int noofCoins(int arr[],int n,int S)
{
int div,noc=0,temp=S,i;
for(i=n-1;i>=0;i--)
{
div=temp/arr[i];
if(div!=0)
{
noc=noc+div;
temp=temp%arr[i];
}
}
return noc;
}
int main()
{
int arr[]={5,3,1};
int S=1;
int n=sizeof(arr)/sizeof(arr[0]);
qsort(arr,n,sizeof(int),compare);
printf("The minimum number of coins required are %d ",noofCoins(arr,n,S));
}
I would use dynamic programming to solve this. This one of those classic DP problems.
Let's say C[] is the sorted coins array and C[i] denotes value of ith coin and M[k] denotes the minimum number of coins required to get a sum of k.
Then
M[k] = min ( M[k-C[i] ) +1
Running time = O(NS) where N is the number of coins and S the desired sum.
This code will give the solution.....
int minCoinsCount(int a[], int N, int s)
{
int i, count=0;
while(s>0 && N--)
{
for(i=1; a[N]*i <= s; i++);
if(i>1)
{
count = count + i-1;
s = s - a[N]*(i-1);
}
// N--;
}
if(s == 0)
return count;
else
return -1;
}
In the above code, N total number of elements in array(Size of array), s is sum.
a[] is array, I am assuming array is sorted in increasing order.
well, obviously this is subset sum for positive integers,
I just thought about it like this, we try to find the minimum subset of coins that sum to the target amount.
try to find one coin that matches the amount. if not, try to find two, then three, till u find a subset or you fail
public static Queue<int> SubSetSum_Major(int[] input, int amount)
{
Queue<int> result = null;
for (int resultCount = 1; resultCount < input.Length; resultCount++)
//try with seubsets with length 1, then 2 ...
for (int i = 0; i < input.Length; i++)
{
SubsetSum(input, i, resultCount, amount, ref result);
if (result != null)
{
//whenever you find a result, will be with minimum length
return result;
}
}
return null;
}
public static void SubsetSum(int[] input, int startIndex, int subsetLength, int amount, ref Queue<int> result)
{
for (int i = startIndex; i <= input.Length - subsetLength; i++)
{
if (subsetLength == 1)
{
if (amount == input[i])
{
result = new Queue<int>(new int[] { input[i] });
}
}
else
{
SubsetSum(input, i + 1, subsetLength - 1, amount - input[i], ref result);
if (result != null)
{
result.Enqueue(input[i]);
if (result.Count == subsetLength)
return;
}
}
}
}
public int FindMinCoins(int[] coins, int end, int sum, int count)
{
int index = FindFistCoinLessThan(coins, end, sum);
if (index == -1)
return -1;
if (sum == coins[i])
return count+1;
if (sum > coins[i])
int result = FindMinCoins(coins, index, sum - coins[i], count+1);
if (result == -1)
int result = FindMinCoins(coins, index - 1, sum, count);
return result;
}
A well-known Dynamic Programming problem. Follows the recursive structure:
min # of coins for the given value = min {1 + min # of coins for [the given value - Di]. where Di are values from the set of Denominations}
I have got a working solution for this: Give input as:
1 2 5 10 20 50 100 500 1000 887 (Here 1 to 1000 are the denominations and the last number is the value for which the change has to be made)
Other examples are:
2 5 3 (make a change for 3 using the denominations 2 and 5, outputs -1)
10 5 2 21 (make a change for 21 using the denominations 10 5 & 2, outputs 10 5 2 2 2)
20 5 10 6 (make a change for 6 using the denominations 20 5 & 10, outputs -1)
- Murali Mohan June 19, 2013