Frontend School

Multi-Resource Feature Allocation

DSA
hard

Multi-Resource Feature Allocation

Hard
Dynamic Programming
Knapsack
Resource Allocation

Overview

Zoho is expanding its cloud infrastructure, and a critical task involves efficiently deploying new software features onto shared server resources. Each feature requires specific amounts of CPU and Memory and offers a distinct business value. To maximize the utility of a single server, we need to select a subset of features that can be deployed without exceeding the server's total CPU and Memory capacities, while yielding the highest possible aggregated business value.

What you need to do / Task

Your task is to implement a function that determines the maximum total business value achievable by deploying features onto a single server, given the resource requirements of each feature and the server's capacities.

  1. Implement the function maximizeFeatureValue with the specified signature.
  2. The function should calculate the maximum sum of values from selected features.
  3. The sum of cpuRequirements for selected features must not exceed maxCpuCapacity.
  4. The sum of memoryRequirements for selected features must not exceed maxMemoryCapacity.
  5. Each feature can either be deployed entirely or not at all (0/1 choice).

Input & output

  • cpuRequirements: An array of numbers, where cpuRequirements[i] is the CPU units needed for the i-th feature.
  • memoryRequirements: An array of numbers, where memoryRequirements[i] is the memory units needed for the i-th feature.
  • values: An array of numbers, where values[i] is the business value of the i-th feature.
  • maxCpuCapacity: A number representing the total CPU units available on the server.
  • maxMemoryCapacity: A number representing the total memory units available on the server.
  • Return: A number representing the maximum total business value that can be achieved.

Clarifications

  • All input arrays (cpuRequirements, memoryRequirements, values) will have the same length, N.
  • If no features can be deployed within the given capacities, the function should return 0.
  • Features are indivisible; you cannot deploy a fraction of a feature.

Examples

1

Example 1

Input:

cpuRequirements = [1, 2, 3], memoryRequirements = [1, 2, 3], values = [10, 20, 30], maxCpuCapacity = 3, maxMemoryCapacity = 3

Output:

30

Note:

You can either take feature 3 (CPU 3, Mem 3, Value 30) or features 1 and 2 together (Total CPU 3, Total Mem 3, Total Value 10+20=30). Both yield a maximum value of 30.

2

Example 2

Input:

cpuRequirements = [2, 3, 4], memoryRequirements = [3, 2, 1], values = [15, 20, 10], maxCpuCapacity = 5, maxMemoryCapacity = 5

Output:

35

Note:

Taking feature 1 (CPU 2, Mem 3, Val 15) and feature 2 (CPU 3, Mem 2, Val 20) results in a total CPU of 5, total Memory of 5, and total Value of 35. Feature 3 cannot be added without exceeding capacities or reducing value.

3

Example 3

Input:

cpuRequirements = [100], memoryRequirements = [100], values = [100], maxCpuCapacity = 50, maxMemoryCapacity = 50

Output:

0

Note:

The only feature requires 100 CPU and 100 Memory, which exceeds the server's capacity of 50 CPU and 50 Memory. Thus, no features can be deployed, resulting in a total value of 0.

Constraints

Constraints & assumptions

  • 1 <= N <= 50 (number of features)
  • 1 <= cpuRequirements[i], memoryRequirements[i], values[i] <= 1000
  • 1 <= maxCpuCapacity, maxMemoryCapacity <= 500
  • All input values (cpuRequirements, memoryRequirements, values, maxCpuCapacity, maxMemoryCapacity) are non-negative integers.

Out of scope

  • Optimizing feature deployment across multiple servers.
  • Considering feature dependencies or specific deployment order.
  • Handling negative resource requirements or values (inputs are guaranteed positive).

What interviewers evaluate

  • Correct identification and application of dynamic programming principles (specifically, a multi-dimensional knapsack problem variant).
  • Optimal time and space complexity suitable for the given constraints.
  • Clarity, correctness, and robustness of the implementation.
  • Effective handling of edge cases, such as scenarios where no features can be deployed.

Loading editor...