Frontend School

Maximize Profile Impact

DSA
medium

Maximize Profile Impact

Medium
Dynamic Programming
Knapsack
Arrays

Overview

On LinkedIn, professionals strategically curate their profiles to showcase their most impactful achievements. Often, there's a practical limit to how much detail can be provided or how many projects can be highlighted effectively, representing a 'time budget' a recruiter or peer might spend reviewing. This problem simulates a scenario where a user needs to select a set of projects to feature on their profile, each with a specific timeCost (e.g., effort to prepare, space on profile) and an impactScore (e.g., perceived value, relevance). The goal is to maximize the total impact within a given timeBudget.

What you need to do / Task

Implement a function maximizeProfileImpact that, given a list of projects and a total timeBudget, calculates the maximum possible total impactScore that can be achieved without exceeding the timeBudget.

  1. Design and implement an algorithm to determine the optimal selection of projects.
  2. Each project can be selected at most once.
  3. Ensure your solution correctly handles edge cases, such as an empty list of projects or a timeBudget that is too small for any project.
  4. Optimize for time and space complexity, aiming for an efficient solution.

Input & output

Function Signature:

interface Project {
    timeCost: number;
    impactScore: number;
}

function maximizeProfileImpact(projects: Project[], timeBudget: number): number;

Parameters:

  • projects: An array of Project objects. Each Project object has two properties:
    • timeCost: A non-negative integer representing the time commitment or resource cost for the project.
    • impactScore: A non-negative integer representing the value or impact gained from including the project.
  • timeBudget: A non-negative integer representing the maximum total timeCost that can be allocated across selected projects.

Returns:

  • A non-negative integer representing the maximum total impactScore that can be achieved within the timeBudget.

Clarifications

  • If no projects can be selected within the timeBudget (e.g., all projects have timeCost greater than timeBudget), the function should return 0.
  • The order of projects in the input array does not matter.
  • Assume project objects in the projects array are distinct entities; you cannot select the same project multiple times, even if it has identical timeCost and impactScore to another project in the list.

Examples

1

Example 1

Input:

projects = [{ "timeCost": 10, "impactScore": 60 }, { "timeCost": 20, "impactScore": 100 }, { "timeCost": 30, "impactScore": 120 }], timeBudget = 50

Output:

220

Note:

Projects available: P1 (10, 60), P2 (20, 100), P3 (30, 120). Budget = 50.

  • Selecting P1 and P2: total timeCost = 10 + 20 = 30, total impactScore = 60 + 100 = 160.
  • Selecting P2 and P3: total timeCost = 20 + 30 = 50, total impactScore = 100 + 120 = 220.
  • Selecting P1 and P3: total timeCost = 10 + 30 = 40, total impactScore = 60 + 120 = 180.

The maximum achievable impact score is 220.

2

Example 2

Input:

projects = [{ "timeCost": 5, "impactScore": 10 }, { "timeCost": 4, "impactScore": 40 }, { "timeCost": 6, "impactScore": 30 }, { "timeCost": 3, "impactScore": 50 }], timeBudget = 10

Output:

90

Note:

Projects available: P1 (5, 10), P2 (4, 40), P3 (6, 30), P4 (3, 50). Budget = 10.

  • The optimal combination is P2 (4, 40) and P4 (3, 50). Total timeCost = 4 + 3 = 7 (<= 10), total impactScore = 40 + 50 = 90.
3

Example 3

Input:

projects = [{ "timeCost": 60, "impactScore": 100 }], timeBudget = 50

Output:

0

Note:

The only project available has a timeCost of 60, which exceeds the timeBudget of 50. No projects can be selected, resulting in a total impactScore of 0.

Constraints

Constraints & assumptions

  • 1 <= projects.length <= 100
  • 0 <= timeBudget <= 5000
  • 1 <= projects[i].timeCost <= 500
  • 1 <= projects[i].impactScore <= 1000
  • All timeCost and impactScore values are integers.
  • The solution should aim for a time complexity of O(N * W) where N is projects.length and W is timeBudget.

What interviewers evaluate

  • Algorithmic Correctness: The solution accurately computes the maximum impact score under all valid inputs and edge cases.
  • Efficiency: The chosen algorithm demonstrates optimal time and space complexity for the given constraints.
  • Problem-Solving Approach: The candidate identifies the underlying algorithmic pattern (e.g., Knapsack) and applies dynamic programming effectively.
  • Code Quality: The code is well-structured, readable, and handles input parameters gracefully.

Loading editor...