Frontend School

Diverse Product Bundle Recommendation

DSA
medium

Diverse Product Bundle Recommendation

Medium
Graph
BFS
DFS
Product Recommendation

Overview

Nykaa aims to enhance customer experience by offering intelligent product bundle recommendations. A key challenge is ensuring these bundles are diverse, exposing customers to a wider range of products and categories. This problem asks you to determine if a specific product can be part of a "diverse bundle" – a set of compatible products that collectively span at least a minimum number of distinct product categories. This capability is crucial for generating engaging and comprehensive recommendations.

What you need to do / Task

Implement a function canFormDiverseBundle that determines if a given startProductId can be included in a bundle of compatible products such that the bundle contains at least minCategories distinct product categories. A "bundle" in this context is defined as a connected component in the compatibility graph that includes startProductId.

Input & output

Your function will receive the following parameters:

  • numProducts: An integer representing the total number of products, indexed from 0 to numProducts - 1.
  • compatibilities: A 2D array of integers, where each inner array [u, v] denotes that product u and product v are compatible. Compatibility is bidirectional.
  • productCategories: An array of integers where productCategories[i] is the category ID for product i. Category IDs are positive integers.
  • startProductId: An integer representing the ID of the product from which to start forming the bundle.
  • minCategories: An integer representing the minimum number of distinct product categories required in the bundle.

The function should return a boolean: true if startProductId can be part of such a diverse bundle, false otherwise.

Clarifications

  • Products are represented by integer IDs from 0 to numProducts - 1.
  • Compatibility is an undirected relationship: if u is compatible with v, then v is compatible with u.
  • A bundle is formed by startProductId and all other products reachable from it through compatibility links.
  • If startProductId has no compatibilities, the bundle consists only of startProductId itself.
  • minCategories will always be at least 1.

Examples

1

Example 1

Input:

numProducts = 5, compatibilities = [[0, 1], [1, 2], [2, 3], [3, 4]], productCategories = [100, 200, 100, 300, 200], startProductId = 0, minCategories = 3

Output:

true

Note:

Starting from product 0 (Category 100), we can reach product 1 (Category 200), product 2 (Category 100), product 3 (Category 300), and product 4 (Category 200). The distinct categories encountered are {100, 200, 300}, which is 3 distinct categories. Since 3 >= minCategories (3), the function returns true.

2

Example 2

Input:

numProducts = 3, compatibilities = [[0, 1], [1, 2]], productCategories = [100, 200, 100], startProductId = 0, minCategories = 3

Output:

false

Note:

Starting from product 0 (Category 100), we can reach product 1 (Category 200) and product 2 (Category 100). The distinct categories encountered are {100, 200}, which is 2 distinct categories. Since 2 < minCategories (3), the function returns false.

3

Example 3

Input:

numProducts = 3, compatibilities = [[1, 2]], productCategories = [100, 200, 300], startProductId = 0, minCategories = 2

Output:

false

Note:

Product 0 is not compatible with any other product. The bundle consists only of product 0 (Category 100). The distinct categories are {100}, which is 1 distinct category. Since 1 < minCategories (2), the function returns false.

4

Example 4

Input:

numProducts = 2, compatibilities = [[0, 1]], productCategories = [100, 200], startProductId = 0, minCategories = 1

Output:

true

Note:

Starting from product 0 (Category 100), we immediately have 1 distinct category. Since 1 >= minCategories (1), the function returns true.

Constraints

Constraints & assumptions

  • 1 <= numProducts <= 10^5
  • 0 <= compatibilities.length <= 10^5
  • compatibilities[i].length == 2
  • 0 <= u, v < numProducts for all [u, v] in compatibilities
  • 1 <= productCategories[i] <= 10^9 for all i
  • 0 <= startProductId < numProducts
  • 1 <= minCategories <= numProducts
  • The graph formed by compatibilities may contain self-loops or multiple edges between the same pair of products. Treat them as a single edge for reachability.

Out of scope

  • Optimizing for the largest possible diverse bundle, only checking existence.
  • Handling invalid input types or out-of-bounds startProductId. Assume valid inputs.

What interviewers evaluate

  • Correctness: The solution accurately identifies if a diverse bundle can be formed.
  • Algorithm Efficiency: Uses an optimal graph traversal algorithm (BFS or DFS) with appropriate data structures.
  • Edge Case Handling: Correctly handles scenarios like isolated products, minCategories = 1, or sparse compatibility graphs.
  • Code Clarity and Structure: Well-organized, readable code with meaningful variable names.

Loading editor...