Katkat
Back

Minimize Cost for Feature-Capable Models

Walmart LabsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to use greedy strategies or dynamic programming to satisfy coverage constraints while minimizing total costs from a set of available items.

Problem Statement

You are tasked with selecting a subset of machine learning models to deploy for a service. Each model i has a cost C[i] and supports two features, A and B. Some models support feature A, some support feature B, and some support both.

You must select a subset of models such that at least min_A models providing feature A are included and at least min_B models providing feature B are included. Note: If a model provides both, it counts toward the count of A and the count of B simultaneously. Your goal is to minimize the total cost of the selected models.

Function Signature

def min_cost_to_cover(models, min_A, min_B):

Input

  • models: A list of tuples (cost, supports_A, supports_B), where supports_A and supports_B are booleans.
  • min_A: Integer, the required number of models supporting feature A.
  • min_B: Integer, the required number of models supporting feature B.

Examples

Example 1:

  • models = [(10, True, False), (5, False, True), (2, True, True)]
  • min_A = 1, min_B = 1
  • Output: 7 (Selecting the second and third models gives one A and two Bs for cost 7).

Constraints

  • 1 <= len(models) <= 1000
  • 0 <= cost <= 10000
  • 0 <= min_A, min_B <= 500

Edge Cases

  • It might be impossible to satisfy the constraints; return -1 in this case.
  • If a model supports both features, it is always more efficient to use it if you need both types.

Hints

Hint 1

Categorize the models into four groups: those supporting only A, only B, both A and B, and none.

Hint 2

The models supporting both features are special because they reduce the requirement for both A and B simultaneously.

Hint 3

You can iterate through the number of 'both' models used (from 0 to the total available) and greedily pick the cheapest remaining models to satisfy the remaining A and B requirements.

Follow-up questions

  • How would your approach change if each model had a capacity limit on how many concurrent requests it could handle?
  • What if the requirement was not a count, but a total 'accuracy score' that must reach a threshold?
  • How would you optimize the solution if the number of models was in the millions, but the types of models (cost/features) were limited to a few hundred distinct categories?