FastPrep
Problem · Union Find

Product Category Group Sizes

● EasyAmazonFULLTIMEPHONE SCREEN
See Amazon hiring insights

You are given a list of products and a list of pairs. Each pair means the two products belong to the same category. Category membership is transitive: if product A is in the same category as B, and B is in the same category as C, then A and C are in the same category.

Return the size of every final category group, sorted in increasing order. The number of returned sizes is the number of final categories.

Function Description

Complete the function productCategoryGroupSizes in the editor.

productCategoryGroupSizes has the following parameters:

  1. String products[]: all product identifiers
  2. String pairs[][]: product pairs that belong to the same category

Returns

int[]: the sorted sizes of the final category groups

Examples
01 · Example 1
products = ["A", "B", "C", "D", "E"]
pairs = [["A", "B"], ["B", "C"], ["D", "E"]]
return = [2, 3]
A, B, and C form one category of size 3. D and E form one category of size 2.
02 · Example 2
products = ["p1", "p2", "p3", "p4"]
pairs = [["p1", "p2"]]
return = [1, 1, 2]
Products p3 and p4 are not paired with any other product, so each is its own category.
Constraints
  • Product identifiers are unique in products.
  • Each pair contains two valid product identifiers.
  • Category membership is transitive.
More Amazon problems
drafts saved locally
public int[] productCategoryGroupSizes(String[] products, String[][] pairs) {
  // write your code here
}
products["A", "B", "C", "D", "E"]
pairs[["A", "B"], ["B", "C"], ["D", "E"]]
expected[2, 3]
sign in to submit