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 (adjacency list), find out the largest connected component on this graph.
1List<String> findRelatedProducts(List<List<String>> graph)
Note that the graph is transitive.
Examples
Example 1:
Input:
1var arr = [ 2 ["product1", "product2", "product3"], 3 ["product5", "product2"], 4 ["product6", "product7"], 5 ["product8", "product7"] 6]
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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.