Amazon Interview Question for SDE-2s


Country: India
Interview Type: Written Test




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

dp

public static int canBuyPack(int [] packs , int n){
		  boolean [] dp = new boolean [n+1];
		  dp [0] = true ;
		  for (int i = 0 ;i < packs.length ;++i){
			  for (int j = packs[i] ; j <=n ;++j){
				  if (dp[j - packs[i]]){
					  dp [j] = true;
				  }
			  }
		  }
		  
		  return  dp [n]? 1 : 0;

}

- Scott February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

which algorithms you are following??

- anoynmous February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you approach this solution??

- meyer February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi there. It is a dynamic programming based solution. The idea here is pretty simple.
n = 0 is true, the algorithm tries to do something similar to the sieve of Eratosthenes. If the current number is say x and the current factor in consideration is say 9, we know that x can be represented if x - 9 can be represented.

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

Solution seems to be correct and perfect.
Time complexity: O(m*n) if m<<n then O(n), Space complexity: n bits=n/8 byte = is almost equal to O(n)

- Sana February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

dynamic programming , find a subset add a pack which equals to N.

- Scott February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In python

def canBuyPack(packs,n):
        dp = [0] * (int(n)+1)
        dp[0] = True
        n = int(n)
        for i in packs.split(","):
                i = int(i)
                j = i
                while j <=n:
                        print str(j) + str(" ") + str(i)
                        if dp[int(j) - int(i)] == True:
                                dp[j] = True;
                        j += 1
        if dp[n] == True:
                return True
        else:
                return False

- aka February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I couldn't fathom how this works from the code itself, so I ran it in Eclipse. It always returns 1, not matter what.

- Runner October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

this problem can be solved in constant time.

the trick is to note that, if there is a solution, there would be a solution in which the number of 9s is either 0 or 1, and the number of 20s will be 0, 1, or 2. the rest will be all 6s.

reason: any set of three 20s can be substituted by 10 of 6s. any two 9s can be substituted by three 6s.

so, we consider the six cases of 0-1 pack of 9s and 0-2 pack of 20s and see if the rest is divisable by 6.

o(1) time o(1) space.

- vingard March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

and moreover as 3*9-1*(20+6) = 1 (either see it or use extended euclidean algorithm)
you can start with
6*(20+6) = 156
6*(20+6) + 3*9 - 1*(20+6) = 157
6*(20+6) + 6*9 - 2*(20+6) = 158
6*(20+6) + 9*9 - 3*(20+6) = 159
6*(20+6) + 12*9 - 4*(20+6) = 160
6*(20+6) + 15*9 - 5*(20+6) = 161

and obviously all other sizes will be also possible as 156+6=162, 157+6=163 and so on

so you only need to calculate solutions untill 156 at most!

- Markus March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use dynamic programming.

Given N packs and M items (N=3 and M=21 in the above example),
construct a boolean matrix A of size (N+1, M+1). A[i][j] is true if A[i][j-1] is true or
A[i-packs[k]][j] is true for any k \in N

The solution takes O(N^2M) time O(NM) space

bool shoekeeper(int N, const vector<int> &packs) {
	if( N==0 ) return true;
	if( packs.empty() ) return false;
	
	/* M[i][j] = true if i is true using items packs(0...j) */
	/* i=[0...N] j=[0...packs.size()] */
	vector<vector<int> > A(N+1, vector<int>(packs.size()+1,false));
	
	/* always true when i==0 */
	for(int j=0; j<=packs.size(); j++)
		A[0][j] = true;

	/* Dynamic Programming */
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=packs.size(); j++) {
			/* always true if we can sell N shoes without j'th pack */
			if( A[i][j-1] ) { A[i][j]=true; continue; }
			/* true if we can sell N shoes by adding k'th pack */
			for(int k=0; k<j; k++) {
				if( packs[k]<=i )
					A[i][j] = A[i][j] || A[i-packs[k]][j];
			}
		}
	}

	return A[N][packs.size()];
}

- mombasa February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have a doubt on this .......
j is represented to state whether the individual DP has j types of packs
so in the Table that we are constructing , when we say
A[i][j] = true if A[i-packs[k]][j] is true
shouldn't k be iterated over all the pack sizes to check ?

I mean for the same problem above if let's say n = 80
and packs[]={6,9,20}
then A[80][1] should be true , because we can solve this problem by taking packs of 20's
but when i try to check for A[80 - pack[0]][1] , or A[80-pack[1]][1] it will fail
beacuse i did not require pack's of six or nine

So essentially what I'm saying is that , in the for loop of k , the limit should be pack.size() and not j ;;

Correct me if I'm wrong !!!!!!
and if I'm right , happy to help :)

- crackyCoder February 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Shopkeeper want sells in the packs of 20,9 and 6. 
Given an n, you need to find whether its possible to buy the items or not.
For example n=21, you can buy 2 packs of 6 and one pack of 9(2*6 + 9) 
Output 1 if possible and 0 if not */

Test cases: 
1) n=47 ==> possible, output = 1 
2) n=7 ===> not possible, output = 0
class assign2
{
  public static void main(String[] x)
  {  int j=  calculate(x[0]);
        System.out.println(j);
  }
  public static int calculate(String str)
  {       int i=Integer.parseInt(str);
          int count6=0,count20=0,count9=0;
          count6=i/6;
           int n=i%6;
        if(n==0)
        {
           
		   return 1;
        }
        else
        {
           
            switch(n)
        {
            
            case 1: if(count6>8)
            {
              count6=count6-8;
              count20=2;
              count9=1;
              return 1;
           }
            else
            {
            return 0;
            }
           
            case 2:
              if(count6>3)
            {
              count6=count6-3;
              count20=1;count9=0;
              return 1;
            }
            else
            {
            return 0;
            }
           
            case 3:if(count6>1)
            {
               count6=count6-1;
               count9=1;
               count20=0;
                 return 1;
            }
              else
              {
              return 0;
              }
           
            case 4:
              if(count6>9)
            {
              count6=count6-9;
              count20=1;
              count9=0;
			  return 1;
            }
              else {return 0;}
           
              
            case 5:  if(count6>4)
            {
                     count6=count6-4;
                     count20=1;
                     count9=1;
                    return 1;
            }
            else
            {
                return 0;
            }
        }
     }
	 return 0;
}
}

- Abhishek Kumar February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not think it might work for 49 (2*20 + 9) :)

- Anonymous February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution. Little bit easier to understand.

bool shoekeeper(int N, int sum, const vector<int>& packs){
	if (sum > N)
		return false;
	else if (sum == N)
		return true;
	for (int i = 0; i < packs.size(); i++){
		if (shoekeeper(N, sum + packs[i], packs))
			return true;
	}
	return false;
}

- GK February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This does a lot of repeated work. One branch will add 20, and then add 9. while a different branch will add 9 and then add 20. Since addition is commutative, the two branches up to this point are the same!

- AC February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void check(N){
int N=21;
for (int i=0; i<=N/9+1; i++)
    for (int j=0; i<=N/6+1; i++)
        for (int k=0; i<=N/20+1; i++)
            if (i*9+j*6+k*20==N){
                cout<<i<<","<<j<<","<<k<<endl<<"Output: 1";
		return;
            }
cout<<"output: 0"<<endl;
}

- tester February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A python recursive solution:

def find(A, N):
	if len(A)==0 and N>0:
		return False
	if len(A)==0 and N==0:
		return True
	r=int(N/A[0])
	for i in range(r+1):
		if find(A[1:], N-i*A[0]):
			return True
	return False

print(find([20,9,6],21))

- samuel February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int canBuy(int n){
	vector<int> dp(n+1, 0);
	vector<int> packs{6,9,20};
	dp[0]=1;
	for(int i=0; i<=n; i++)
		for(vector<int>::iterator itr=packs.begin(); itr!=packs.end(); itr++){
			if(i-*itr < 0)
				break;
			if(dp[i-*itr] == 1)
				dp[i]=1;
		}
	return dp[n];
}

- me February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if (dp[i-*itr] == 1)  {
	db[i]=1;
	break;
}

- smallville March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A greedy approach O(n) time O(1) space :

int check(int n)
{
  int c6, c9, c20, rem9, rem20;
  for(c20 = n/20; c20; c20--)
  {
    rem20 = n - (20*c20);
    if(rem20%9 == 0)
      return 1;
    for(c9 = rem20/9; c9; c9--)
    {
      rem9 = rem20 - (9*c9);
      if(rem9%6 == 0)
        return 1;
    }
  }
  for(c9 = n/9; c9; c9--)
  {
    rem9 = n - (9*c9);
    if(rem9%6 == 0)
      return 1;
  }
  if(n%6 == 0)
    return 1;
  return 0;
}

- Anonymous February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please tell me if i'm right :)

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

iint check(int n)
{
if(n < 6) return 0;

if(n%3==0||n%20==0||n%9==0||n%6==0) return 1;

int c9, c20;
for(c20 = n; c20 < 0 ; c20-=20)
{
if(c20%9 == 0)
return 1;
for(c9 = c20; c9 < 0; c9-=9)
{
if(c9%6 == 0)
return 1;
}
}
return 0;
}

- prince February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

dp

public static int canBuyPack(int [] packs , int n){
		  boolean [] dp = new boolean [n+1];
		  dp [0] = true ;
		  for (int i = 0 ;i < packs.length ;++i){
			  for (int j = packs[i] ; j <=n ;++j){
				  if (dp[j - packs[i]]){
					  dp [j] = true;
				  }
			  }
		  }
		  
		  return  dp [n]? 1 : 0;

}

- Scott February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How did you approach this solution??

- red February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isFeasible(int[] items, int value) {

if(value < 0)

return false;

if(value == 0)

return true;

boolean total = false;

for(int i =0 ;i <items.length; i++) {
total |= isFeasible(items, value - items[i]);
}

return total;

}

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

This is not a general solution and only works in this case.
Coded in C/C++.

boolean canSell (int n) {
		
		if (n % 20 == 0)
			return true;

		while (n > 0) {
			if (n%6 == 0) 
				return true;

			if(n%6 == 3 && n > 3)	
				return true;
		
			n -= 20;
		}

		return false;
	}

- Alex L February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will below code work??

boolean canSell (int n) {
if(n < 6) return false;
if (n % 20 == 0)
return true;

while (n > 0) {
if (n%3 == 0)
return true;
n -= 20;
}

return false;
}

- Thomas February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple recursive solution . It is like a*pack1 + b*pack2 + c*pack3 = n .

Here is complete code

#include<stdio.h>

int comb(int pack1 , int pack2, int pack3, int prod_sum, int desired_sum)
{
	if(prod_sum == desired_sum)
		return 1;
	if(prod_sum > desired_sum)
		return 0;
		
	if(prod_sum < desired_sum)
		return(comb(pack1, pack2, pack3, prod_sum + pack1, desired_sum) 
				|| comb(pack1, pack2, pack3, prod_sum + pack2, desired_sum) 
				|| comb(pack1, pack2, pack3, prod_sum + pack3, desired_sum));
			
}

void main()
{
	int output = comb(20, 9, 6, 0, 47);
	printf("for 47 output is : %d\n", output);
	output = comb(20, 9, 6, 0, 7);
	printf("for 7 output is : %d\n", output);
}

- aditya kumar February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;

//shopkeeper wants to sell only in weights of 20,9 and 6

public class SetOfWeights {
	
	
	public void findWeights(int totWeight)
	{
		LinkedList<Integer> maxWeight=new LinkedList<Integer>();
		LinkedList<Integer> midWeight=new LinkedList<Integer>();
		LinkedList<Integer> minWeight=new LinkedList<Integer>();
		
		int weight1=20,weight2=9,weight3=6;
		
		int multiple=0;
	
		int i1=0;
		while(totWeight>multiple)
		{  
			maxWeight.add(multiple);
			i1++;
			multiple=weight1*i1;
		}
		multiple=0;i1=0;
		while(totWeight>multiple)
		{  
			midWeight.add(multiple);
			i1++;
			multiple=weight2*i1;
		}
		multiple=0;i1=0;
		while(totWeight>multiple)
		{  
			minWeight.add(multiple);
			i1++;
			multiple=weight3*i1;
		}
		
		//display();
		for(int i=0;i<maxWeight.size();i++)
		{
			for(int j=0;j<midWeight.size();j++)
			{
				
				for(int k=0;k<minWeight.size();k++)
				{
					int calc= maxWeight.get(i)+midWeight.get(j)+minWeight.get(k);
					if(calc==totWeight)
					{
						System.out.println("set equal to "+totWeight+"= {"+ weight1+"*"+maxWeight.get(i)/weight1+" , "+ weight2+"*"+ midWeight.get(j)/weight2+" , "+ weight3+"*"+ minWeight.get(k)/weight3 + "}");
					}
				}
			}
		}
	}

	

	public static void main(String[] args) {
		
		SetOfWeights sw=new SetOfWeights();
		sw.findWeights(47);
	}
}

- Ravi Kumar February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Many of the solution here used 3 for loops .. using them here is ok, because we know we have 3 options 20,9,6
What if we have large set of options then making that no of for loops will not be a good solution.


Better use recursion or backtracking algo:

Hint of backtracking ....
we should make logic which runs like:
20, 9, 6
20, 9, 6, 6 ... till this sum <= desired value
when all combination with one 20 and one 9 are over
then work for
20, 9 , 9 , 6
20, 9 , 9 , 6, 6 ...

and so on ... till we get valid sum or all over options get exhausted.

- Mohit February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A Python iterative solution with two loops. The solution has O(nm) runtime and O(n) space
complexity where

n: amount being tested
m: number of possible values for the packs

packs = [20, 9, 6]

def buy(max_value):
    # Initialize a matrix k columns and n lines
    # This means the base cases
    best_values = [0 for j in range(max_value+1)]
    best_values[0] = 1

    for value in range(1, max_value+1):
        for pack in packs:
            if value >= pack:
                if value - pack == 0 or best_values[value - pack] == 1:
                    best_values[value] = 1
            else:
                best_values[value] = 0
    return best_values[max_value]

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

#include<iostream>
using namespace std;
class M {
private:
int flag;
public:
M() {
flag=0;
}

void shoekeeper(int n) {
if (n==0) {
flag=1;
return;
} else {
if (n<0) {
return;
}
shoekeeper(n-20);
shoekeeper(n-9);
shoekeeper(n-6);
}
}


int getFlag() {
return flag;
}
};
int main() {
M n;
n.shoekeeper(7);
if (n.getFlag()) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
return 0;
}

- rashid February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;
public class Backtrack {

static Stack<Integer> stack= new Stack<Integer>();
static int[] options = {6, 9, 20};

public static boolean recurse(int remainder) {
if(remainder == 0) {
return true;
}
if(remainder < options[0]){
return false;
}

boolean value = false;
for(int i:options) {
stack.push(i);
value = recurse(remainder-i);
if(value)
break;
stack.pop();
}
return value;
}

public static void main(String[] args) {
System.out.println( recurse(47) );
System.out.println( recurse(7) );
}
}

- ChiP February 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<map>
using namespace std ;

int createOrder(const int iOrder, map<int,int> & iOrdertodelivered)
{
map<int,int> l_storedorder;
int l_order = iOrder;
int count20 = 0 ,count9 = 0 ,count6 = 0;
do{
// check it is multiple of gieven packs
if( (l_order%20 ) == 0)
{

count20 = count20+(l_order/20);
break;
}
if( (l_order%9) == 0)
{
count9 = count9+(l_order/9);
break;
}

if( (l_order%6) == 0)
{
count6 = count6+(l_order/6);
break;
}


// Now atart with 6 if it has reminder
if(l_order > 6 )
{
l_order = l_order -6;
count6++;
if(l_order > 9 )
{
l_order = l_order -9;
count9++;
if(l_order > 20)
{

l_order = l_order -20;
count20++;
}
}
}
else
{
return -1;
}

}while(1);

// fill the sequence
if(count20 > 0)
{
l_storedorder.insert(std::pair<int,int>(20,count20));
}
if(count9 >0 )
{
l_storedorder.insert(std::pair<int,int>(9,count9));
}
if(count6 > 0)
{
l_storedorder.insert(std::pair<int,int>(6,count6));
}
iOrdertodelivered = l_storedorder;
return 0;
}
int main(int argc, char *argv[])
{
int l_order =0;
map<int,int> l_storedorder;
cout<<"Enter order made to shopkeeper"<<endl;
cin>>l_order;

// Now shopker only deliver order in the form of 30 9 and 6 packs
cout<<"user ordered "<<l_order<<endl;

int rc = createOrder(l_order,l_storedorder);
if(rc == 0)
{
// print map to find order
cout<<" Order Successful : Breakup "<<endl;
std::map<int,int>::iterator it = l_storedorder.begin();
cout<<"Packs"<<" "<<"Quantity"<<endl;
for(;it != l_storedorder.end();++it)
{
cout<<" "<<it->first<<" "<<it->second<<endl;
}
}
else
{
cout<<"Invalid Order "<<endl;
}
return 0;
}

Result :

nitesh@nitesh-PC ~
# ./a
Enter order made to shopkeeper
21
user ordered 21
Order Successful : Breakup
Packs Quantity
6 2
9 1

nitesh@nitesh-PC ~
# ./a
Enter order made to shopkeeper
47
user ordered 47
Order Successful : Breakup
Packs Quantity
6 3
9 1
20 1

nitesh@nitesh-PC ~
# ./a
Enter order made to shopkeeper
47
user ordered 47
Order Successful : Breakup
Packs Quantity
6 3
9 1
20 1

- Nitesh February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x, y, z, n >= 0
20x + 9y + 6z = n
> 21x + 9y + 6z = n + x
> 7x + 3y + 2z = (n + x) / 3
because 3y + 2z >= 0 and <>1
So calculate x = 0, x = 1, x = 2
>
if (n+2) % 3 = 0, n >=40, n <> 43. return true
if (n+1) % 3 = 0, n >=20, n <> 23. return true
if n % 3 = 0, n <> 3. return true
other return false

- LiMingjie0719 March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def possible(number):
        number = int(number)
        print number
        if number == 0:
                return 1
        if number < 6:
                return 0
        if number%6 == 0 or number%9 == 0 or number%20 == 0:
                return 1
        if number >= 20:
                number = number - 20
                return possible(number%20)
        if number >= 9:
                number = number - 9
                return possible(number%9)
        if number >= 6:
                number = number - 6
                return possible(number%6)
        return 0

- aka February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will not work for number=53, which has a possible breakup 9*3+6*4=53

- smallville March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

53 is not equal to 9*3 + 6 * 4, it is 51

- bharath.paturi March 30, 2014 | Flag


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