Amazon Interview Question for Software Engineers


Team: none
Country: United States
Interview Type: Phone Interview




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

DFS. Take quantity from 0 to q_i. Check price limit. Generate result.

- Anonymous October 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS. Take price from 0 to q_i. Check price limit. Generate result.

- Yurii_Yavorskyi October 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS. Take quantity from 0 to q_i. Check price limits. Generate results.

- Yavorsky.Yuriy October 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Chaitanya Srikakolapu November 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- tariq July 02, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- tariq July 02, 2020 | 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