Frontend School

Maximize Endorsement Impact

DSA
medium

Maximize Endorsement Impact

Medium
Greedy
Arrays
Sorting

Overview

As a prominent LinkedIn user, your goal is to strategically manage your daily endorsement activities to maximize your networking impact. You have a limited daily budget for endorsements. Each of your connections has several skills, and each skill carries a specific "endorsement value" reflecting its importance or relevance within the network. This problem challenges you to select which skills to endorse to achieve the highest possible total impact score.

What you need to do / Task

Implement a function maximizeEndorsementImpact that calculates the maximum total impact score you can achieve.

  1. For each connection, identify the single skill with the highest endorsement value.
  2. From these "best" skills (one per connection), select a subset to endorse such that the total number of endorsements does not exceed your endorsementLimit.
  3. The objective is to maximize the sum of the values of the endorsed skills.

Input & output

Function Signature: function maximizeEndorsementImpact(connectionsSkills: number[][], endorsementLimit: number): number

Input:

  • connectionsSkills: An array of arrays of numbers. connectionsSkills[i] is an array representing the endorsement values of skills for connection i. Each inner array will contain at least one skill value.
  • endorsementLimit: An integer representing the maximum total number of skills you can endorse across all connections.

Output:

  • An integer representing the maximum possible total impact score.

Clarifications

  • Empty connectionsSkills? If connectionsSkills is empty, the total impact should be 0.
  • endorsementLimit vs. number of connections? endorsementLimit can be greater than the number of connections. In such a case, if you have enough endorsements, you would endorse the best skill for every connection.
  • Skill values? All skill values are positive integers.

Examples

1

Example 1

Input:

connectionsSkills = [[10, 5, 8], [7, 12], [3, 9, 6]], endorsementLimit = 2

Output:

22

Note:

For Connection 0, the best skill is 10. For Connection 1, the best skill is 12. For Connection 2, the best skill is 9. The available top skills are [10, 12, 9]. With an endorsement limit of 2, we pick the two highest: 12 + 10 = 22.

2

Example 2

Input:

connectionsSkills = [[1, 2, 3]], endorsementLimit = 5

Output:

3

Note:

Only one connection. The best skill is 3. Since endorsementLimit (5) is greater than or equal to 1, we endorse this skill. Total impact: 3.

3

Example 3

Input:

connectionsSkills = [[100], [50], [200]], endorsementLimit = 0

Output:

0

Note:

With an endorsement limit of 0, no skills can be endorsed, resulting in a total impact of 0.

4

Example 4

Input:

connectionsSkills = [], endorsementLimit = 5

Output:

0

Note:

No connections, so no skills can be endorsed. Total impact is 0.

Constraints

Constraints & assumptions

  • 0 <= connectionsSkills.length <= 10^4
  • 1 <= connectionsSkills[i].length <= 50
  • 1 <= connectionsSkills[i][j] <= 1000 (Skill values are positive integers)
  • 0 <= endorsementLimit <= 10^5 (Can be 0, meaning no endorsements are given)

Out of scope

  • Handling negative skill values or non-integer values.
  • Optimizing for endorsement distribution beyond the maximum total impact (e.g., fairness across connections).
  • Real-time updates or dynamic changes to skill values or connections.

What interviewers evaluate

  • Correctness: The solution correctly identifies the optimal set of skills to endorse and calculates the maximum impact.
  • Algorithm Design: The candidate identifies and applies an appropriate greedy strategy.
  • Time and Space Complexity: The solution demonstrates efficient use of time and space, considering the given constraints.
  • Code Quality: The code is clean, readable, well-structured, and handles edge cases gracefully.

Loading editor...