Meesho Product Family Management
Meesho operates a vast e-commerce platform with an extensive product catalog. Efficiently managing product relationships is critical for various backend operations, including inventory optimization, supplier management, and targeted promotions. Products are often grouped into "families" due to shared manufacturing processes, design specifications, or supplier agreements. Understanding and dynamically tracking these product families allows Meesho to make informed decisions about sourcing, bundling, and logistics.
You are tasked with implementing a system to manage and query product families. Given an initial set of N products and a sequence of operations, your system should process these operations and provide results for specific queries. You need to ensure that operations like linking products and querying family information are performed efficiently.
Your function will receive the following parameters:
N: An integer representing the total number of products. Products are indexed from 0 to N-1.operations: An array of arrays, where each inner array represents an operation. There are three types of operations:
["LINK", p1, p2]: This operation signifies that product p1 and product p2 are now considered linked. If they were already part of different families, their families should merge. If they were already in the same family, this operation has no effect.["COUNT_FAMILIES"]: This operation requests the total number of distinct product families currently existing.["GET_FAMILY_SIZE", p]: This operation requests the total number of products within the family that product p belongs to.Your function should return an array of numbers. This array will contain the results of all "COUNT_FAMILIES" and "GET_FAMILY_SIZE" operations, in the order they appear in the operations input.
0 to N-1.LINK operations are idempotent. If two products are already in the same family, linking them again should not change the state or family count.Examples
Example 1
Input:
N = 5, operations = [["LINK", 0, 1], ["LINK", 2, 3], ["COUNT_FAMILIES"], ["GET_FAMILY_SIZE", 0], ["LINK", 0, 2], ["GET_FAMILY_SIZE", 3], ["COUNT_FAMILIES"]]
Output:
[3,2,4,2]
Note:
Initial state: 5 products, each in its own family. Total families = 5, all sizes = 1.
LINK 0, 1: Products 0 and 1 merge. Families: [0,1], [2], [3], [4]. Total families = 4.LINK 2, 3: Products 2 and 3 merge. Families: [0,1], [2,3], [4]. Total families = 3.COUNT_FAMILIES: Returns 3.GET_FAMILY_SIZE 0: Product 0 is in family [0,1] (size 2). Returns 2.LINK 0, 2: Products 0 (and its family [0,1]) merge with product 2 (and its family [2,3]). Families: [0,1,2,3], [4]. Total families = 2.GET_FAMILY_SIZE 3: Product 3 is in family [0,1,2,3] (size 4). Returns 4.COUNT_FAMILIES: Returns 2.Example 2
Input:
N = 3, operations = [["GET_FAMILY_SIZE", 1], ["LINK", 0, 1], ["LINK", 1, 2], ["COUNT_FAMILIES"], ["GET_FAMILY_SIZE", 0]]
Output:
[1,1,3]
Note:
Initial state: 3 products, each in its own family. Total families = 3, all sizes = 1.
GET_FAMILY_SIZE 1: Product 1 is in its own family (size 1). Returns 1.LINK 0, 1: Products 0 and 1 merge. Families: [0,1], [2]. Total families = 2.LINK 1, 2: Products 1 (and its family [0,1]) merge with product 2. Families: [0,1,2]. Total families = 1.COUNT_FAMILIES: Returns 1.GET_FAMILY_SIZE 0: Product 0 is in family [0,1,2] (size 3). Returns 3.Example 3
Input:
N = 1, operations = [["GET_FAMILY_SIZE", 0], ["COUNT_FAMILIES"]]
Output:
[1,1]
Note:
Initial state: 1 product (product 0) in its own family. Total families = 1, size = 1.
GET_FAMILY_SIZE 0: Returns 1.COUNT_FAMILIES: Returns 1.Constraints
1 <= N <= 10^51 <= operations.length <= 10^50 <= p, p1, p2 < N for all product IDs in operations.N and the number of operations can be large, so your solution must be efficient.LINK and GET_FAMILY_SIZE operations, where α is the inverse Ackermann function. COUNT_FAMILIES should also be efficient.p >= N) or malformed operation arrays.Loading editor...