Yahoo Interview Question for Software Engineer / Developers


Country: United States




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

classical coin sum problem. DP solution. O(n).

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 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is the csTable the number of solutions or the number of coins?

if it is the number of solutions, then returning csTable[sum][m], in the end is wrong.

if it is the number of minimal coins then, this is wrong:
for (int j = 0; j <= m; j++) {
csTable[0][j] = 1;
}
and should be =0

- Yehuda August 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you misunderstood the question.

- addy October 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Study coin change problem from DP.

- Study DP February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

classical coin sum problem. DP solution. O(n).

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 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Famous min coin denomination problem. can be found on net.

private static void minCoinChange(int[] denom, int n) {

int[] s = new int[n+1];
int[] c = new int[n+1];

int size = denom.length;
s[0]=0;
c[0]=0;

int coin=1;

for(int p=1;p<=n;p++)
{
int min=Integer.MAX_VALUE;
for(int d=0;d<size;d++)
{
if(p>=denom[d])
{
if((1+c[p-denom[d]]) < min)
{
min = 1+c[p-denom[d]];
coin=denom[d];
}
}
}
s[p]=coin;
c[p]=min;
}

System.out.println("min coins: " + c[n]);

printMinCoinChange(c,s,n);
}

- Anonymous April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a dynamic programming problem.

Code:

#include <stdio.h>

void calc_min( int arr[],  int len, int sum ){

	int i=0;
	int j=0;
	int mat[len][sum+1];
	for( i=0; i<len; i++){
		for( j=0; j<=sum; j++){
			mat[i][j] = 99;
		}
	}

	for( j=0; j<=sum; j++ ){
		if( j==arr[0] )
			mat[0][j] = 1;
		else
			mat[0][j] = 99;
	}
	for( i=0; i<len; i++)
		mat[i][0] = 0;
	for( i=1; i<len; i++ ){
		for( j=1; j<=sum; j++ ){
			int x = 99;
			int y = 99;
			if(j-arr[i]>=0){
				x = 1 + mat[i-1][j-arr[i]];
			}
			y = mat[i-1][j];
			mat[i][j] = (x<y?x:y);
			printf("%d\t", mat[i][j]);
		}
	}
	printf("%d\n", mat[3][12]);
}

int main(void) {
	
	int arr[] = { 2,3,5,7 };
	int len = sizeof(arr) / sizeof(int);
	int sum = 12;
	calc_min( arr, len, sum );
	
	return 0;
}

Time complexity = O(sum*num_coins)
Space complexity = O(sum*num_coins)

- nharryp November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic Programming problem:

Code:

#include <stdio.h>

void calc_min( int arr[],  int len, int sum ){

	int i=0;
	int j=0;
	int mat[len][sum+1];
	for( i=0; i<len; i++){
		for( j=0; j<=sum; j++){
			mat[i][j] = 99;
		}
	}

	for( j=0; j<=sum; j++ ){
		if( j==arr[0] )
			mat[0][j] = 1;
		else
			mat[0][j] = 99;
	}
	for( i=0; i<len; i++)
		mat[i][0] = 0;
	for( i=1; i<len; i++ ){
		for( j=1; j<=sum; j++ ){
			int x = 99;
			int y = 99;
			if(j-arr[i]>=0){
				x = 1 + mat[i-1][j-arr[i]];
			}
			y = mat[i-1][j];
			mat[i][j] = (x<y?x:y);
			printf("%d\t", mat[i][j]);
		}
	}
	printf("%d\n", mat[3][12]);
}

int main(void) {
	
	int arr[] = { 2,3,5,7 };
	int len = sizeof(arr) / sizeof(int);
	int sum = 12;
	calc_min( arr, len, sum );
	
	return 0;
}

Complexity = O(no_of_coins*sum)

- nharryp November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This problem can entail to the partition problem. There is a pseudo polynomial time solution. Partition_problem as in Wikipedia.
Use S instead of N/2 in the solution.
Complexity: N*S

- Gourab Roy February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If I understand the problem correctly - this is a variant of the Knapsack01 problem where the goal is to find the maximum value with the minimum number of items. In other words, out of all possible combinations which result in the maximum value (in our case the maximum value is the sum), we want to find the one with the minimum number of items.

In the original Knapsack01 problem we define an array dp[number_of_coins+1][sum+1] and each array element dp[i][j] represents the maximum sum which can be achieved using the first i coins (without repetitions):
dp[i][j] = (j>=coin_value[i-1]) ? Max(dp[i-1][j-coin_value[i-1]+coin_value[i-1],dp[i-1][j]) : dp[i][j-1]

In order to calculate the minimum number of coins for the maximum sum, we'll store both the sum and the corresponding number of coins for each dp[i][j].
Now, whenever dp[i-1][j-coin_value[i-1]].sum() + coin_value[i-1] == dp[i-1][j].sum() we'll choose the value for dp[i][j] according to the minimum number of coins:
1. if dp[i-1][j-coin_value[i-1]].coins() + 1 < dp[i-1][j].coins() then
dp[i][j].coins dp[i-1][j-coin_value[i-1]].coins() + 1
2. Otherwise, dp[i][j].coins = dp[i-1][j].coins
3. For both (1) and (2), dp[i][j].sum = dp[i-1][j-coin_value[i-1]].sum() + coin_value[i-1] (it can also be dp[i-1][j] because both values are equal).

Basically, every time we need to decide between two equal maximum sums (one that includes the current coin and that doesn't) we choose the one which can be achieved with less coins according to dp[i][j].coins() value.

Here's an implementation of this idea (admittedly, I haven't tested it thoroughly):

private static class SumCoins {
		private int sum;
		private int coins;
		
		public SumCoins(int sum, int coins){
			this.sum = sum;
			this.coins = coins;
		}
		
		public int getSum(){return sum;}
		public int getCoins(){return coins;}
		public void setSum(int sum){this.sum = sum;}
		public void setCoins(int coins){this.coins = coins;}
	}

	public static int findMinimumCoins(int[] coins, int sum){
		if ((coins==null) || (sum<=0)){return 0;}
		
		SumCoins[][] dp = new SumCoins[coins.length+1][sum+1];
		for (int i=0;i<dp.length;i++){
			for (int j=0;j<dp[i].length;j++){
				dp[i][j] = new SumCoins(0,0);
			}
		}
		
		for (int i=1;i<dp.length;i++){
			for (int j=1;j<dp[i].length;j++){
				if (j>=coins[i-1]){
					if ((dp[i-1][j-coins[i-1]].getSum()+coins[i-1] > dp[i-1][j].getSum()) || 
					((dp[i-1][j-coins[i-1]].getSum()+coins[i-1] == dp[i-1][j].getSum()) &&
					(dp[i-1][j-coins[i-1]].getCoins()+1 < dp[i-1][j].getCoins()))){
						dp[i][j].setCoins(dp[i-1][j-coins[i-1]].getCoins()+1);
						dp[i][j].setSum(dp[i-1][j-coins[i-1]].getSum()+coins[i-1]);
					}
					else {
						dp[i][j].setCoins(dp[i-1][j].getCoins());
						dp[i][j].setSum(dp[i-1][j].getSum());
					}
				}
				else{
					dp[i][j].setCoins(dp[i][j-1].getCoins());
					dp[i][j].setSum(dp[i][j-1].getSum());
				}
			}
		}
		
		return dp[coins.length][sum].getCoins();
	}

Complexity: O(n*s) run-time and space complexity.

Note: If the sum cannot be reached using the given coins then the returned value in the code above would be the minimum number of coins for the closest value to sum which can be achieved using the input coins. Using dp[coins.length][sum].getSum() we can determine that value and decide what to do in this case.

- IvgenyNovo February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Greedy solution will not work in some cases.

If for e.g. if denominations are 1,2,4,5 and you want to make up 8, the greedy algorithm will return (5,2,1), the solution is (4,4).

We need dynamic programming solution.

N - total sum
d - number of coins
change[N+1] - stores change values of sum 1->N
Coins[d] stores coin values

N[0] = 0 //trivial problem with known solution

for i=1 to N do
  change[i] = N+1 // ideally infinity, but N+1 is also not possible so we can use it
  for j=d to 0 do
//     check if current coin is of lesser or equal value of curret sum
//     check if we we include the coin, and a best solution for number of coins lower value coin (sum-current_coin) +1 is lesser that current known value starting from N+1

    if(Coins[j]<=i and change[i-coins[j]]+1<change[i]) then
      change[i] = change[i-coins[j]]+1
    end if
  end for
end for

return 

//O(N*D)

- greedy_programmer February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

call the method, 
S - Sum,
A[] - Denominations
int mincoins =  makeChange(S,A.length-1, A);


	int makeChange(int amount, int index, int[] Denominations) {
		
		if ( amount <=0 ){
			return 0;
		}
		
		if ( amount >= Denominations[index]) {			
			return change(amount-Denominations[index], index, Denominations);
		} else{
			return change(amount, --index, Denominations);
		}		
		
	}

- beginner February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is incorrect. What happens when the denominations are [1, 10, 25] and S = 30? The correct answer is 3 (3 '10's), but this algorithm will return 5 ('25' and 5 '1's).

- alex May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

call the method as makeChange.
Input - S - Sum, A.length-1,  A[] - Denominations

int mincoins =  makeChange(S,A.length-1, A);


	int makeChange(int amount, int index, int[] Denominations) {
		
		if ( amount <=0 ){
			return 0;
		}
		
		if ( amount >= Denominations[index]) {			
			return makeChange(amount-Denominations[index], index, Denominations);
		} else{
			return makeChange(amount, --index, Denominations);
		}		
		
	}

- Anonymous February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Public int countNoOfCoins(int[] coins, int sum)
{
Arrays.sort(coins);
int count =0;
for(int index=coins.length-1;index>=0;index--)
{
if(sum>= coins[index])
{
sum=sum-a[index];
count++;
}
if(sum ==0)
return count;

}
return -1;

}

- Kannan February 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int countNoOfCoins(int[] coins, int sum) {
Arrays.sort(coins);
int count = 0;
for (int index = coins.length - 1; index >= 0; index--) {
if (sum >= coins[index]) {
sum = sum - coins[index];
count++;
}
if (sum == 0)
return count;
}
return -1;

}

- Kannan February 20, 2014 | Flag


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