How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Walmart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Walmart during technical interviews.

Minimize Cost for Feature-Capable Models

Company: Walmart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given `n` machine learning models. Model `i` has a positive integer cost `cost[i]` and a two-character binary string `featureAvailability[i]` describing which features it supports: - `"00"`: supports neither Feature A nor Feature B - `"01"`: supports only Feature B - `"10"`: supports only Feature A - `"11"`: supports both Feature A and Feature B For an integer `k`, a selected set of models is called **k-capable** if the set contains at least `k` models that support Feature A and at least `k` models that support Feature B. A model with availability `"11"` counts toward both requirements. For every integer `k` from `1` to `n`, determine the minimum total cost required to select a k-capable set of models. If no such set exists for a given `k`, return `-1` for that `k`. Return an array `answer` of length `n`, where `answer[k - 1]` is the minimum cost for `k`. Example: ```text cost = [3, 2, 7, 5, 1] featureAvailability = ["10", "01", "11", "10", "00"] ``` For `k = 1`, selecting the model with `"11"` costs `7`, but selecting the `"10"` model with cost `3` and the `"01"` model with cost `2` costs `5`, so the minimum is `5`. For `k = 2`, one valid choice is models with costs `3`, `2`, and `7`, giving two Feature A supporters and two Feature B supporters, with total cost `12`. If larger `k` values cannot be satisfied, their result should be `-1`.

Quick Answer: This question evaluates algorithmic problem-solving and combinatorial optimization skills related to selecting cost-minimal subsets that satisfy dual feature-coverage constraints.

You are given n machine learning models. Model i has a positive integer cost cost[i] and a two-character binary string featureAvailability[i]. The string describes whether the model supports Feature A and/or Feature B: "00" supports neither, "01" supports only Feature B, "10" supports only Feature A, and "11" supports both. For an integer k, a selected set of models is k-capable if it contains at least k models supporting Feature A and at least k models supporting Feature B. A model with availability "11" counts toward both requirements. For every k from 1 to n, return the minimum total cost needed to select a k-capable set. If it is impossible for a k, return -1 for that k.

Constraints

0 <= n == len(cost) == len(featureAvailability) <= 2 * 10^5
1 <= cost[i] <= 10^9
featureAvailability[i] is one of "00", "01", "10", "11"
If n = 0, return an empty list

Examples

Input: ([3, 2, 7, 5, 1], ["10", "01", "11", "10", "00"])

Expected Output: [5, 12, -1, -1, -1]

Explanation: For k=1, the cheapest option is the A-only model costing 3 plus the B-only model costing 2, total 5. For k=2, add the "11" model costing 7, total 12. Larger k values cannot be satisfied.

Input: ([4, 1, 6], ["11", "11", "00"])

Expected Output: [1, 5, -1]

Explanation: Only the two "11" models help. The cheapest cost for k=1 is 1, and for k=2 both useful models are needed, costing 1+4=5.

Input: ([5, 5, 2, 8, 1, 4], ["10", "01", "10", "01", "11", "00"])

Expected Output: [1, 8, 21, -1, -1, -1]

Explanation: The "11" model costing 1 satisfies k=1. For additional capability levels, pair the cheapest remaining A-only and B-only models: 2+5=7, then 5+8=13. Prefix totals are 1, 8, and 21.

Input: ([3, 2, 1], ["10", "00", "10"])

Expected Output: [-1, -1, -1]

Explanation: There are no models supporting Feature B, so no k-capable set exists for any k.

Input: ([], [])

Expected Output: []

Explanation: There are no models and no k values to answer.

Hints

Models with availability "00" can be ignored because costs are positive and they do not help either requirement.
Think of satisfying one level of k as either choosing one "11" model, or choosing one "10" model together with one "01" model.

Quick Overview

This question evaluates algorithmic problem-solving and combinatorial optimization skills related to selecting cost-minimal subsets that satisfy dual feature-coverage constraints.