Frontend School

Optimal Product Curation

DSA
hard

Optimal Product Curation

Hard
Dynamic Programming
Sliding Window
Deque

Overview

Nykaa's product curation team aims to optimize the display of a linear sequence of products to maximize customer engagement. Each product offers a certain "satisfaction value". To maintain variety and prevent user fatigue, specific rules dictate how many products must be skipped between any two consecutively chosen products. Your task is to implement an algorithm that finds the maximum total satisfaction value achievable under these constraints.

What you need to do / Task

Implement a function maxCuratedSatisfaction that calculates the maximum total satisfaction value from selecting products based on the given rules. The function must adhere to the following:

  • If you select product i and then product j (where j > i), you must skip at least minSkip products and at most maxSkip products between them. That is, minSkip <= (j - i - 1) <= maxSkip.
  • You can choose to select any number of products, from zero up to the total number of products. Selecting zero products yields a total satisfaction of 0.
  • The first product selected does not have any preceding skip requirements.

Input & output

  • Input:
    • satisfactionScores: An array of non-negative integers (number[]), where satisfactionScores[k] represents the satisfaction value of the k-th product.
    • minSkip: A non-negative integer (number) representing the minimum number of products to skip between two selected products.
    • maxSkip: A non-negative integer (number) representing the maximum number of products to skip between two selected products.
  • Output:
    • A single non-negative integer (number) representing the maximum total satisfaction value that can be achieved.

Clarifications

  • If satisfactionScores is empty, the result is 0.
  • If all possible selections result in negative total satisfaction (which is unlikely given satisfactionScores[i] >= 0, but dp[j] could be negative if satisfactionScores[j] were allowed to be negative in general DP problems), the function should return 0 (by choosing no products). However, for this problem, satisfactionScores[i] are guaranteed to be non-negative, so dp[i] values will also be non-negative.

Examples

1

Example 1

Input:

satisfactionScores = [10, -5, 20, 3, 15], minSkip = 1, maxSkip = 2

Output:

45

Note:

Let N be the length of satisfactionScores. dp[i] represents the maximum satisfaction ending with product i. The predecessor j for product i must satisfy i - maxSkip - 1 <= j <= i - minSkip - 1.

  • dp[0] = 10
  • dp[1] = -5 + max(0, dp[0]) = 5 (no valid predecessor j in range [-2, -1], so consider starting new chain at dp[0])
  • dp[2] = 20 + max(0, dp[0]) = 30 (predecessor j in range [-1, 0], so dp[0] is considered)
  • dp[3] = 3 + max(0, dp[0], dp[1]) = 13 (predecessor j in range [0, 1], so dp[0] and dp[1] are considered)
  • dp[4] = 15 + max(0, dp[1], dp[2]) = 45 (predecessor j in range [1, 2], so dp[1] and dp[2] are considered) The maximum value in dp is 45. The optimal sequence is choosing product 0 (score 10), then product 2 (score 20, skipping 1 product), then product 4 (score 15, skipping 1 product). Total: 10 + 20 + 15 = 45.
2

Example 2

Input:

satisfactionScores = [5, 1, 10, 1, 20], minSkip = 0, maxSkip = 1

Output:

37

Note:

Here, minSkip=0 and maxSkip=1 means you can select an adjacent product (skip 0) or skip one product. This allows summing all positive values. Since all scores are positive, the optimal strategy is to pick every product if possible. The sequence 5 -> 1 -> 10 -> 1 -> 20 sums to 37. Each step skips 0 products, which is within [0,1].

3

Example 3

Input:

satisfactionScores = [10, 0, 0, 0, 20], minSkip = 3, maxSkip = 3

Output:

30

Note:

Here, you must skip exactly 3 products between selections. Choosing product 0 (score 10) allows the next product to be product 4 (skipping products 1, 2, 3). Choosing product 4 (score 20) leads to a total of 10 + 20 = 30. No other valid sequence yields a higher total.

Constraints

Constraints & assumptions

  • 0 <= satisfactionScores.length <= 10^5
  • 0 <= satisfactionScores[i] <= 1000
  • 0 <= minSkip <= maxSkip
  • If satisfactionScores.length > 0, then maxSkip < satisfactionScores.length.

What interviewers evaluate

  • Correctness and Optimality: The solution must correctly calculate the maximum satisfaction value and achieve optimal time and space complexity (typically O(N) time and O(N) space).
  • Dynamic Programming Application: Demonstrate a clear understanding and correct application of 1D dynamic programming principles with optimized state transitions.
  • Edge Cases and Constraints: Properly handle edge cases such as empty input, single product, or scenarios where minSkip and maxSkip values lead to specific jump patterns (e.g., minSkip = maxSkip = 0).
  • Code Structure and Readability: Write clean, well-structured, and easy-to-understand code with appropriate variable names.
  • Sliding Window Optimization: Correctly apply a monotonic queue (deque) to optimize the windowed maximum query for DP transitions.

Loading editor...