FastPrep
Problem · Array

Minimum Cost K-Capable Models

● MediumMicrosoftOA
See Microsoft hiring insights

Given n machine learning models, each with an associated cost and feature compatibility:

  • cost[i] represents the cost of the ith model.
  • featureAvailability[i] is a binary string indicating suitability for two distinct features:
    • "00": not equipped for either feature
    • "01": suitable for feature A but not feature B
    • "10": suitable for feature B but not feature A
    • "11": suitable for both features

A set of models is k-capable if the number of models suitable for feature A and the number suitable for feature B are both greater than or equal to k.

For each value of k from 1 to n, determine the minimum cost required to assemble a k-capable set of models. Return an array of n integers, where the ith integer represents the minimum cost for an i-capable set. If no i-capable set exists, the ith integer should be -1.

Examples
01 · Example 1
cost = [3, 6, 9, 1, 2, 5]
featureAvailability = ["10", "01", "11", "01", "11", "10"]
return = [2, 6, 15, 26, -1, -1]

The source table lists these optimal sets:

kOptimal SetFeature 1
Compatible		Feature 2
Compatible		Cost
1[5][5][5]2
2[1, 4, 5][1, 5][4, 5]3 + 1 + 2 = 6
3[1, 3, 4, 5][1, 3, 5][3, 4, 5]3 + 9 + 1 + 2 = 15
4[1, 2, 3, 4, 5,
6]		[1, 3, 5, 6][2, 3, 4, 5]3 + 6 + 9 + 1 + 2 + 5 =
26

For k >= 5, there is no capable set. Hence, the answer is [2, 6, 15, 26, -1, -1].

More Microsoft problems
drafts saved locally
public int[] minimumKCapableModelCosts(int[] cost, String[] featureAvailability) {
  // write your code here
}
cost[3, 6, 9, 1, 2, 5]
featureAvailability["10", "01", "11", "01", "11", "10"]
expected[2, 6, 15, 26, -1, -1]
checking account