Amazon Interview Question
Software EngineersTeam: none
Country: United States
Interview Type: Phone Interview
First converted List of items, quantity and prices into Product Objects using following class
public class Product {
public String name;
public int price;
public int quantity;
@Override
public boolean equals(Object obj) {
Product other = (Product)obj;
return this.name == other.name && this.price == other.price && this.quantity == other.quantity;
}
@Override
public int hashCode() {
int result = 31;
result +=name.hashCode();
result +=price;
result +=quantity;
return result;
}
@Override
public String toString() {
return "n:"+name+"-p:"+price+"-q:"+quantity;
}
}
Following getItemsList method will return possible items list(Cart objects)
Cart Class
public class Cart {
public Set<Product> items= new HashSet<>( );
@Override
public boolean equals(Object obj) {
Cart other = (Cart) obj;
if(this.items.size() != other.items.size()){
return false;
}else{
for(Product product:this.items){
if(!other.items.contains( product )){
return false;
}
}
}
return true;
}
@Override
public int hashCode() {
int result = 31;
for(Product product:items){
result += product.hashCode();
}
return result;
}
@Override
public String toString() {
return items.toString();
}
}
==============Actual Logic:================
private Set<Cart> getItemsList(List<Product> products, int totalOrder) {
Set<Cart> carts = new HashSet<>( );
for(int i=1;i<=products.size();i++){
carts.addAll(getItemsList( products,totalOrder, i ));
}
return carts;
}
private Set<Cart> getItemsList(List<Product> products,int totalOrder, int i) {
Set<Cart> carts = new HashSet<>( );
if(totalOrder <= 0){
return carts;
}
if(i == 1){
products.forEach( product -> {
if(totalOrder%product.price == 0){
Cart cart = new Cart();
Product p = new Product();
p.name = product.name;
p.price = product.price;
p.quantity = totalOrder/product.price;
if(p.quantity <= product.quantity) {
cart.items.add( p );
carts.add( cart );
}
}
} );
}else{
products.forEach( product -> {
List<Product> newProductList = new ArrayList<>( products );
newProductList.remove( product );
for(int quantity = 1 ;;quantity++){
Set<Cart> subCarts = getItemsList(newProductList, totalOrder-(quantity*product.price), i-1);
if(subCarts.size()>0){
Product p = new Product();
p.price = product.price;
p.name = product.name;
p.quantity = quantity;
subCarts.forEach( cart -> {
cart.items.add(p);
} );
carts.addAll( subCarts );
}else{
break;
}
}
});
}
return carts;
}
class Item {
public:
int id;
int price;
int quantity;
Item(int _id, int _p, int _q) : id(_id), price(_p), quantity(_q) { }
friend ostream& operator<<(ostream& os, const Item& item) {
os << item.id << " price " << item.price << " qu " << item.quantity << endl;
return os;
}
};
void selectItem (vector<Item>::iterator vecStart, vector<Item>::iterator vecEnd, int partialSum, int sum, int& ways) {
if (vecStart != vecEnd && partialSum < sum) {
auto it = vecStart;
for(int k = 1; k <= it->quantity; ++k) {
cout << *it;
auto price = it->price;
it++;
selectItem(it, vecEnd, partialSum + k*price, sum, ways);
it--;
}
} else {
if (partialSum == sum) {
ways++;
}
return;
}
};
int findTotalWays(vector<Item>& items, int sum) {
int ways = 0;
selectItem(items.begin(), items.end(), 0, sum, ways);
return ways;
}
class Item {
public:
int id;
int price;
int quantity;
Item(int _id, int _p, int _q) : id(_id), price(_p), quantity(_q) { }
friend ostream& operator<<(ostream& os, const Item& item) {
os << item.id << " price " << item.price << " qu " << item.quantity << endl;
return os;
}
};
void selectItem (vector<Item>::iterator vecStart, vector<Item>::iterator vecEnd, int partialSum, int sum, int& ways) {
if (vecStart != vecEnd && partialSum < sum) {
auto it = vecStart;
for(int k = 1; k <= it->quantity; ++k) {
cout << *it;
auto price = it->price;
it++;
selectItem(it, vecEnd, partialSum + k*price, sum, ways);
it--;
}
} else {
if (partialSum == sum) {
ways++;
}
return;
}
};
int findTotalWays(vector<Item>& items, int sum) {
int ways = 0;
selectItem(items.begin(), items.end(), 0, sum, ways);
return ways;
}
DFS. Take quantity from 0 to q_i. Check price limit. Generate result.
- Anonymous October 31, 2019