Frontend School

Project Optimization for Security Compliance

DSA
medium

Project Optimization for Security Compliance

Medium
Dynamic Programming
Knapsack

Overview

As a Project Manager at a leading software company, you are responsible for ensuring your product meets stringent security compliance standards. To achieve this, you have a set of available security patches, each with an associated development cost and a specific boost to the overall security score. Your goal is to select a subset of these patches to apply, such that the cumulative security score meets or exceeds a predefined minimum target, while minimizing the total development cost. You also operate under a strict total development budget.

This problem evaluates your ability to apply dynamic programming techniques to optimize resource allocation under multiple constraints, a common challenge in software development planning.

What you need to do / Task

Implement the function minCostToSecureProject that calculates the minimum total development cost required to achieve at least the minSecurityTarget security score, without exceeding the totalBudget. If it's impossible to meet the minSecurityTarget within the totalBudget, the function should return -1.

You must select each patch at most once.

Input & Output

Function Signature (TypeScript):

function minCostToSecureProject(
    costs: number[],
    securityBoosts: number[],
    totalBudget: number,
    minSecurityTarget: number
): number

Parameters:

  • costs: An array of positive integers, where costs[i] represents the development cost of the i-th security patch.
  • securityBoosts: An array of positive integers, where securityBoosts[i] represents the security score boost provided by the i-th security patch.
  • totalBudget: A positive integer representing the maximum total development cost you can incur.
  • minSecurityTarget: A positive integer representing the minimum cumulative security score that must be achieved.

Return Value:

  • A single integer representing the minimum total cost to achieve the minSecurityTarget, or -1 if it's not possible within the totalBudget.

Clarifications

  • All costs and security boosts are positive integers.
  • The number of patches (costs.length and securityBoosts.length) will always be the same.
  • If multiple combinations of patches achieve the minSecurityTarget (or higher), return the one with the absolute minimum cost, provided that cost does not exceed totalBudget.
  • If minSecurityTarget is 0, the minimum cost is 0 (as no patches are needed).

Examples

1

Example 1

Input:

costs = [10, 20, 30], securityBoosts = [5, 12, 18], totalBudget = 50, minSecurityTarget = 17

Output:

30

Note:

Selecting patches with costs [10, 20] gives a total cost of 30 and security boost of 17, meeting the target. Selecting the patch with cost [30] also gives a total cost of 30 and security boost of 18, also meeting the target. Both are optimal, so 30 is the minimum.

2

Example 2

Input:

costs = [50, 60], securityBoosts = [10, 15], totalBudget = 100, minSecurityTarget = 30

Output:

-1

Note:

The maximum security boost achievable with the given patches is 25 (by selecting both patches, total cost 110). Even if we ignore the budget, 25 is less than the minSecurityTarget of 30. Thus, it's impossible to meet the target.

3

Example 3

Input:

costs = [100, 20, 70], securityBoosts = [30, 10, 25], totalBudget = 80, minSecurityTarget = 25

Output:

70

Note:

Selecting the patch with cost 70 provides a security boost of 25, meeting the target exactly within the budget. Other combinations either exceed the budget or don't meet the target.

Constraints

Constraints & Assumptions

  • 1 <= N <= 100, where N is the number of security patches.
  • 1 <= costs[i] <= 1000
  • 1 <= securityBoosts[i] <= 200
  • 1 <= totalBudget <= 100000
  • 1 <= minSecurityTarget <= 20000 (Note: Maximum possible total security boost is N * max(securityBoosts[i]) = 100 * 200 = 20000)
  • The input arrays costs and securityBoosts will always have the same length.

Out of scope

  • Error handling for invalid input types or values (e.g., negative costs, non-integer inputs). Assume inputs adhere to constraints.
  • Network latency or external API calls.
  • Concurrency or multi-threading considerations.

What interviewers evaluate

  • Correctness of Logic: The solution correctly identifies the minimum cost to meet the security target within the budget, handling edge cases and impossible scenarios.
  • Algorithm Efficiency: The chosen approach is efficient enough (e.g., Dynamic Programming) to solve the problem within typical time limits for the given constraints.
  • Code Structure and Readability: The code is well-organized, easy to understand, and follows reasonable coding practices (e.g., meaningful variable names, clear logic).
  • Problem Decomposition: Ability to break down the problem into subproblems and manage the DP state effectively.

Loading editor...