Walmart·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Walmart SWE online assessment, one algorithmic problem about selecting ML models to satisfy feature coverage requirements at minimum cost. The problem looked like a greedy/DP hybrid and took me longer than I'd like to admit to even parse correctly.

Questions Asked (1)

You have n ML models, each with a cost and a binary string indicating whether it supports Feature A, Feature B, both, or neither. For each k from 1 to n, find the minimum total cost to select a set of models that includes at least k supporters of Feature A and at least k supporters of Feature B. A model supporting both counts toward either requirement. Return -1 if a given k is impossible.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Spent the first ten minutes just re-reading the problem because the dual-counting on '11' models kept tripping me up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, categorize models into three groups: A-only, B-only, and both. Then, for each k, find the minimum cost to select at least k from A∪Both and at least k from B∪Both, ensuring the intersection (Both) is counted appropriately. Use sorting and prefix sums to efficiently compute the minimum cost for each k, or use a greedy approach with priority queues.

Pro tip: Clarify that models supporting both features are the most flexible and should be prioritized, but sometimes it's cheaper to use separate A-only and B-only models. Discuss trade-offs between time and space complexity, and mention that precomputing prefix sums can reduce per-k computation to O(1) after sorting.

1. Categorize models

Separate models into three lists: those supporting only A, only B, and both. Sort each list by cost ascending.

2. Precompute prefix sums

For each list, compute prefix sums of costs to quickly get the total cost of selecting the cheapest m models from that list.

3. Iterate over number of both models

For each possible number of both models selected (from 0 to total both), determine how many additional A-only and B-only models are needed to meet the requirement for a given k.

4. Compute minimum cost for each k

For each k, take the minimum over all valid choices of both models count, using prefix sums to get costs in O(1). If no valid combination exists, return -1.

5. Optimize and analyze complexity

The overall time complexity is O(n log n) due to sorting, and O(n^2) if iterating naively over both count and k, but can be optimized to O(n log n) or O(n) with two pointers or priority queues.

Key Points to Mention

Categorization of models into A-only, B-only, and both.
Sorting by cost and using prefix sums for efficient cost retrieval.
Handling the overlap of both models: they count toward both requirements.
Edge cases: k greater than available supporters, or no valid set exists.
Time and space complexity trade-offs: O(n log n) sorting, O(n) space for prefix sums.
Greedy approach with priority queues as an alternative to prefix sums.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.