Frontend School

Maximize Curated Collection Profit Margin

DSA
hard

Maximize Curated Collection Profit Margin

Hard
Binary Search
Meet-in-the-Middle
Knapsack

Overview

Nykaa is planning a new "Curated Collection" of beauty products. To make this collection a success, they need to maximize its overall profitability while adhering to strict budget and production time constraints. A unique marketing strategy dictates that if a product is selected for the collection, it must be produced in the same uniform quantity as all other selected products.

What you need to do / Task

Your task is to implement a function that determines the maximum possible profit margin percentage Nykaa can achieve for this curated collection. If no collection can be formed (e.g., due to insufficient budget or time for even a single item), return 0.0.

Profit margin percentage is calculated as ((Total Revenue - Total Cost) / Total Cost) * 100. The total cost and total revenue are summed across all selected products, each produced in the same uniform quantity X (where X >= 1).

Input & output

Function Signature:

function maxCuratedCollectionProfitMargin(
  unitCosts: number[],
  unitSalePrices: number[],
  unitProductionTimes: number[],
  totalBudget: number,
  totalProductionTimeLimit: number
): number

Parameters:

  • unitCosts: An array of N numbers, where unitCosts[i] is the cost to acquire/produce one unit of product i.
  • unitSalePrices: An array of N numbers, where unitSalePrices[i] is the selling price of one unit of product i.
  • unitProductionTimes: An array of N numbers, where unitProductionTimes[i] is the time required to produce one unit of product i.
  • totalBudget: A number representing the maximum total capital (cost) Nykaa can spend on acquiring/producing all selected products.
  • totalProductionTimeLimit: A number representing the maximum total time Nykaa can spend on producing all selected products.

Return Value:

  • A number representing the maximum achievable profit margin percentage. The result should be accurate to at least 10^-5 decimal places. If no valid collection can be formed (i.e., no subset of items can be produced even for X=1 within constraints), return 0.0.

Clarifications

  • The uniform quantity X for each selected product must be an integer X >= 1.
  • A collection must consist of at least one product.
  • unitCosts[i] will always be positive.
  • The profit margin percentage can be negative if total costs exceed total revenue.

Examples

1

Example 1

Input:

unitCosts = [10, 20, 30], unitSalePrices = [15, 25, 40], unitProductionTimes = [1, 2, 3], totalBudget = 50, totalProductionTimeLimit = 5

Output:

50.00000

Note:

With a uniform quantity X=1:

  • Product 0: Cost=10, Sale=15, Time=1. Profit=5.
  • Product 1: Cost=20, Sale=25, Time=2. Profit=5.
  • Product 2: Cost=30, Sale=40, Time=3. Profit=10.

Consider selecting products 0 and 2: Total Cost = 10 + 30 = 40 (<= 50) Total Time = 1 + 3 = 4 (<= 5) Total Revenue = 15 + 40 = 55 Profit Margin = ((55 - 40) / 40) * 100 = (15 / 40) * 100 = 37.5%

Consider selecting products 0, 1, and 2: Total Cost = 10 + 20 + 30 = 60 (> 50) - Not possible.

Consider selecting only product 2: Total Cost = 30 (<= 50) Total Time = 3 (<= 5) Total Revenue = 40 Profit Margin = ((40 - 30) / 30) * 100 = (10 / 30) * 100 = 33.333...

Consider selecting products 0 and 1: Total Cost = 10 + 20 = 30 (<= 50) Total Time = 1 + 2 = 3 (<= 5) Total Revenue = 15 + 25 = 40 Profit Margin = ((40 - 30) / 30) * 100 = (10 / 30) * 100 = 33.333...

If we target a profit margin M = 50.0%. We define transformed_value[i] = (unitSalePrices[i] - unitCosts[i]) - (M/100) * unitCosts[i].

  • Product 0: (15-10) - 0.5 * 10 = 5 - 5 = 0
  • Product 1: (25-20) - 0.5 * 20 = 5 - 10 = -5
  • Product 2: (40-30) - 0.5 * 30 = 10 - 15 = -5

If we select only Product 0: Total Cost = 10 (<=50), Total Time = 1 (<=5), Sum of Transformed Values = 0 (>=0). This is a valid collection. Thus, 50% profit margin is achievable. The maximum is indeed 50.0%.

2

Example 2

Input:

unitCosts = [100], unitSalePrices = [90], unitProductionTimes = [5], totalBudget = 10, totalProductionTimeLimit = 10

Output:

0.00000

Note:

Only one product. Cost=100, Budget=10. Cannot afford even 1 unit. No collection possible, so return 0.0.

3

Example 3

Input:

unitCosts = [100, 50], unitSalePrices = [120, 70], unitProductionTimes = [10, 5], totalBudget = 150, totalProductionTimeLimit = 15

Output:

40.00000

Note:

Product 0: Cost=100, Sale=120, Time=10. Profit=20. Product 1: Cost=50, Sale=70, Time=5. Profit=20.

If X=1:

  • Select Product 0: Total Cost=100, Total Time=10. Margin=((120-100)/100)*100 = 20%.
  • Select Product 1: Total Cost=50, Total Time=5. Margin=((70-50)/50)*100 = 40%.
  • Select Product 0 and 1: Total Cost=150, Total Time=15. Margin=(( (120+70) - (100+50) ) / (100+50) )*100 = ((190 - 150) / 150) * 100 = (40/150)*100 = 26.666...

The maximum is 40% by selecting only Product 1. Let's verify with the check function for M=40.0: transformed_value[i] = (unitSalePrices[i] - unitCosts[i]) - (M/100) * unitCosts[i]

  • Product 0: (120-100) - 0.4 * 100 = 20 - 40 = -20
  • Product 1: (70-50) - 0.4 * 50 = 20 - 20 = 0

If we select only Product 1: Total Cost = 50 (<=150), Total Time = 5 (<=15), Sum of Transformed Values = 0 (>=0). This is a valid collection. Thus, 40% profit margin is achievable. The maximum is indeed 40.0%.

Constraints

Constraints & assumptions

  • 1 <= N <= 50 (Number of available products)
  • 1 <= unitCosts[i], unitSalePrices[i], unitProductionTimes[i] <= 10^9
  • 1 <= totalBudget, totalProductionTimeLimit <= 10^14
  • All input values are integers.
  • The returned percentage should be accurate to 10^-5 or better.

Out of scope

  • Handling invalid input types or negative values for totalBudget or totalProductionTimeLimit.
  • Optimizing for specific product combinations beyond the maximum profit margin percentage (e.g., maximizing the number of products).

What interviewers evaluate

  • Algorithmic Correctness: Correct application of binary search on the answer space and an efficient check function.
  • Efficiency: The check function should be optimized to handle large N and constraints within typical time limits (e.g., O(2^(N/2) * (N/2)) for the meet-in-the-middle part).
  • Edge Cases: Correctly handles scenarios like no possible collection, negative profit margins, or cases where only one product can be selected.
  • Code Structure & Readability: Clean, well-organized code with appropriate variable names and comments where necessary.

Loading editor...