Frontend School

Max Net Content Engagement

DSA
medium

Max Net Content Engagement

Medium
Dynamic Programming
2D Array
Optimization

Overview

Sharechat aims to maximize user engagement by curating personalized content feeds. Imagine a simplified model where a user interacts with content across several days. Each day, the user can choose to engage with one specific content category. Different categories offer varying engagement scores on different days. However, switching between categories from one day to the next incurs a "switch cost," reflecting the cognitive effort or preference shift required. The goal is to design an optimal content consumption strategy to maximize the net engagement (total engagement scores minus total switch costs) over a given period.

What you need to do / Task

Implement the function calculateMaxNetEngagement that determines the maximum possible net engagement a user can achieve over a period of D days, given the daily engagement scores for each category and the costs associated with switching between any two categories.

Input & output

The function calculateMaxNetEngagement takes two 2D arrays as input:

  • engagementScores: A D x C 2D array of integers, where D is the number of days and C is the number of content categories. engagementScores[i][j] represents the engagement score obtained if the user engages with category j on day i.
  • switchCosts: A C x C 2D array of integers. switchCosts[j][k] represents the cost incurred if the user switches from category j on the previous day to category k on the current day. If the user stays in the same category j, the cost switchCosts[j][j] is incurred.

The function should return a single integer representing the maximum net engagement score achievable.

Function Signature:

function calculateMaxNetEngagement(engagementScores: number[][], switchCosts: number[][]): number {
  // your code here
}

Clarifications

  • The number of days D is engagementScores.length.
  • The number of categories C is engagementScores[0].length.
  • The user starts on day 0. There is no switch cost incurred before day 0 as there's no previous day to switch from. The engagement on day 0 is simply engagementScores[0][j] for the chosen category j.
  • All engagement scores and switch costs are non-negative.
  • The problem guarantees that D >= 1 and C >= 1.

Examples

1

Example 1

Input:

engagementScores = [[10, 5], [8, 12]], switchCosts = [[0, 1], [2, 0]]

Output:

21

Note:

D=2, C=2. Day 0: Max engagement is 10 (Cat 0). Day 1:

  • If Day 0 was Cat 0 (score 10):
    • Stay Cat 0: 10 + 8 - switchCosts[0][0] = 10 + 8 - 0 = 18
    • Switch to Cat 1: 10 + 12 - switchCosts[0][1] = 10 + 12 - 1 = 21
  • If Day 0 was Cat 1 (score 5):
    • Switch to Cat 0: 5 + 8 - switchCosts[1][0] = 5 + 8 - 2 = 11
    • Stay Cat 1: 5 + 12 - switchCosts[1][1] = 5 + 12 - 0 = 17 Maximum overall is 21 (Day 0 Cat 0 -> Day 1 Cat 1).
2

Example 2

Input:

engagementScores = [[10, 1, 5], [2, 15, 3], [7, 4, 20]], switchCosts = [[0, 1, 2], [3, 0, 1], [4, 2, 0]]

Output:

43

Note:

D=3, C=3. Optimal path: Day 0 Cat 0 (10) -> Day 1 Cat 1 (15 - S[0][1]=1 = 14) -> Day 2 Cat 2 (20 - S[1][2]=1 = 19). Total net engagement: 10 + (15 - 1) + (20 - 1) = 10 + 14 + 19 = 43.

3

Example 3

Input:

engagementScores = [[100, 20, 50]], switchCosts = [[0, 10, 20], [10, 0, 10], [20, 10, 0]]

Output:

100

Note:

D=1, C=3. Since there is only one day, no switch costs are incurred. The maximum engagement is simply the highest score on day 0, which is 100 for category 0.

Constraints

Constraints & assumptions

  • 1 <= D <= 1000 (number of days)
  • 1 <= C <= 100 (number of content categories)
  • 0 <= engagementScores[i][j] <= 1000 for all i, j.
  • 0 <= switchCosts[j][k] <= 500 for all j, k.
  • The input arrays engagementScores and switchCosts will always be valid and conform to the D x C and C x C dimensions respectively.

Out of scope

  • Input validation (e.g., checking for null arrays, incorrect dimensions, or negative values if not specified).
  • Handling extremely large numbers that might exceed standard integer limits (assume results fit within a 32-bit signed integer, or 64-bit if language default allows).

What interviewers evaluate

  • Correctness: The solution must produce the accurate maximum net engagement for all valid inputs.
  • Efficiency: The solution should achieve optimal time and space complexity, typically O(D * C^2) time and O(D) or O(C) space.
  • Code Quality: The code should be well-structured, readable, and follow good programming practices (e.g., meaningful variable names, clear logic).
  • Edge Cases: Proper handling of scenarios like a single day or a single category.

Loading editor...