Frontend School

Optimize Feature Adoption

DSA
easy

Optimize Feature Adoption

Easy
Dynamic Programming
1D DP
Arrays

Overview

Zoho aims to deliver highly relevant and valuable features to its users. To optimize product adoption strategies, we need to understand how feature choices impact overall user engagement. This problem models a scenario where adopting certain features influences the adoption of others, and our goal is to maximize the cumulative engagement score by strategically selecting features.

What you need to do / Task

You are given an array featureScores representing the individual adoption scores of various features. If a feature with score X is adopted, it contributes X points to the total engagement score. However, due to user experience considerations, if a feature X is adopted, features with scores X-1 and X+1 cannot be adopted. Your task is to implement a function that calculates the maximum possible total engagement score by strategically selecting features.

Input & output

Function Signature:

function maximizeEngagement(featureScores: number[]): number
  • featureScores: An array of integers, where each featureScores[i] represents the adoption score of a particular feature. Multiple features can have the same adoption score.
  • Returns: An integer representing the maximum total engagement score achievable.

Clarifications

  • What if featureScores is empty? The constraints specify featureScores.length >= 1, so it will not be empty.
  • What about large scores? Scores can go up to 10^4. The resulting total engagement score might exceed standard 32-bit integer limits, so ensure your solution handles larger numbers (standard number type in JS/TS handles this automatically up to 2^53 - 1).

Examples

1

Example 1

Input:

featureScores = [3, 4, 2]

Output:

6

Note:

If you adopt features with scores 2 and 4, you get 2 + 4 = 6 points. Adopting 2 disallows 3. Adopting 4 disallows 3 and 5. This is the maximum.

2

Example 2

Input:

featureScores = [2, 2, 3, 3, 3, 4]

Output:

9

Note:

Features with score 2 appear twice (total 4 points). Features with score 3 appear thrice (total 9 points). Features with score 4 appear once (total 4 points). Option 1: Adopt all features with score 3 (9 points). This disallows scores 2 and 4. Total: 9. Option 2: Adopt all features with score 2 (4 points) and all features with score 4 (4 points). This disallows score 3. Total: 8. The maximum is 9.

3

Example 3

Input:

featureScores = [1, 1, 1, 2, 2, 3, 3, 4, 5]

Output:

14

Note:

Scores and their total points: 1 (3 points), 2 (4 points), 3 (6 points), 4 (4 points), 5 (5 points). Optimal strategy: Adopt features with scores 1, 3, and 5. This yields (13) + (32) + (5*1) = 3 + 6 + 5 = 14 points. Scores 2 and 4 are disallowed due to adjacent selections.

Constraints

Constraints & assumptions

  • 1 <= featureScores.length <= 2 * 10^4
  • 1 <= featureScores[i] <= 10^4
  • The order of features in featureScores does not imply any dependency beyond the X-1, X, X+1 rule.
  • Your solution should aim for optimal time complexity.

Out of scope

  • Input validation (e.g., featureScores containing non-positive numbers or non-integers).
  • Handling extremely large numbers that exceed typical number precision (e.g., BigInt not required).

What interviewers evaluate

  • Correctness: The solution accurately calculates the maximum engagement score for all valid inputs.
  • Algorithmic Efficiency: The solution uses an optimal approach in terms of time and space complexity (e.g., O(N + MaxScore) time complexity, where N is featureScores.length and MaxScore is the maximum value in featureScores).
  • Code Structure and Readability: The code is well-organized, easy to understand, and follows good programming practices.
  • Problem-Solving Process: Ability to identify the dynamic programming pattern and derive the correct recurrence relation.

Loading editor...