Yahoo Interview Question
Software Engineer / DevelopersDon'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.
// 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;
}
It is a straight forward dp.
- Anonymous September 13, 2010int 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;
}