## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Please check this one - looks like works

``````#include <iostream>
#include <vector>

void printAllCoinsCombinationComplex(int Sum, std::vector<int>& denominations, std::vector<int> coinsValue, int currentCoinIndex, int maxCoinsNumber)
{
if (Sum == 0 && maxCoinsNumber == 0)
{
//result
for (size_t i = 0; i < denominations.size(); ++i)
{
for (int j = coinsValue[i]; 0 < j; --j)
{
std::cout <<  denominations[i] << " " ;
}
}
std::cout << std::endl;
return;
}

if (Sum == 0 || maxCoinsNumber == 0)
{
//no valid combinations
return;
}

if (currentCoinIndex >= denominations.size())
return;

for (int i = 1; i*denominations[currentCoinIndex] <= Sum; ++i)
{
coinsValue[currentCoinIndex] +=i;
printAllCoinsCombinationComplex(Sum - i*denominations[currentCoinIndex], denominations, coinsValue, currentCoinIndex+1, maxCoinsNumber-coinsValue[currentCoinIndex]);
coinsValue[currentCoinIndex] -=i;
}

if (currentCoinIndex+1 < denominations.size())
printAllCoinsCombinationComplex(Sum, denominations, coinsValue, currentCoinIndex+1, maxCoinsNumber);
}

int main()
{
int denominations[] = {25, 10, 5, 1};
std::vector<int> vDenominations(&denominations[0], &denominations[(sizeof denominations / sizeof(int)) ]);
std::vector<int> vValues(vDenominations.size(), 0);
printAllCoinsCombinationComplex(30, vDenominations, vValues, 0, 6);
return 0;
}``````

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

yep, this code is very similar to the one I produced in the interview:

``````static void ChangeCoinsModified(int sum, int n, int[] d, int start, List<int> combination)
{
if(n==0 && sum == 0)
{
PrintArray(combination);
}
if(n==0)
{
return;
}
for(var i=start;i<d.Length;i++)
{
if (d[i] > sum) continue;
var newCombination = new List<int>(combination) {d[i]};
ChangeCoinsModified(sum-d[i], n-1,d, i, newCombination);
}
}``````

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

hi
can anyone explain this code.

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

@S.Abakumoff,

will your code work for 555555 = 30 , I dont think so you will never generate this sequence

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

This works for the 6 5's

``````public class Denominations {
public static void main(String[] args){
int[] d = {1,5,10,25};
int[] maxdCount = new int[d.length];
int sum = 30;
int n = 6;
populateMaxdCount(d,maxdCount,sum,n);
printCombinations(sum,n,d,maxdCount,d.length-1, new ArrayList<String>());
//for(int i:maxdCount)System.out.println(i);
}

private static void printCombinations(int sum, int n, int[] d, int[] maxdCount, int curr, List<String> combinations) {
if(sum==0 && n==0){
System.out.println(combinations);
return;
}else if(sum<0 || n<0 || curr<0){
return;
}

for(int i=maxdCount[curr];i>=0;i--){
printCombinations(sum-(i*d[curr]), n-i, d, maxdCount, curr-1, combinations);
combinations.remove(i +" "+ d[curr]);
}
}

private static void populateMaxdCount(int[] d, int[] maxdCount, int sum, int n) {
for(int i=0;i<d.length; i++){
int count=sum/d[i];
maxdCount[i]=(count>n?n:count);
}
}``````

}

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

its a DP problem, similar to coin change problem, only change is that denomination should not be repeated..

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

I think as per the problem the denominations could be repeated. As I understand it first solve for the coin change problem that sum up to the change value n. then print out the different combinations (non-repeated) of the denominations that were used to sum up to n.

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

this problem turned out to be much easier to solve than using dp. There is the polynomial solution with the recursive calls + some logic to cut off the calls that lead to the already inspected combinations.

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

``````public static void main(String[] args) {

int aSum = 26;
int[] denom = {25, 10, 5, 1};

findValidCombos(denom, aSum, denom.length, 0, new ArrayList<Integer>(),    validCombos );
for(List<Integer> combo: validCombos) {
for(int i = 0 ; i < combo.size(); i++)
System.out.print(denom[i] +" X "+ combo.get(i) +"\t");
System.out.println();
}
}

private static void findValidCombos(int[] denom,int aSum,  int maxlevel, int level, List<Integer> stack, List<List<Integer>> validCombo ) {
int d = denom[level];
for(int i = aSum/d ; i >=0 ; i--) {
int a = d * i;
if(maxlevel == level+1) {
//check the sum of combo
int tSum = 0;
for(int j = 0 ; j < stack.size(); j++) {
int x = stack.get(j) * denom[j];
tSum+=x;
}
if(tSum == aSum) {
//System.out.println(stack);
List<Integer> combo = new ArrayList<Integer>(stack.size());
}

stack.remove(stack.size()-1);
}
else {
findValidCombos(denom, aSum,maxlevel, level+1, stack, validCombo);
stack.remove(stack.size()-1);
}

}
}``````

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

Given a sum say 26 and denominations quarters (25) , dime (10), nickel (5) and pennies (1) first find max number of coins per denominations that reaches the sum. Then apply the find change problem only to find all possible permutations.

For sum=26 you can have zero or 1 quarter, 0 to 2 dimes, 0 to 5 nickels and 0 to 26 nickels.

Putting the face values:
quarters(25) 0,25
dime(10) 0,1,2
nickel(5) 0,1,2,3,4,5
pennies(1) 0,1,2,3,4,5,6,7,8....26

Not just find all combination that add up to sum.
Say dmax represents such a matrix as shown below

* 25 0
* 20 10 0
* 25 20 15 10 5 0
* 26 25 24 23 ........ 20 ... 10 ... 5, 4, 3, 2, 1 , 0

we find the valid combinations as below. But a generic version is the one I posted above in findValidCombos method.

``````for(int a1: dmax[0]) {
for(int a2: dmax[1]) {
for(int a3: dmax[2]) {
for(int a4: dmax[3]) {
if (a1+a2+a3+a4 == aSum) {
System.out.println(a1+","+a2+","+a3+","+a4);
}
}
}
}
}``````

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

int a = d * i; - is not used,
denom[j]; - thorws index out of range exception.
Somethign is wrong with this.

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

Treat this like an odometer problem. Start with zero of each coin. Increment pennies. If pennies takes you past n, then zero pennies and increment nickels. If nickels take you past n, then zero pennies and nickels and increment dimes. If dimes take you past n, then zero pennies/nickels/dimes and increment quarters. If quarters take you past n, then you're done. Each roll of the odometer starts on pennies again.

Once you get a basic odometer working, refine the increment step to be more aggressive. For example, if you are looking at nickels and you're 15 short, jump right ahead to incrementing 3 nickels. If you're 14 short, jump right ahead to two more nickels, and then continue the loop to get more pennies.

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

Here's example Python code:

``````def ways_to_make_change(amount, coins):
# Assumption: coins[0] should be the smallest
# denomination for optimal performance.
solution = [0] * len(coins)
amount_needed = amount
while True:
# To generate each new solution, we increase
# at most one of the denominations and roll
# the odometer back to zero for any smaller
# coins.
which_coin = 0
while True:
if coins[which_coin] > amount_needed:
for i in range(which_coin+1):
amount_needed += solution[i] * coins[i]
solution[i] = 0
which_coin += 1
if which_coin >= len(coins):
return
else:
if which_coin == 0:
coins_needed = amount_needed / coins[which_coin]
else:
coins_needed = 1
amount_needed -= coins_needed * coins[which_coin]
solution[which_coin] += coins_needed
if amount_needed == 0:
yield solution
break

coins = [1, 5, 10, 25]
amount = 27
for solution in ways_to_make_change(amount, coins):
print solution``````

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

Hi,
I probably didn't make it clear..but the input has the number of coins that should sum up to n. i.e. in your sample:
coins = 1,5,10,25, amount=27
There should be one more input parameter - number of coins. I.e. if number of coins = 3 then the output should be:
1,1,25
and no other combinations.
but if number of coins = 5 then the output would be
1, 1, 5, 10, 10 and no others
Another example:
coins = [1,5,10,25] sum = 30 n = 6
Output:
1,1,1,1,1,25
5,5,5,5,5,5

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

dp[i][n][sum]=dp[i-1][n-1][sum-a[i]]+dp[i-1][n][sum]

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

The array of coin denominations could be arbitrarily long, which makes a DP solution a bit tricky to orchestrate. Suppose you have pennies, nickels, dimes, quarters, and half dollars. Then you have a five-dimensional matrix of coin combinations.

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

void printsubset(int a[],int n)
{ for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<"\n";
}
void printallsubset(int arr[],int tmp[],int asize,int tsize,int sum,int ite,int targetsum)
{
if(sum==targetsum) {
printsubset(tmp,tsize);
printallsubset(arr,tmp,asize,tsize-1,sum-arr[ite],ite+1,targetsum);
return;
}
else
{ for(int i=ite,i<asize,i++)
{ tmp[tsize]=arr[i];
printallsubset(arr,tmp,asize,tsize+1,sum+arr[i],i+1,targetsum);
}
}
}

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

``````def denom_nonrep(l, n, s):
def denom_int(d, n, s, p):
if n==0 and s==0:
print p
return

k=[x for x in d if d[x]]
for x in k:
d[x]=False
tmp_s=s
tmp_n=n
while(True):
p.append(x)
tmp_s-=x
tmp_n-=1
if (tmp_s<0 or tmp_n<0):
break
denom_int(d, tmp_n, tmp_s, p)
while(tmp_n<n):
tmp_n+=1
p.pop()
for x in k:
d[x]=True

d=dict([(x,True) for x in l])
denom_int(d, n, s, [])

def main():
l=[1,5,10,25]
n=6
s=30
denom_nonrep(l,n,s)``````

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

Implementation in C++ using lambda

``````#include <stdio.h>

#include <future>
#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>

/**
* input:
* sum - the integer amount
* n - the number of coins
* d - the array contains the coins denominations
*
* WAP that prints all the possible non-repeated combinations of n coins of denominations from d that sum up to n.
*
* Sample of input:
* d={1,5,10,25}
* sum = 30
* n = 6
* The expected output:
* 1,1,1,1,1,25
* 5,5,5,5,5,5
*
*/
static void
printArray(const std::vector<int> &d, int sum, size_t n)
{
int result[n];
std::function<void (int, int, size_t)> rec = [&result, &d, &n, &rec](int lastNumber, int sum, size_t resultSize) {

if (resultSize) {
for (size_t i = 0; i < d.size(); ++i) {
if (sum - d[i] < 0 || d[i] < lastNumber) continue;
result[n - resultSize] = d[i];
rec(d[i], sum - d[i], resultSize - 1);
}
}
else if (!sum) {
for (size_t i = 0; i < n; ++i) {
std::cout << result[i];
if (i < n - 1) std::cout << " ";
}
std::cout << std::endl;
}
};

rec(0, sum, n);
}

int main(int, char **)
{
std::vector<int> d = { 1, 5, 10, 25 };

printArray(d, 30, 6);

return 0;
}``````

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

Could anyone explain the question ?

1,1,1,1,1,25 has 8 coins in it, not n.

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.