Yahoo Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
This Clearly is a modified version of SubSet Sum Problem.
The only challenge here is we need to collect a set of values where the subset will equal to the sum which is $1.
Dynamic Programmings gives :- O(n2)
Ugly, but working code.
Result: all possible combinations, combinations count = 292 for amount = 100 (1 dollar)
public Set<List<Integer>> allCombinations( int amount, int[]coins ){
Arrays.sort( coins );
int length = amount+1;
List<Set<List<Integer>>> combinations = new ArrayList<>( length );
Set<List<Integer>> emptyComb = new HashSet<>();
emptyComb.add( new ArrayList<Integer>() );
combinations.add(0, emptyComb);
for( int changeSum = 1; changeSum < length; changeSum++ ){
Set<List<Integer>> newComb = new HashSet<>();
for( int coin : coins ){
if( coin > changeSum ){
break;
}
int offset = changeSum-coin;
Set<List<Integer>> offsetComb = combinations.get(offset);
for( List<Integer> prevComb : offsetComb ){
List<Integer> prevCopy = new ArrayList<>();
prevCopy.add( coin );
prevCopy.addAll(prevComb);
Collections.sort( prevCopy );
newComb.add( prevCopy );
}
}
combinations.add(changeSum, newComb);
}
return combinations.get( length-1 );
}
Using recursion we can find all possible ways to sum up to a dollar.
Code:
public void count_ways(int N, int i, int arr[], int t[]) {
if (N == 0) {
print(t, arr, i);
return;
}
if (i == arr.length)
return;
for (int j = 0; j * arr[i] <= N; j++) {
{
t[i] = arr[i] * j;
count_ways(N - t[i], i + 1, arr, t);
}
}
}
public void print(int t[], int a[], int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + "*" + t[i] / a[i] + " ");
System.out.println();
}
Invocation:
int a[] = { 1, 5, 10, 25, 50 };
int val = 100;
int t[] = new int[a.length];
count_ways(val, 0, a, t);
Using recursion we can find all possible ways to sum up to a dollar.
Code:
public void count_ways(int N, int i, int arr[], int t[]) {
if (N == 0) {
print(t, arr, i);
return;
}
if (i == arr.length)
return;
for (int j = 0; j * arr[i] <= N; j++) {
{
t[i] = arr[i] * j;
count_ways(N - t[i], i + 1, arr, t);
}
}
}
public void print(int t[], int a[], int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + "*" + t[i] / a[i] + " ");
System.out.println();
}
Invocation:
int a[] = { 1, 5, 10, 25, 50 };
int val = 100;
int t[] = new int[a.length];
count_ways(val, 0, a, t);
I'm no computer scientist, but I don't think this problem can be considered to be the same as the subset sum or knapsack problems, because the result set is not a subset of the input set. In any case, it is actually quite simple to solve using recursion with a running time approximately equal to the number of valid coin combinations (292) by using 2 optimizations:
1) sort the coins in descending order
2) when processing the last coin in the combo (i.e. deepest recursion level), realize that there is only 0 or 1 valid combo left.
For arbitrary sets of coins and sum (e.g. {3,7,11,13} and 103), the running time can be worse and some memoization of hasValidCombo(offset,sum) might be able to help. This requires more thought.
Code:
import java.util.ArrayList;
import java.util.Arrays;
public class YahooCoinCombos {
public static void main(String[] args) {
int coins[] = new int[] {1, 5, 10, 25, 50};
//int coins[] = new int[] {3, 7, 11, 13, 17};
dump(coins, findCombos(coins, 100));
}
static void dump(int coins[], ArrayList<int[]> comboList) {
System.out.println("Found " + comboList.size() + " combinations");
for (int[] combo : comboList) {
int sum = 0;
for (int i = 0; i < combo.length; ++i) {
if (i != 0) {
System.out.print(" + ");
}
System.out.print(combo[i] + "*" + coins[i]);
sum += combo[i] * coins[i];
}
System.out.print(" = " + sum + "\n");
}
}
static ArrayList<int[]> findCombos(int coins[], int sum) {
Arrays.sort(coins);
reverse(coins);
ArrayList<int[]> result = new ArrayList<int[]>();
int combo[] = new int[coins.length];
int iterations = findCombos(result, coins, combo, 0, sum);
System.out.println("iterations=" + iterations);
return result;
}
static void reverse(int a[]) {
int mid = a.length/2;
for (int i = 0; i < mid; ++i) {
swap(a, i, a.length - i - 1);
}
}
static void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static int findCombos(ArrayList<int[]> result, int coins[], int combo[], int offset, int sum) {
int iterations = 1;
if (sum == 0) {
int validCombo[] = new int[offset];
System.arraycopy(combo, 0, validCombo, 0, offset);
result.add(validCombo);
return iterations;
}
if (offset < coins.length - 1) {
for(int i = 0; ; ++i) {
if (sum < 0) {
return iterations;
}
combo[offset] = i;
iterations += findCombos(result, coins, combo, offset + 1, sum);
sum -= coins[offset];
}
}
else if (sum % coins[offset] == 0) {
combo[offset] = sum / coins[offset];
return findCombos(result, coins, combo, offset + 1, 0);
}
else {
return iterations;
}
}
}
I belive the answer this question is 193.
here is a code in java
class Foo{
public int[] coins ={1,5,10,25,50};
public static int countOfDollar = 0;
public void recurcive(int currentIndex,int countValue){
int iteration = 100/coins[currentIndex];
do {
countValue += coins[currentIndex] ;
if (countValue == 100) {
countOfDollar++;
}
if (currentIndex+1 < coins.length) {
recurcive(currentIndex+1,countValue);
}
--iteration;
} while (iteration >= 0);
}
public void getCountOfDollar(){
for (int i = 0; i < coins.length; i++) {
recurcive(i,0);
}
}
}
public void printPos(int sum, int type, int[] combination) throws Exception{
int nextType=0;
if(type ==100) nextType = 25;
else if (type ==25) nextType =10;
else if (type ==10) nextType =5;
else if (type ==5) nextType =1;
else if (type ==1){
combination[1] = sum;
System.out.println("Combination: ");
System.out.println(combination[100]);
System.out.println(combination[25]);
System.out.println(combination[10]);
System.out.println(combination[5]);
System.out.println(combination[1]);
return;
}
else throw new Exception();
for (int i=0;i*type<=sum;i++){
combination[type]=i;
printPos(sum-type*i,nextType,combination);
}
}
public void printPos(int sum, int type, int[] combination) throws Exception{
int nextType=0;
if(type ==100) nextType = 25;
else if (type ==25) nextType =10;
else if (type ==10) nextType =5;
else if (type ==5) nextType =1;
else if (type ==1){
combination[1] = sum;
System.out.println("Combination: ");
System.out.println(combination[100]);
System.out.println(combination[25]);
System.out.println(combination[10]);
System.out.println(combination[5]);
System.out.println(combination[1]);
return;
}
else throw new Exception();
for (int i=0;i*type<=sum;i++){
combination[type]=i;
printPos(sum-type*i,nextType,combination);
}
}
public static int makeChange3AndPrint(int n, int[] denoms, int k, String s)
{
if(k+1 >= denoms.length)
{
System.out.println(s+n + "*" + denoms[k] );
return 1;
}
int ways =0;
for(int j=0; j*denoms[k]<=n; j++)
{
ways+=makeChange3AndPrint(n-j*denoms[k], denoms, k+1, s+j + "*" + denoms[k] + " + ");
}
return ways;
}
public static void main(String[] args) {
int[] denoms = {50, 25, 10, 5, 1};
int n =100;
int c = makeChange3AndPrint(n, denoms, 0, n +"= ");
System.out.println("=========Total:" + c +"==================");
}
Classical coin change problem. O(n) DP solution.
- zahidbuet106 May 23, 2014