Amazon Interview Question
SDE-2sCountry: India
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.
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.
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.
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.