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.

List<String> findRelatedProducts(List<List<String>> graph)

Note that 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