Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
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.
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)
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
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.
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!
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()];
}
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 :)
/*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;
}
}
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;
}
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];
}
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;
}
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;
}
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);
}
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);
}
}
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.
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]
#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;
}
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) );
}
}
#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
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
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
dp
}
- Scott February 18, 2014