Yahoo Interview Question for Software Engineer / Developers






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

It is a straight forward dp.
int minCoins(int n){
if(n<0) return INF;
if(!n) return 0;
int &ans = dp[n];
if(ans!=-1) return ans;
ans = INF;
for(int i=0;i<no_coins;i++){
ans=min(ans,minCoins(n-coins[i])+1);
}
return ans;
}

- Anonymous September 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Straight forward greedy algorithm where DP would fail

- Radhika November 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a greedy approach is usually used

- chennavarri October 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't give your opinions, give a solution. If you think that greedy will be enough for this problem than please post the code, because i think it is solvable by DP.

- ibakar August 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ibajar. The same applies to u. Where is ur code for the solution witth DP
I think PMS works for u

- @chennavarri August 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// CoinDenomination.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<Windows.h>
#include<atlstr.h>
typedef struct _deno
{
	CString individualDeno;
	CString denominations;
	int cnt;
	_deno()
	{
		individualDeno = _T("");
		denominations = _T("");
		cnt = -1;
	}
}Deno;
int getMin(int n,int *denom,int denomcnt,int currentNum,Deno *denomidations)
{
	
	int min = n + 1;
	int cnt = -1;
	for(int i=0;i<denomcnt;i++)
	{
		if(denom[i] <= currentNum)
		{
			int x = currentNum % denom[i];
			int y = currentNum/denom[i];
			if(!x)
			{
				cnt = denomidations[denom[i]].cnt * y;
				if(cnt < min)
				{
					min = cnt;
				}
			}
			else
			{
				if((denomidations[x].cnt != -1) || (denomidations[x].cnt != -2))
				{
					cnt = denomidations[denom[i]].cnt * y + denomidations[x].cnt;
					if(cnt < min)
					{
						min = cnt;
					}
				}
			}
		}
	}
	denomidations[currentNum].cnt = min;

	return min;

}
int FunmindenomCnt(int n,int *denom,int denomcnt)
{
	Deno *denominations = new Deno[n];
	int minDenom;
	for(int i=0;i<denomcnt;i++)
	{
		denominations[denom[i]].cnt = 1;
	}
	for(int i=0;i<=n;i++)
	{
		if(i >= denom[0])
		{
			if(denominations[i].cnt != 1)
			{
				minDenom = getMin(denominations[i-1].cnt,denom,denomcnt,i,denominations);
				denominations[i].cnt = minDenom;
			}
		}
		else
		{
			denominations[i].cnt = -2;
		}
			
	}
	return minDenom;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3]={1,2,4};
	int mindenomCnt = FunmindenomCnt(7,arr,3);
	return 0;
}

- gopi.komanduri May 31, 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