FastPrep
Problem · Union Find

Product Category Group Sizes

Learn this problem
● EasyAmazonFULLTIMEPHONE SCREEN
See Amazon hiring insights

Problem statement

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

productCategoryGroupSizes(products: String[], pairs: String[][]) → int[]

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

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.

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]
checking account