Yahoo Interview Question for Applications Developers


Country: United States
Interview Type: Phone Interview




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

Classical coin change problem. O(n) DP solution.

public static int coinSum(final int[] coins, final int sum) {
        final int m = coins.length;
        final int[][] csTable = new int[sum + 1][m + 1];

        // base cases: if m == 0 then no solution for any sum
        for (int i = 0; i <= sum; i++) {
            csTable[i][0] = 0;
        }
        // base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
        for (int j = 0; j <= m; j++) {
            csTable[0][j] = 1;
        }

        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= m; j++) {
                // solutions excluding coins[j]
                final int s1 = csTable[i][j - 1];
                // solutions including coins[i]
                final int s2 = (i - coins[j - 1]) >= 0 ? csTable[i - coins[j - 1]][j] : 0;

                csTable[i][j] = s1 + s2;
            }
        }

        return csTable[sum][m];
    }

- zahidbuet106 May 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- hprem991 April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n^2)?
And what is n?

- J. April 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

hint : Array ={ 1,5,10,25,50} Sum = 100

- Algorithms_99 April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- m@}{ April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

use DP to solve this coin change problem.

- zahidbuet106 May 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Dhass April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This can be optimized 2 ways:

1) Sort the coins in descending order
2) When processing the last and smallest coin (the penny), realize that the only valid multiplier is n / coin.

I will post code below.

- gudujarlson May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- gudujarlson May 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Naveen Muthy May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- coding101 July 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- coding101 July 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 +"==================");
	}

- jagdish July 18, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More