Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
u can use that coin as many times u want. No restriction on number of times used a same coin.
U Dont need Dynamic programming then.
BIGGEST_DENOMINATION should be used maximum number of times
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int coins[] = {1,2,3,5,8,21,37,56};
int min_coins(int v)
{
int *mcoins = (int*)malloc(sizeof(int)*(v+1));
int *prev = (int*)malloc(sizeof(int)*(v+1));
memset(mcoins, 1<<7-1, sizeof(int)*(v+1));
memset(prev, 0, sizeof(int)*(v+1));
mcoins[0] = 0;
int i = 0, j = 0, tmp;
for(i = 1; i < v + 1; i++)
{
for(j = 0; i >= coins[j]; j++){
if((tmp = 1+mcoins[i-coins[j]]) < mcoins[i]){
mcoins[i] = tmp;
prev[i] = coins[j];
}
}
}
// final output
printf("%d", prev[v]);
i = v - prev[v];
while(prev[i] > 0){
printf("->%d", prev[i]);
i = i - prev[i];
}
return mcoins[v];
}
int main(){
min_coins(189);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int count( int a[], int m, int n )
{
int table[n+1],i,j,min;
memset(table, -1, sizeof(table));
table[0] = 0;
for(i=1; i<=n; i++)
{
min=INT_MAX;
for(j=0;j<m;j++)
{
if(a[j]<=i)
{
if(1+table[i-a[j]]<min)
{
min=1+table[i-a[j]];
}
}
}
if(min!=INT_MAX)
table[i]=min;
}
for(i=0;i<=n;i++)
printf("%d ",table[i]);
return table[n];
}
int main()
{
int arr[] = {5};
int m = sizeof(arr)/sizeof(arr[0]);
int n = 11;
printf(" %d ", count(arr, m, n));
return 0;
}
int[] a = {1,2,3,5,8,12,15,21,37,56};
int N = 100;
bool value = false;
int count = 0;
int testN = N;
for (int i = a.Length-1; i>=0; i--)
{
while (!value)
{
if (testN >= a[i])
{
count = count + testN / a[i];
testN = testN % a[i];
if (testN == 0)
{
break;
}
}
else
{
value = true;
}
}
value = false;
}
Console.WriteLine(count);
class Test{
public static void main(String []args){
int []coins={1,2,3,5,8,12,15,21,37,56};
int sum= 189;
int count =0;
int remainder=sum;
for(int i=coins.length-1;i>=0;i--){
count=count+(remainder-(remainder%coins[i]))/coins[i];
remainder=remainder%coins[i];
if(remainder==0){
System.out.println(count);
break;
}else if(remainder<coins[0]){
remainder = sum;
count=0;
}
}
}
}
Here is TC = O(n) solution
Have a Multiplier[] which keeps the multiplying factor
We have N denominations = {1,2,3,...,56} //here N=10
Given num = 189;
Algorithm :
for i=N-1 to 0
do
if num >= A[i]
{
Multiplier[N-i-1] = num/A[i] ;
num = A[i]*Multiplier[N-i-1] - num;
}
if num <= 0 then break;
}
So now Multiplier[] will have the factor by which the denominations to be multiplied and added up to get the reqd number.
189 = 3*56 + 1*21;
My solution below is a greedy approach calculating all the solutions and cacheing the latest optimal one. If current executing solution is already larger than chached solution abort the path. Note, for best performance denomination should be in decreasing order.
import java.util.ArrayList;
import java.util.List;
public class CoinDenomination {
int denomination[] = new int[]{50,33,21,2,1};
int minCoins=Integer.MAX_VALUE;
String path;
class Node{
public int coinValue;
public int amtRemaining;
public int solutionLength;
public String path="";
public List<Node> next;
public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
}
public List<Node> build(Node node)
{
if(node.amtRemaining==0)
{
if (minCoins>node.solutionLength) {
minCoins=node.solutionLength;
path=node.path;
}
return null;
}
if (node.solutionLength==minCoins) return null;
List<Node> nodes = new ArrayList<Node>();
for(int deno:denomination)
{
if(node.amtRemaining>=deno)
{
Node nextNode = new Node();
nextNode.amtRemaining=node.amtRemaining-deno;
nextNode.coinValue=deno;
nextNode.solutionLength=node.solutionLength+1;
nextNode.path=node.path+"->"+deno;
System.out.println(node);
nextNode.next = build(nextNode);
nodes.add(node);
}
}
return nodes;
}
public void start(int value)
{
Node root = new Node();
root.amtRemaining=value;
root.solutionLength=0;
root.path="start";
root.next=build(root);
System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
}
public static void main(String args[])
{
CoinDenomination coin = new CoinDenomination();
coin.start(35);
}
}
I think it can be acheived with complexity equal to the size of denominations. Here is the code
void min_coins(int n)
{
int coins[] = {1, 2, 3, 5, 8, 12, 15, 21, 37, 56};
int size, count, temp;
size = (sizeof(coins) / sizeof(coins[0])) - 1;
while (n && (size >=0)) {
temp = coins[size--];
if (n >= temp) {
count = n / temp;
n = n % temp;
printf("%d coins of %d \n", count, temp);
}
}
}
int selectCoinDenom(int* result, int amount)
{
int [] value = {1,2,3,5,8,12,15,21,37,56};
int denomSize = strlen(value);
int returnSize = 0;
int remainingAmnt = amount; // for e.g: 189
for(int i=(denomSize-1); i>=0; i--)
{
while(1)
{
if(remainingAmnt >= value[i])
{
remainingAmnt -= value[i];
result[returnSize] = value[i];
returnSize++;
}
else break;
}
if(remainingAmnt == 0)
break;
}
return returnSize;
}
This implementation should work fine. The array of denominations is sorted before using it. I have used int[] and StringBuilder as method arguments as a "hack" to pass by reference. This is greedy algorithm again which computes all possible solutions and picks the optimal one.
static int[] denoms = { 40, 14, 11, 1 };
public static void main(String[] args) {
quickSort(denoms, 0, denoms.length - 1);
int j = denoms.length;
TreeMap<Integer, String> resultmap = new TreeMap<Integer, String>();
while (j >= 0) {
int[] coincount = new int[1];
StringBuilder result = new StringBuilder();
if (findCoins(44, j--, coincount, result))
resultmap.put(coincount[0], result.toString());
}
if (!resultmap.isEmpty())
System.out.println(resultmap.get(resultmap.firstKey()));
}
private static boolean findCoins(int sum, int end, int[] coinCount,
StringBuilder result) {
int j = end - 1;
for (; j >= 0; j--) {
if (sum / denoms[j] > 0) {
// System.out.println(sum / denoms[j] + "->" + denoms[j]);
coinCount[0] += sum / denoms[j];
result .append("\n" + sum / denoms[j] + "->" + denoms[j]);
sum = sum % denoms[j];
if (sum == 0)
return true;
else {
if (findCoins(sum, j, coinCount, result))
return true;
else
break;
}
}
}
return false;
}
private static void quickSort(int[] a, int start, int end) {
int i = start, j = end;
int pivotval = a[(start + end) / 2];
while (i <= j) {
while (a[i] < pivotval)
i++;
while (a[j] > pivotval)
j--;
if (a[i] >= pivotval && a[j] <= pivotval) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i - 1 > start)
quickSort(a, start, i - 1);
if (i < end)
quickSort(a, i, end);
}
My apologies for overlooking the redundant recursion in the method.
private static boolean findCoins(int sum, int end, int[] coinCount,
StringBuilder result) {
int j = end - 1;
for (; j >= 0; j--) {
if (sum / denoms[j] > 0) {
// System.out.println(sum / denoms[j] + "->" + denoms[j]);
coinCount[0] += sum / denoms[j];
result .append("\n" + sum / denoms[j] + "->" + denoms[j]);
sum = sum % denoms[j];
if (sum == 0)
return true;
}
}
return false;
}
It can be solved using the dynamic programming or recursion.. Here is the code for DP,
public int minCoins(int n, int[] denominations) {
int[] dp = new int[n + 1];
dp[1] = 0;
for (int i = 2, len = dp.length; i < len; i++) {
int minValue = 1 + dp[i - 1];
//find minValue
for (int j = 0; j < denominations.length; j++) {
if (i > denominations[j]) {
minValue = min(minValue, 1 + (dp[i - denominations[j]]));
}
}
dp[i] = minValue;
}
return dp[n];
}
@ramakrishna: Your code has some silly errors, I edited it, point me out if I left something..
#include<iostream>
using namespace std;
int main()
{
int denominations[10]={1,2,3,5,8,12,15,21,6,56};
int n=189;
int dp[n+1];
dp[0] = 0;
for (int i = 1, len = n+1; i <= len; i++)
{
int minValue = 1 + dp[i - 1];
for (int j = 0; j < 10; j++)
{
if (i >= denominations[j])
{
minValue = min(minValue, 1 + (dp[i - denominations[j]]));
}
}
dp[i] = minValue;
}
cout << dp[n] << endl;
system("pause");
return 0;
}
@everyone
I really wonder if this method would work if we don't have 1 in the denominations array.
@ramakrishna: Your code has some silly errors, I edited it, point me out if I left something..
#include<iostream>
using namespace std;
int main()
{
int denominations[10]={1,2,3,5,8,12,15,21,6,56};
int n=189;
int dp[n+1];
dp[0] = 0;
for (int i = 1, len = n+1; i <= len; i++)
{
int minValue = 1 + dp[i - 1];
for (int j = 0; j < 10; j++)
{
if (i >= denominations[j])
{
minValue = min(minValue, 1 + (dp[i - denominations[j]]));
}
}
dp[i] = minValue;
}
cout << dp[n] << endl;
system("pause");
return 0;
}
@everyone
I really wonder if this method would work if we don't have 1 in the denominations array.
public static void change_coins(int [] denomination,int n){
int [] a = new int [n+1];
LinkedList<Integer>[] l = new LinkedList[n+1];
for(int i=0;i<l.length;i++){
l[i] = new LinkedList<Integer>();
}
for(int i=0;i<a.length;i++){
a[i] = Integer.MAX_VALUE;
}
a[0]=0;
HashSet<Integer> set = new HashSet<Integer>();
for(int i:denomination){
set.add(i);
}
for(int i=1;i<a.length;i++){
if(is_in_list(set, i)){
a[i] = 1;
l[i].add(i);
continue;
}
int m = Integer.MAX_VALUE;
int indexJ = 1;
boolean change = false;
for(int j=1;j<i;j++){
if(a[j]+a[i-j] < m ){
m = a[j]+a[i-j];
indexJ = j;
change = true;
}
}
a[i] = m;
if(change){
for(int c:l[indexJ]){
l[i].add(c);
}
for(int c:l[i-indexJ]){
l[i].add(c);
}
}
}
System.out.println(l[n].toArray().length+":"+Arrays.toString(l[n].toArray()));
}
private static boolean is_in_list(Set<Integer> set,int x){
if(set.contains(x)){
return true;
}
return false;
}
1 .First reverse Sort the denominations array
2. Then keep subtracting from amount , the highest denomination till amount < denomination.
3. Repeat loop for lesser denominations until amount hits zero.
Java code :
public class CoinDenominations {
public static void main(String []args)
{
int amount = 189;
int []denominations = {1,2,3,5,8,12,15,21,37,56};
new CoinDenominations().displayOutput(amount,denominations);
}
public void displayOutput(int amount,int [] denominations)
{
reverseSort(denominations);
for(int i = 0;i < denominations.length && amount > 0;i++)
{
while(amount - denominations[i] >= 0)
{
System.out.print(denominations[i] + "->");
amount -= denominations[i];
}
}
}
public void reverseSort(int []array)
{
for(int i = 0;i < array.length;i++)
{
for(int j = 0;j < array.length - i - 1;j++)
{
if(array[j] < array[j+1])
{
swap(array,j,j+1);
}
}
}
}
public void swap(int []array,int x,int y)
{
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
testcase : sum = 42. denomination array = {40,3}.
as per u'r algo, it shows that it is not possible. but ans is 14*3= 42.
You can solve it using Dynamic Programming. Specifically, given the sum p to be obtained using n coins you need to calculate the
- Anonymous November 14, 2012C(p) = min_{i<=p}(C(p-i))+1 // here i<=p is in fact value of a given coin in the input array a i.e., a[i]<=p
the time complexity is in the order of O(p*n) where n is the size of the input coins and p is the sum to be obtained.