Frontend School

Maximize Product Launch Impact

DSA
medium

Maximize Product Launch Impact

Medium
Dynamic Programming
Knapsack

Overview

At Amazon, launching new products and features is crucial for delighting customers and driving business growth. Before a major product launch, teams often face the challenge of selecting which features to develop given limited resources. Each potential feature has an estimated development cost and a projected customer impact score. The goal is to maximize the total customer impact for the launch while staying within a predefined development budget.

What you need to do / Task

Your task is to implement a function that determines the maximum total customer impact that can be achieved for a product launch. You will be provided with a list of features, each with an associated development cost and customer impact score, along with the total development budget.

Specifically, you must:

  1. Given costs (an array of feature development costs), impacts (an array of corresponding customer impact scores), and a budget (the maximum total cost allowed).
  2. Select a subset of features such that their total development cost does not exceed the budget.
  3. Maximize the sum of the customer impact scores for the selected features.
  4. Each feature can be selected at most once.

Input & output

  • Input:
    • costs: An array of numbers, where costs[i] represents the development cost of the i-th feature.
    • impacts: An array of numbers, where impacts[i] represents the customer impact score of the i-th feature, corresponding to costs[i].
    • budget: A number representing the maximum total development cost allowed.
  • Output:
    • A single number representing the maximum total customer impact score achievable within the given budget.

Clarifications

  • The costs and impacts arrays will always have the same length, representing the same set of features.
  • All costs, impacts, and budget values will be non-negative integers.
  • If no features can be selected without exceeding the budget, the maximum total impact is 0.

Examples

1

Example 1

Input:

costs = [10, 20, 30], impacts = [60, 100, 120], budget = 50

Output:

220

Note:

Features are (cost, impact): (10,60), (20,100), (30,120). With a budget of 50, selecting features (20,100) and (30,120) yields a total cost of 50 and total impact of 220. No other combination yields a higher impact within the budget.

2

Example 2

Input:

costs = [5, 3, 2], impacts = [10, 8, 5], budget = 4

Output:

8

Note:

Features are (cost, impact): (5,10), (3,8), (2,5). With a budget of 4, selecting feature (3,8) costs 3 and gives an impact of 8. Selecting feature (2,5) costs 2 and gives an impact of 5. The feature (5,10) cannot be afforded. The maximum impact is 8.

3

Example 3

Input:

costs = [100], impacts = [500], budget = 50

Output:

0

Note:

The only feature costs 100, which exceeds the budget of 50. Therefore, no features can be selected, resulting in a total impact of 0.

Constraints

Constraints & assumptions

  • 1 <= N <= 100, where N is the number of features (length of costs and impacts arrays).
  • 1 <= costs[i] <= 1000
  • 1 <= impacts[i] <= 1000
  • 0 <= budget <= 10000
  • All input values (costs, impacts, budget) are integers.

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly identify the maximum impact for all valid inputs?
  • Optimal Complexity: Is the solution efficient in terms of time and space complexity, aligning with the constraints?
  • Dynamic Programming Application: Does the candidate demonstrate a solid understanding of Dynamic Programming principles, specifically related to the Knapsack problem?
  • Code Quality: Is the code clean, readable, well-structured, and does it handle edge cases gracefully?

Loading editor...