Amazon Interview Question
AnalystsTeam: asdd
Country: India
Interview Type: In-Person
void getmin(int sum,int a[],int n,int count,int *min)
{
if(n==0 || sum<0)
return;
if(sum==0)
{
if(count<*min)
*min=count;
return;
}
if(sum>=a[n-1])
getmin(sum-a[n-1],a,n,count+1,min);
getmin(sum,a,n-1,count,min);
}
I think this would work if you were only allowed to use 1 of each coin, but the question says you can use one coin multiple times. So I think this algo would work if you expanded the coin set to contain X number of each denomination where x = sum div denom. The exploded set would then be {1,1,1,1,1,1,1,1,1,1,1,3,3,3,5,5} and I think your algo would return the correct result.
boolean vis[][];
int din[][];
int getMin( int position, int A[], int sum){
if( position == A.length || sum < 0 ) return (1<<22);
if( sum == 0) return 0;
if( vis[position][ sum ] == true) return din[ position ][ sum ];
vis[ position ][ sum ] = true;
din[position][ sum ] = (1<<22);
if( A[ position ] > 0 ){
din[position][ sum ] = Math.min( din[ position][sum], getMin( position , sum - A[ position ]) + 1);
}
din[ position ][ sum ] = Math.min( din[position][sum], getMin( position + 1, sum ) );
return din[ position ][ sum ];
}
int solve( int []A, int S){
vis = new boolean[ A.length ][ S + 1];
din = new int[A.length][ S +1];
int res = getMin( 0, A, S);
return ( res >= (1<<22) ) ? -1 : res;
}
boolean vis[][];
int din[][];
final static int INF = 1000000000;
int getMin( int position, int A[], int sum){
if( position == A.length || sum < 0 ) return INF;
if( sum == 0) return 0;
if( vis[position][ sum ] == true) return din[ position ][ sum ];
vis[ position ][ sum ] = true;
din[position][ sum ] = INF;
if( A[ position ] > 0 ){
din[position][ sum ] = Math.min( din[ position][sum], getMin( position , sum - A[ position ]) + 1);
}
din[ position ][ sum ] = Math.min( din[position][sum], getMin( position + 1, sum ) );
return din[ position ][ sum ];
}
int solve( int []A, int S){
vis = new boolean[ A.length ][ S + 1];
din = new int[A.length][ S +1];
int res = getMin( 0, A, S);
return ( res >= INF ) ? -1 : res;
}
another way to ge it:
import java.util.*;
class Main{
public static void main(String arg[]){
Scanner scan = new Scanner(System.in);
int size;
while( (size = scan.nextInt()) != 0 ) {
int sum = scan.nextInt();
int []input = new int[ size ];
for( int x = 0; x < size; x++) input[ x ] = scan.nextInt();
System.out.println( "" + ( (new Main()).solve( input , sum ) ) ) ;
}
}
class SumInformation{
private Integer sum;
private Integer distance;
private Integer operation;
public SumInformation( int sum, int distance, int operation){
this.sum = sum;
this.distance = distance;
this.operation = operation;
}
public int getDistance(){
return this.distance;
}
public int getSum(){
return this.sum;
}
public int getOperation(){
return this.operation;
}
}
public int solve( int A[], int S){
Queue<Integer> queue = new LinkedList<Integer>();
HashMap<Integer, SumInformation> hashInformation = new HashMap<Integer, SumInformation>();
queue.add( S );
hashInformation.put( S, new SumInformation( S, 0, 0 ));
while( !queue.isEmpty() ) {
Integer sum = queue.poll();
Integer distance = hashInformation.get( sum).getDistance();
if( sum == 0 ) {
while( sum != S ) {
Integer operation = hashInformation.get( sum).getOperation();
System.out.println(" " + sum + " previous operation " + (-operation));
sum += -operation;
}
return distance;
}
for( int position = 0; position < A.length; position++){
int sign = -1;
Integer sumtmp = sum + sign * A[ position ];
SumInformation inf = hashInformation.get( sumtmp );
if( sumtmp < 0 ) continue;
if( inf != null ) continue;
hashInformation.put( sumtmp , new SumInformation( sumtmp, distance + 1, sign * A[ position ] ) );
queue.add( sumtmp);
}
}
return -1;
}
}
void minCoinReq(int reqSum)
{
int arr[] = {5,3,1};
int coinCntArr[4]={0,0,0};
int k=0;
while(reqSum)
{
while(reqSum>=arr[k])
{
reqSum = reqSum -arr[k];
coinCntArr[k]=coinCntArr[k]+1;
}
k++;
}
for(int t=0;t<4;t++)
cout << "\n In func coins used are "<< coinCntArr[t] << " : "<< arr[t];
return ;
}
I think the most efficient you can get is an O(N Log N) solution:
-Sort the array (E.g, After sorting our array is {1,3,5}
Repeat the following:
- Starting from the end, find the next smallest number A < S(5 in this case)
- Multiple A as many times as possible till its becomes > S (5 * 3 > 11 so we'll save 2)
- Subtract this from the sum and repeat (11 - 5*2 = 1)
Run time = Sorting array + Walking it once = NLog(N) + N = N Log (N)
Hi punnet.sochi, I think your idea is great but if we have this input
A = {2 , 4}
and the sum = 5
you find 4 , and then 5 - 4 = 1 , but you don't have any 1.
Your idea work well if they use as a input the first kth fibonacci number , or something like that.
Best regards.
Thanks for the inputs Rodrigo. My algo needs a little correction.
If no match found i.e. if we reach end of array and no number found < sum,
return -1
A={2,4}
Find smallest # < S, this would be 4. Now, S = 5 - 4*1 = 1
Find smallest # < S, no number found and we reach end of array, so return -1.
Your welcome, try with this input
A= {2, 3, 4}
sum = 5
I think is necessary use a dynamic programming or best first search to find all possibilities.
Good look!
Even with this input {2,3,4 }, my algo will still return -1 (if we're searching for 5), which is the correct answer.
I see your point, but I don't think its necessary to run through all the inputs?
I think the correct answer is 3 + 2 = 5.
May be exist another way to find a correct solution.
Good look!
Algorithm:
1) Check if the largest element is divisible. return with count + currentresult
2) If not remove the largest element and loop through the rest of the elements. If the sum is completely divisible then check the totalCountResult. If it is greater than currentResult+count replace. Do not RETURN.
3) recurse with the smaller set and sum being the remainder value and count being the result .
PS: I know this is for array. we can sort the array but i have used TreeSet here because all the Integers are ordered and improves time performance. Best case complexity of this is O(1) worst case O(nlogn).
Here is some Java code:
public int numofcoins = -1;
public int counter = 0;
public static void main(String[] args)
{
Try thisClass = new Try();
TreeSet<Integer> denominations = new TreeSet<Integer>(
Collections.reverseOrder());
denominations.add(5);
denominations.add(13);
denominations.add(2);
thisClass.getmin(denominations, 102, 0);
System.out.println(thisClass.numofcoins);
System.out.println(thisClass.counter);
}
public void getmin(TreeSet<Integer> deno, int sum, int count)
{
this.counter +=1;
float currResult = -1;
float firstCurrResult = -1;
int firstElement = deno.first();
firstCurrResult = (float) sum / firstElement;
float firstRemainder = firstCurrResult - sum / firstElement;
if (firstRemainder == 0)
{
if (numofcoins == -1
|| ((int) (firstCurrResult + count) < numofcoins))
{
numofcoins = (int) (firstCurrResult + count);
return;
}
}
else
{
deno.remove(firstElement);
if (deno != null && !deno.isEmpty())
{
for (Integer i : deno)
{
currResult = (float) sum / i;
float remainder = currResult - sum / i;
if (remainder == 0)
{
if (numofcoins == -1
|| ((int) (currResult + count) < numofcoins))
{
numofcoins = (int) (currResult + count);
}
}
}
getmin(deno, Math.round(firstRemainder * firstElement), count + sum / firstElement);
}
else
{
return;
}
}
}
Below code is of O(nlogn) efficiency using the divide and mod operator. (assumption coin array is sorted descending order)
void minCoinReq(int reqSum)
{
int arr[] = {5,3,1};
int coinCntArr[4]={0,0,0};
int k=0;
while(reqSum)
{
coinCntArr[k]=( reqSum)/arr[k];
reqSum = reqSum %arr[k];
k++;
if(reqSum !=1 && reqSum!=0)
continue;
else if(arr[k]==1)
coinCntArr[k]= reqSum/arr[k];
}
}
private static Map<Integer,Integer> memoization = new HashMap<Integer,Integer>();
public int minCoint(int[] coinDenominations,int sum){
if(sum==0){
return 0;
}
if(coinDenominations.length==0){
return 0;
}
List<Integer> current = new ArrayList<Integer>();
for(int i=0;i<coinDenominations.length;i++){
if(sum>=coinDenominations[i]){
int sum2 = sum-coinDenominations[i];
if(memoization.containsKey(sum2)){
current.add(i, memoization.get(sum2));
}else{
current.add(i,minCoint(coinDenominations, sum2));
}
}
}
int min = min(current);
memoization.put(sum, min+1);
return min+1;
}
class Solution
{
public:
int GetMinCoins(vector<int>& coins, int Sum)
{
if(Sum <= 0) return 0;
vector<int> lvdp(Sum + 1, INT_MAX);
lvdp[0] = 0;
hGetMinCoins(coins, Sum, lvdp);
return lvdp[Sum] == INT_MAX? -1: lvdp[Sum];
}
void hGetMinCoins(vector<int>& coins, int leftSum, vector<int>& ovdp)
{
if(ovdp[leftSum] != INT_MAX) return;
for(int i = 0; i< coins.size(); i++)
{
if(leftSum >= coins[i])
{
hGetMinCoins(coins, leftSum - coins[i], ovdp);
if(ovdp[leftSum - coins[i]] < INT_MAX)
ovdp[leftSum] = min(ovdp[leftSum], ovdp[leftSum - coins[i]] + 1);
}
}
}
};
#include<stdio.h>
int main()
{
int input_data = 0;
int five_coins = 0 , three_coins = 0 , one_coins = 0;
int remained_data = 0 ;
int total_coins = 0 ;
printf("\nEnter input value : ");
scanf("%d",&input_data);
if( input_data <= 0 )
{
printf("\nCan not use any coin dimentions .... !!\n");
exit(0);
}
printf("\nCoin dimentions are {1,3,5}");
five_coins = input_data / 5 ;
remained_data = input_data % 5;
three_coins = remained_data / 3;
remained_data = remained_data % 3;
one_coins = remained_data / 1;
total_coins = five_coins + three_coins + one_coins ;
printf("\nFor %d we need coin dimentions of {1,3,5} as --- > %d(1) ; %d(3) ; %d(5) \n",input_data,one_coins,three_coins,five_coins);
printf("\nTotal number of coins we require are : %d\n",total_coins);
return 0;
}
The solution to the problem is the same as the unbounded knapsack problem and can be solved in pseudo polynomial time.
- Brave Heart April 06, 2014