Frontend School

Meesho Product Family Management

DSA
medium

Meesho Product Family Management

Medium
Union Find
Data Structures
Graph

Overview

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.

What you need to do / Task

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.

Input & output

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.

Clarifications

  • Products are 0-indexed, meaning their IDs range from 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

1

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.

  1. LINK 0, 1: Products 0 and 1 merge. Families: [0,1], [2], [3], [4]. Total families = 4.
  2. LINK 2, 3: Products 2 and 3 merge. Families: [0,1], [2,3], [4]. Total families = 3.
  3. COUNT_FAMILIES: Returns 3.
  4. GET_FAMILY_SIZE 0: Product 0 is in family [0,1] (size 2). Returns 2.
  5. 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.
  6. GET_FAMILY_SIZE 3: Product 3 is in family [0,1,2,3] (size 4). Returns 4.
  7. COUNT_FAMILIES: Returns 2.
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.

  1. GET_FAMILY_SIZE 1: Product 1 is in its own family (size 1). Returns 1.
  2. LINK 0, 1: Products 0 and 1 merge. Families: [0,1], [2]. Total families = 2.
  3. LINK 1, 2: Products 1 (and its family [0,1]) merge with product 2. Families: [0,1,2]. Total families = 1.
  4. COUNT_FAMILIES: Returns 1.
  5. GET_FAMILY_SIZE 0: Product 0 is in family [0,1,2] (size 3). Returns 3.
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.

  1. GET_FAMILY_SIZE 0: Returns 1.
  2. COUNT_FAMILIES: Returns 1.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5
  • 1 <= operations.length <= 10^5
  • 0 <= p, p1, p2 < N for all product IDs in operations.
  • The total number of products N and the number of operations can be large, so your solution must be efficient.
  • Time complexity: Aim for nearly constant time (amortized O(α(N))) for LINK and GET_FAMILY_SIZE operations, where α is the inverse Ackermann function. COUNT_FAMILIES should also be efficient.
  • Space complexity: O(N) for storing the Union Find data structures.

Out of scope

  • Error handling for invalid product IDs (e.g., p >= N) or malformed operation arrays.
  • Handling of product deletions or unlinking operations.

What interviewers evaluate

  • Correctness and Efficiency: Implementation of the Union-Find data structure with proper path compression and union-by-size/rank heuristics for optimal performance.
  • State Management: Accurately tracking auxiliary information such as the total count of distinct families and the size of each family.
  • Problem Decomposition: Ability to map different operation types to the core Union-Find logic effectively.
  • Code Quality: Clarity, readability, and maintainability of the solution.

Loading editor...