Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
#include <stdio.h>
void findCoins(int *, int, int , int *);
int main()
{
int d[2] = {5,10}; //coin denomination
int c[2], i;
int amt;
printf("Enter the amt ");
scanf("%d", &amt);
findCoins(d, 2, amt, c);
for (i=0; i<2; i++){
printf("coin %d - deno %d\n",d[i],c[i]);
}
return 0;
}
/*
* The easiest way to approach the solution is to divide amt by the coin
* with the largest denomination (dn). Let us say the number is k1. Now,
* whatever remains must be divided again by dn-1 and so on. Thus k1+k2+...+kn
* will be the result we seek, the minimum number of coins with which the amount
* can be made.
* This approach is known as the Greedy approach to problem solving.
*/
void findCoins(int d[], int n, int amt, int c[])
{
int i = n-1;
while (amt > 0) {
c[i] = (amt/d[i]);
amt = amt - c[i]*d[i];
i = i-1;
if(-1 == i && 0 != amt) {
printf("Not Possible!!\n");
exit(-1);
}
}
while (i>=0) {
c[i] = 0;
i = i-1;
}
return;
}
here is the C# implementation, but I haven't developed any test case yet, :)
public static int SimpleDo(List<int> coins, int sum)
{
//build tree
CoinArrange2TreeNode parent,left, right, root,temp;
root = new CoinArrange2TreeNode(0) { Add = false, Sum = 0 };
Queue<CoinArrange2TreeNode> parents = new Queue<CoinArrange2TreeNode>();
parents.Enqueue(root);
for (int i = 0; i < coins.Count; i++)
{
while (parents.Count != 0)
{
parent = parents.Dequeue();
left = new CoinArrange2TreeNode(coins[i]) { Add = false, Parent = parent, Sum = parent.Sum };
right = new CoinArrange2TreeNode(coins[i]) { Add = true, Parent = parent, Sum = parent.Sum + coins[i] };
}
}
//search tree
parents.Clear();
parents.Enqueue(root);
int min = Int32.MaxValue;
while (parents.Count != 0)
{
temp = parents.Dequeue();
if (temp.Sum == sum && temp.Count < min)
{
min = temp.Count;
}
if (temp.Left != null)
{
parents.Enqueue(temp.Left);
}
if (temp.Right != null)
{
parents.Enqueue(temp.Right);
}
}
return min == Int32.MaxValue ? -1 : min;
}
class CoinArrange2TreeNode
{
public int Value { get; set; }
public bool Add { get; set; }
public int Sum { get; set; }
public int Count { get; set; }
public CoinArrange2TreeNode Parent { get; set; }
public CoinArrange2TreeNode Left { get; set; }
public CoinArrange2TreeNode Right { get; set; }
public CoinArrange2TreeNode(int v)
{
Value = v;
}
}
I tried very hard to write code. I couldn't even make a pseudo-code. It turned out to be a nightmare. But here's what I was thinking:
1. Consider the sum 11 first. See if it belongs to coin list.
Yes? return 1? No? proceed
2. Start the second degree distribution of the sum.
Example: Represent 11 as 10+1, 9+2, 8+3, 6+4, 5+5 etc.....
//We need to do this with help of an array.
Do all of those numbers in each of the above sum exist in coinList?
Yes? Return degree 2
No? Proceed to degree 3 sum representations below.
3. Start the third degree distribution of the sum.
Example: Represent 11 as 9+1+1, 8+2+1, 7+2+2, 6+3+2 etc...
Do all of those numbers in each of the above sum exist in coinList.
Yes? Return degree 3
No? Proceed to degree 4 sum representations below.
4. Repeat this procedure recursively until a match is found or return -1.
It turns out to be far more easy to give this textual explanation than translating this to code.
Your comments are welcome on this. Any suggestions?
int GetMinCount(int total, int* coins, int length)
{
int* counts = new int[total + 1];
counts[0] = 0;
const int MAX = 0x7FFFFFFF;
for(int i = 1; i <= total; ++ i)
{
int count = MAX;
for(int j = 0; j < length; ++ j)
{
if(i - coins[j] >= 0 && count > counts[i - coins[j]])
count = counts[i - coins[j]];
}
if(count < MAX)
counts[i] = count + 1;
else
counts[i] = MAX;
}
int minCount = counts[total];
delete[] counts;
return minCount;
}
public class Coins {
public static int countCoins(int sum, int[] arr,
HashMap<Integer, Integer> map) {
if (sum == 0)
return 0;
else if (sum < 0)
return -1;
else {
int minim = Integer.MAX_VALUE;
int minimOnPath = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(sum - arr[i]))
minimOnPath = 1 + map.get(sum - arr[i]);
else {
minimOnPath = 1 + countCoins(sum - arr[i], arr, map);
map.put(sum - arr[i], minimOnPath - 1);
}
if (minimOnPath > 0)
minim = Math.min(minim, minimOnPath);
}
if (minim != Integer.MAX_VALUE)
return minim;
else
return -1;
}
}
public static void main(String[] args) {
HashMap<Integer, Integer> mapValueCoins = new HashMap<>();
int[] coins = { 1, 3, 7 };
int sum = 22;
System.out.println(countCoins(sum, coins, mapValueCoins));
mapValueCoins = new HashMap<>();
int[] coins2 = { 5, 5, 5, 5, 5 };
sum = 11;
System.out.println(countCoins(sum, coins2, mapValueCoins));
mapValueCoins = new HashMap<>();
int[] coins3 = { 5, 5, 5, 5, 75 };
sum = 75;
System.out.println(countCoins(sum, coins3, mapValueCoins));
}
}
#define inf 9999
int main()
{
int a[]= {1,1,3,4};//{1,2,3,4,5};//{3,7};//{1,2,3};//{1,2,3,5,8,12,15,21,37,56};
int sum=6,p,min,indx,i,n=sizeof(a)/sizeof(a[0]);
int *c=new int[sum+1];
memset(c,0,sizeof(c)*(sum+1));
c[0]=0;
for(i=0;i<n;i++)
c[a[i]]=1; //c[a[i]]++; is better
printf("\n");
for(p=1;p<=sum;p++)
{
if(c[p]!=1) //include this if MINIMUM NUMBER OF COINS/WAYS is needed
{
min=inf;
indx=-1;
for(i=0;i<n;i++)
{
if(a[i]<=p)
{
if(c[p-a[i]]<min)
{
min=c[p-a[i]];
indx=p-a[i];
}
}
}
if(indx!=-1)
c[p]=c[indx]+1;
}
}
printf("%d\n",c[sum]);
delete [] c;
return 1;
}
int minimumCoins(int A[], int N, int s)
{
int total =0, count =0, i;
if(S== 0 && N == 0 && A.length() == 0)
return 1;
else if(S==0 || N==0 || A.length() == 0)
return -1;
else
{
while(N > -1)
{
if( total + A[N-1] < S)
{
count++;
total = total + A[N-1];
}
else if( total + A[N-1] == S)
{
count++;
break;
}
}
N--;
}
if(count == 0)
return -1;
else
return count;
}
Clear case of Dynamic Programming
- random September 14, 2013Recursive Fucntion : M(i,s)=min( M(i-1,s) , 1+M(i-1,s-v[i]) );
Where s denotes the sum of coins , i denotes current coin and v[i] denotes value of current coin .
Final Solution : M(N,S);
Complexity : O(N*S)