Amazon Interview Question SDE-2s
Country: India
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
is this a multiple set cover problem ? I mean, acc. to it we would need a subset of items (in the cart) such that the union equals to total number of sellers. That said, we may exclude some items in the cart.
Comment hidden because of low score. Click to expand.
0
of 0 votes
It can be a set cover problem if our universe={P1, P2, ..., Pn} and we turn the product/seller mappings over so that 1={P1}, 2={P1, P2}, ... Then we can find the minimum sellers to cover the product universe.
Not many products and sellers so probably just make it a simple combinatoric problem saving only the minimum set of sellers.
Comment hidden because of low score. Click to expand.
1
of 1 vote
apply dynamic programming, find minimum number of sellers for just product sets of {P1, P2, P3, etc...}, then find minimum for sets of {(P1, P2), (P1, P3), etc...} using previously found values.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
This is minimum set cover problem, I think.
- ninhnnsoc February 26, 2015Each seller can "cover" a set of products.
We have to find the minimum number of sellers to cover all required products.
Minimum Set Cover is a NP-hard problem.
Thus, if we want to find optimal solution, heuristic should be used. Or transform it into an integer linear programming instance, then use ILP solver to solve.
If we want to find some approximated solution, greedy may work fine.