Amazon Interview Question for Analysts


Team: asdd
Country: India
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Nitin April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- johny418 April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- RodrigoBurgos April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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; 
}

- Rodrigo Burgos Dominguez April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
   }
}

- Rodrigo Burgos Dominguez April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ;
}

- Anonymous April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- puneet.sohi April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rodrigo Burgos Dominguez April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- puneet.sohi April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Rodrigo Burgos Dominguez April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- puneet.sohi April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the correct answer is 3 + 2 = 5.

May be exist another way to find a correct solution.

Good look!

- Rodrigo Burgos Dominguez April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(nlogn) is not possible. This is an NP-Hard problem.

- Anonymous April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Rodrigo and Anon, I agree with you guys. O(N Log N) is not possible. We will have to examine all the possibilities, so exponential run time.

- puneet.sohi April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
            }
            
        }
        
    }

- Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
		
	}

}

- Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Below code is of O(nlogn) efficiency using the divide and mod operator. (assumption coin array is sorted) {{{ 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]; } } - Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Below code is of O(nlogn) efficiency using the divide and mod operator. (assumption coin array is sorted) {{{ 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]; } } - Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
		
	}
}

- Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Anonymous April 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
			}
		}
	}
};

- suwei19870312 April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Rajesh June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

minimum number of coins to a required sum, can be done through DP right?

- bhreddy.222 September 13, 2014 | 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