Frontend School

Curated Product Bundles

DSA
medium

Curated Product Bundles

Medium
Backtracking
Combinatorics
Arrays
Set

Overview

Nykaa aims to enhance customer experience by offering personalized, curated product bundles. To achieve this, we need a system that can efficiently identify all potential product combinations that meet specific criteria. This problem challenges you to develop an algorithm that generates valid product bundles based on a given budget and a minimum requirement for distinct product categories.

What you need to do / Task

You are tasked with implementing a function findCuratedBundles that takes a list of available products, a maximum budget, and a minDistinctCategories count. Your function should return all unique combinations of products (represented by their IDs) that satisfy the following conditions:

  1. The total price of all products in a bundle must not exceed the budget.
  2. The bundle must contain at least minDistinctCategories unique product categories.
  3. Each product can be included in a bundle at most once.
  4. The order of products within a bundle does not matter. However, for consistent output, each bundle in the result should have its product IDs sorted lexicographically.
  5. The final list of bundles should also be unique and sorted lexicographically (e.g., [["A", "B"], ["A", "C"]] is sorted before [["A", "D"]]).

Input & output

Input

  • products: An array of objects, where each object represents a product.
    interface Product {
        id: string;        // Unique identifier for the product
        category: string;  // Category of the product (e.g., "Skincare", "Makeup")
        price: number;     // Price of the product
    }
    
  • budget: A number representing the maximum allowed total price for a bundle.
  • minDistinctCategories: A number representing the minimum required count of unique categories within a bundle.

Output

  • An array of arrays of strings (string[][]). Each inner array represents a valid product bundle and contains the ids of the products in that bundle, sorted lexicographically. The outer array (list of bundles) should also be sorted lexicographically.

Clarifications

  • Empty Bundles: Bundles must contain at least one product. An empty bundle is not considered valid.
  • Product IDs: All product IDs are unique strings.
  • Category Names: Category names are case-sensitive strings.
  • No Duplicates: A product instance from the input products array can be chosen at most once for a single bundle.
  • Output Format: Ensure the output adheres strictly to the sorting requirements for both individual bundles and the overall list of bundles.

Examples

1

Example 1

Input:

products = [ { id: "P1", category: "Skincare", price: 100 }, { id: "P2", category: "Makeup", price: 200 }, { id: "P3", category: "Skincare", price: 150 }, { id: "P4", category: "Haircare", price: 50 } ], budget = 300, minDistinctCategories = 2

Output:

[["P1","P2"],["P1","P4"],["P2","P4"],["P3","P4"]]

Note:

Valid bundles:

  • ["P1", "P2"]: Price 100+200=300 (<=300). Categories: {Skincare, Makeup} (2 distinct, >=2). Valid.
  • ["P1", "P4"]: Price 100+50=150 (<=300). Categories: {Skincare, Haircare} (2 distinct, >=2). Valid.
  • ["P2", "P4"]: Price 200+50=250 (<=300). Categories: {Makeup, Haircare} (2 distinct, >=2). Valid.
  • ["P3", "P4"]: Price 150+50=200 (<=300). Categories: {Skincare, Haircare} (2 distinct, >=2). Valid. Other combinations either exceed budget or do not meet the minimum distinct category count. The output is sorted lexicographically by bundle and then by product IDs within each bundle.
2

Example 2

Input:

products = [ { id: "A", category: "Electronics", price: 500 }, { id: "B", category: "HomeGoods", price: 300 }, { id: "C", category: "Electronics", price: 400 }, { id: "D", category: "Apparel", price: 200 }, { id: "E", category: "HomeGoods", price: 100 } ], budget = 800, minDistinctCategories = 3

Output:

[["A","D","E"],["C","D","E"]]

Note:

Valid bundles:

  • ["A", "D", "E"]: Price 500+200+100=800 (<=800). Categories: {Electronics, Apparel, HomeGoods} (3 distinct, >=3). Valid.
  • ["C", "D", "E"]: Price 400+200+100=700 (<=800). Categories: {Electronics, Apparel, HomeGoods} (3 distinct, >=3). Valid. Other combinations either exceed the budget or have fewer than 3 distinct categories (e.g., ["B", "C", "E"] has only {HomeGoods, Electronics}).
3

Example 3

Input:

products = [ { id: "X", category: "Food", price: 600 }, { id: "Y", category: "Drinks", price: 700 } ], budget = 500, minDistinctCategories = 1

Output:

[]

Note:

Neither product 'X' (price 600) nor 'Y' (price 700) can be included in any bundle, as their individual prices already exceed the budget of 500. Therefore, no valid bundles can be formed.

Constraints

Constraints & assumptions

  • 1 <= products.length <= 15
  • products[i].id is a unique non-empty string.
  • products[i].category is a non-empty string.
  • 1 <= products[i].price <= 1000
  • 1 <= budget <= 15000
  • 1 <= minDistinctCategories <= 5
  • All prices and the budget are positive integers.
  • The input products array will not be empty.

Out of scope

  • Advanced optimizations like dynamic programming for very large numbers of products (N > 20). The focus is on a clear backtracking solution.
  • Handling invalid input types or negative prices/budget. Assume valid inputs as per constraints.

What interviewers evaluate

  • Correctness: The solution should correctly identify all valid bundles and only valid bundles, adhering to all price, category, and uniqueness constraints.
  • Algorithm Design: Demonstrates a clear understanding and correct application of backtracking principles.
  • Code Quality: Writes clean, readable, and well-structured code with appropriate data structures.
  • Edge Case Handling: Correctly handles scenarios like no valid bundles, or when minDistinctCategories is high.

Loading editor...