Frontend School

Optimize Creative Effects for Mobile

DSA
medium

Optimize Creative Effects for Mobile

Medium
Dynamic Programming
Knapsack
Arrays

Overview

As a senior engineer at Adobe, you're tasked with optimizing the performance of a new feature for a mobile version of a creative application (e.g., Photoshop Express, Lightroom Mobile). This feature allows users to apply multiple enhancement effects (filters) to an image. Each effect consumes a certain amount of processing power (CPU/GPU cycles) and contributes a specific 'visual impact score' to the final image.

The challenge is that mobile devices have a finite processing budget to ensure a smooth, responsive user experience. You need to select a subset of available effects that maximizes the total visual impact score without exceeding the device's processing budget. This problem is crucial for balancing feature richness with application performance on resource-constrained platforms.

What you need to do / Task

Implement the function optimizeEffects that takes three parameters:

  1. processingCosts: An array of numbers, where processingCosts[i] represents the processing power consumed by the i-th effect.
  2. visualImpacts: An array of numbers, where visualImpacts[i] represents the visual impact score provided by the i-th effect.
  3. maxBudget: A number representing the total processing power available.

Your function should return the maximum possible total visual impact score that can be achieved by selecting a subset of effects, such that their combined processing cost does not exceed maxBudget. Each effect can be used at most once.

Input & output

  • Input: processingCosts: number[], visualImpacts: number[], maxBudget: number
    • processingCosts: An array of non-negative integers representing the cost of each effect.
    • visualImpacts: An array of non-negative integers representing the impact of each effect.
    • maxBudget: A non-negative integer representing the maximum allowed total processing cost.
  • Output: number
    • Returns a single non-negative integer: the maximum total visual impact score.

Clarifications

  • The i-th element in processingCosts corresponds to the i-th element in visualImpacts.
  • If no effects can be chosen within the maxBudget, the function should return 0.
  • All input values (costs, impacts, budget) are non-negative integers.

Examples

1

Example 1

Input:

processingCosts = [2, 3, 4], visualImpacts = [3, 4, 5], maxBudget = 5

Output:

7

Note:

With a budget of 5:

  • Option 1: Pick effect 0 (cost 2, impact 3) and effect 1 (cost 3, impact 4). Total cost = 2+3=5, total impact = 3+4=7.
  • Option 2: Pick effect 2 (cost 4, impact 5). Total cost = 4, total impact = 5.
  • Other combinations like (effect 0 + effect 2) or (effect 1 + effect 2) exceed the budget. The maximum visual impact is 7.
2

Example 2

Input:

processingCosts = [10, 20], visualImpacts = [5, 8], maxBudget = 5

Output:

0

Note:

The maxBudget is 5. Both effects have processing costs (10 and 20) that exceed the budget individually. Therefore, no effects can be chosen, resulting in a total visual impact of 0.

3

Example 3

Input:

processingCosts = [1, 2, 3, 4, 5], visualImpacts = [10, 20, 30, 40, 50], maxBudget = 7

Output:

70

Note:

With a budget of 7:

  • Picking effects with costs 3 and 4 gives an impact of 30+40=70 (total cost 7).
  • Picking effects with costs 2 and 5 gives an impact of 20+50=70 (total cost 7).
  • Picking effects with costs 1, 2, and 4 gives an impact of 10+20+40=70 (total cost 7). No other combination yields a higher impact within the budget. The maximum visual impact is 70.

Constraints

Constraints & assumptions

  • 1 <= N <= 500, where N is the number of effects (i.e., processingCosts.length).
  • processingCosts.length === visualImpacts.length.
  • 0 <= processingCosts[i] <= 1000 for all i.
  • 0 <= visualImpacts[i] <= 1000 for all i.
  • 0 <= maxBudget <= 10000.
  • All input values are integers.

Out of scope

  • Input validation for non-array types or negative values (assume valid inputs per constraints).
  • Handling non-integer costs, impacts, or budget.
  • Optimizations for extremely sparse data or specialized hardware architectures.

What interviewers evaluate

  • Ability to identify and apply an appropriate algorithmic paradigm (Dynamic Programming, Knapsack).
  • Correctness and efficiency of the implemented solution, particularly in terms of time and space complexity.
  • Clarity, readability, and structure of the code.
  • Handling of edge cases and base conditions (e.g., zero budget, no selectable items).

Loading editor...