## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India

Comment hidden because of low score. Click to expand.
2
of 4 vote

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)

``````import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class CoinChangingProblem {

static ArrayList<Integer> input = new ArrayList<Integer>();
static int ipmin = 999999;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);

int intval, max = 0;

while (scanner.hasNextInt()) {
intval = scanner.nextInt();

if (intval > max) {
max = intval;
}

if (intval < ipmin) {
ipmin = intval;
}

}

int[] coins = new int[max + 1];
for (int i = 0; i < coins.length; i++)
coins[i] = 99999999;

for (int i = 0; i < input.size() - 1; i++)
coins[input.get(i)] = 1;

for (int i = ipmin + 1; i < coins.length; i++) {
int min = coins[i];
for (int j = 0; j < input.size() - 1; j++) {
if ((i - input.get(j)) >= ipmin) {
if (min > (1 + coins[i - input.get(j)])) {
min = 1 + coins[i - input.get(j)];
}
}
}
coins[i] = min;
}
System.out.println("The denominations that make up the change are:");
show(coins, input.get(input.size() - 1));
}

public static void show(int[] coins, int val) {
if (val < ipmin)
return;

if (coins[val] == 1) {
System.out.println(val);
return;
}

int range, i;
for (i = 0; i < input.size() - 1; i++) {

range = val - input.get(i);
if (range >= ipmin && range < coins.length
&& coins[val] == 1 + coins[range]) {
System.out.println(input.get(i));
show(coins, val - input.get(i));
break;
}
}
if (i == input.size() - 1)
System.out.println(-1);
}
}``````

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

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

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

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

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

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

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

please tell me if there is any mistake

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

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 , seeing if we can use value , current coin count is 
- used  coins with denomination  to reduce sum target to 

Sum target is , seeing if we can use value , current coin count is 
- unable to use denomination  to reduce sum target

Sum target is , seeing if we can use value , current coin count is 
- used  coins with denomination  to reduce sum target to 

It took a total of  coins to make ``````

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

}

}``````

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

- 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.Sort();

foreach (int count in subAmount)
{
if (count > 0)
return 1 + count;
}
return -1;

}``````

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

How to calculate complexity of dynamic programming solution

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

hahahaahha.u r posting their onlin coding question over here.. :)

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

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

}``````

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

I was aked the same too
1. Rectangle overlap
2. Substring check
3. And this coin question

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

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

}``````

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

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;

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

}

}``````

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

``````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++) {
}
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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

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

if(sum < coins[i]) continue; is not required.

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

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.

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

Does not work for sum = 8, coins = [2,5]

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

Yes murlikrishna.b the statement
if(sum < coins[i]) continue; is not required.

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

Epic coder can you give me an example where it could return -1 when there are solutions?

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

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.

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

for sum = 8, coins = [2,5]... shouldn't the answer be 4 because you can make 8 from 4 2 cent coins.

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

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

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

In the above post I meant to say denominations 10, 7 and 1, not 5, 2 and 1 in the first line.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

This will run in exponential time. You should optimize your solution by using DP.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);
qsort(arr,n,sizeof(int),compare);
printf("The minimum number of coins required are %d ",noofCoins(arr,n,S));
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````Set Min[i] equal to Infinity for all of i
Min=0

For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1

Output Min[S]``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

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

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.

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

if the coins are { 2, 3, 5} and sum = 11, i think the above solution doesn't work.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

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

The above code can handle the case: coins {4,5,6} and sum = 18

Assume function "FindFirstCoinLessThan" use binary search

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.