Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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);
}
}
@S.Abakumoff,
will your code work for 555555 = 30 , I dont think so you will never generate this sequence
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--){
combinations.add(i +" "+ d[curr]);
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);
}
}
}
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;
stack.add(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());
combo.addAll(stack);
validCombo.add(combo);
}
stack.remove(stack.size()-1);
}
else {
findValidCombos(denom, aSum,maxlevel, level+1, stack, validCombo);
stack.remove(stack.size()-1);
}
}
}
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);
}
}
}
}
}
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.
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
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
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);
}
}
}
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)
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;
}
Please check this one - looks like works
- Alexandr Yegorov March 01, 2013