Problem · Array
Minimum Cost K-Capable Models
Learn this problem● Medium
MicrosoftOA
See Microsoft hiring insightsMicrosoftOAProblem statement
Given n machine learning models, each model has an associated cost and feature compatibility:
cost[i]is the cost of thei-th model.featureAvailability[i]is a two-character binary string:"00": suitable for neither 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 when the number of selected models suitable for feature A and the number suitable for feature B are both at least k.
For every k from 1 through n, determine the minimum cost required to assemble a k-capable set. Return an array of n integers, where the value at index k - 1 is that minimum cost. If no k-capable set exists, return -1 for that position.
Function
minimumKCapableModelCosts(cost: int[], featureAvailability: String[]) → int[]Examples
Example 1
cost = [3, 6, 9, 1, 2, 5]featureAvailability = ["10", "01", "11", "01", "11", "10"]return = [2, 6, 15, 26, -1, -1]The model indices in the source table are 1-based.
k | Optimal set | Feature 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, no capable set exists. Therefore, the answer is [2, 6, 15, 26, -1, -1].