Frontend School

Maximize Merchant Deal Portfolio Value

DSA
medium

Maximize Merchant Deal Portfolio Value

Medium
Dynamic Programming
Knapsack
Arrays
Optimization

Overview

As a leading fintech platform, Phonepe constantly innovates to provide value to both its users and merchant partners. A critical aspect involves curating attractive deal portfolios for merchants, balancing potential revenue gains with associated costs. This problem challenges you to optimize the selection of merchant deals within a defined budget to maximize the overall value generated.

What you need to do / Task

Your task is to implement a function that, given a list of potential merchant deals (each with an associated value and cost) and a maximum budget, determines the maximum total value that can be achieved by selecting a subset of these deals. Each deal can be chosen at most once.

Input & output

Function Signature: function maximizeDealPortfolioValue(dealValues: number[], dealCosts: number[], budget: number): number

  • dealValues: An array of positive integers, where dealValues[i] represents the monetary or strategic value gained from selecting the i-th deal.
  • dealCosts: An array of positive integers, where dealCosts[i] represents the financial cost incurred for selecting the i-th deal. dealCosts will have the same length as dealValues.
  • budget: A positive integer representing the maximum total cost Phonepe can afford for the selected deals.

Return Value: Return a single integer: the maximum total value that can be achieved without exceeding the budget. If no deals can be selected within the budget, return 0.

Clarifications

  • Empty input: You can assume dealValues and dealCosts will not be empty. Their length will be at least 1.
  • Zero budget: If the budget is 0, no deals can be selected unless a deal has a cost of 0 (which is not allowed by constraints). In such cases, the result should be 0.
  • Deal selection: Each deal can be selected at most once (it's a 0/1 choice for each deal).
  • Data types: All input values (dealValues, dealCosts, budget) are positive integers.

Examples

1

Example 1

Input:

dealValues = [60, 100, 120], dealCosts = [10, 20, 30], budget = 50

Output:

220

Note:

To maximize value, select the deal with value 100 (cost 20) and the deal with value 120 (cost 30). Total value = 100 + 120 = 220. Total cost = 20 + 30 = 50. This fits exactly within the budget. Other combinations, such as selecting all three deals, would exceed the budget.

2

Example 2

Input:

dealValues = [10, 20, 30], dealCosts = [60, 70, 80], budget = 50

Output:

0

Note:

No single deal can be selected as all deals have a cost greater than the budget of 50. Therefore, the maximum achievable value is 0.

3

Example 3

Input:

dealValues = [10, 20, 30, 40], dealCosts = [5, 10, 15, 20], budget = 25

Output:

50

Note:

Several combinations achieve a value of 50 within the budget:

  • Select deal with value 40 (cost 20) and deal with value 10 (cost 5). Total value = 40 + 10 = 50. Total cost = 20 + 5 = 25.
  • Select deal with value 30 (cost 15) and deal with value 20 (cost 10). Total value = 30 + 20 = 50. Total cost = 15 + 10 = 25. Both combinations fit the budget and yield the maximum value.

Constraints

Constraints & assumptions

  • 1 <= dealValues.length == dealCosts.length <= 100
  • 1 <= dealValues[i], dealCosts[i] <= 1000
  • 1 <= budget <= 10000
  • The solution should aim for an optimal time complexity, typically O(N*W) where N is the number of deals and W is the budget.
  • The output value will fit within a standard 32-bit integer.

Out of scope

  • Error handling for invalid input types or negative values.
  • Scalability beyond the given constraints (e.g., extremely large N or budget).
  • Returning the actual subset of deals chosen; only the maximum value is required.

What interviewers evaluate

  • Correctness: Does the solution accurately calculate the maximum portfolio value for all valid inputs?
  • Optimal Approach: Is the chosen algorithm efficient and appropriate for the given constraints (e.g., Dynamic Programming for 0/1 Knapsack)?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand, with meaningful variable names?
  • Edge Case Handling: Does the solution correctly handle scenarios like a very small budget, deals with costs exceeding the budget, or a single deal being the only option?
  • Space Complexity: Is the solution's memory usage optimized (e.g., using a 1D DP array if possible)?

Loading editor...