Amazon Online Assessment (OA) - Find Related Products
This question is based on the product recommendation system on the online shopping website.
Every time you open a product page on the website you can see a section "People who viewed this also viewed"
.
Now given a product relationship represented as a graph(adjacent list), find out the largest connected component on this graph.
List<String> findRelatedProducts(List<List<String>> graph)
Notice the graph is transitive.
Examples
Example 1:
Input:
var arr = [
["product1", "product2", "product3"],
["product5", "product2"],
["product6", "product7"],
["product8", "product7"]
]
Output: ["product1", "product2", "product3", "product5"]
Explanation:
First, we need to process the input and build the graph like this:
Here product1
has two recommendations: "product2", "product3"
product2
has one recommendation: "product5"
Put it together we have the largest recommendation component ["product1", "product2", "product3", "product5"]
.
Notice ["product6", "product7", "product8"]
is also a connected component but smaller than the previous one.
Try it yourself
Loading full content...