Put Marbles in Bags
Asked at Salesforce
Problem
You have n bags of marbles, each with some number of marbles. You are given an integer array weights of length n where weights[i] is the number of marbles in the i-th bag. You must split the marbles into exactly k non-empty groups (bags). The cost of a group is the sum of the weights in that group. The total cost is the sum of the costs of all k groups. Find the minimum and maximum possible total cost of splitting the marbles into k groups.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | HARD | View all Salesforce questions → |
How to Think About It
Brute force: try all ways to partition n marbles into k non-empty groups — exponential and infeasible.
Key insight: the cost of a split depends on the endpoints of consecutive elements. For a sorted array, adjacent differences matter.
For minimum cost: sort the array, compute adjacent differences, and greedily select the k-1 smallest differences to avoid splitting.
For maximum cost: sort the array, compute adjacent differences, and greedily select the k-1 largest differences to create splits.
Optimal: O(n log n) time for sorting. Use a min-heap or max-heap of size k to track the k-1 differences, or simply sort the differences array.
Optimal Approach
Sort the weights array. Compute the differences between each pair of adjacent elements. The minimum cost is achieved by keeping the k-1 smallest differences as merge points (avoiding those splits), and the maximum cost by choosing the k-1 largest differences as split points. Specifically, the min cost is weights[0] + weights[n-1] + sum of the smallest (n-k) adjacent differences, and the max cost is the same base plus the sum of the largest (n-k) adjacent differences. Use a heap or simply sort the differences to extract the required values. Total time is O(n log n) due to sorting.
What Trips People Up in Real Interviews
Clarify whether the bags are distinguishable or indistinguishable — here they are indistinguishable.
Work through a small example (e.g., weights = [1, 3, 5, 1], k = 2) to find the pattern.
Explain why sorting the weights first is the right approach — the optimal splits use contiguous sorted elements.
Describe the greedy strategy clearly: differences between adjacent sorted elements represent potential split costs.
Mention that the minimum uses the k-1 smallest gaps and the maximum uses the k-1 largest gaps.
Solution Code
def putMarbles(weights, k):
n = len(weights)
if k == 1 or k == n:
return 0
diffs = []
for i in range(n - 1):
diffs.append(weights[i] + weights[i + 1])
diffs.sort()
pairs = n - k
minCost = sum(diffs[:pairs])
maxCost = sum(diffs[pairs:])
return maxCost - minCostFrequently Asked Questions
What is the Put Marbles in Bags problem?
You have n bags of marbles, each with some number of marbles. You are given an integer array weights of length n where weights[i] is the number of marbles in the i-th bag. You must split the marbles into exactly k non-empty groups (bags). The cost of a group is the sum of the weights in that group. The total cost is the sum of the costs of all k groups. Find the minimum and maximum possible total cost of splitting the marbles into k groups.
How do you solve Put Marbles in Bags?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Put Marbles in Bags?
Put Marbles in Bags is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Put Marbles in Bags?
- Clarify whether the bags are distinguishable or indistinguishable — here they are indistinguishable.
- Work through a small example (e.g., weights = [1, 3, 5, 1], k = 2) to find the pattern.
- Explain why sorting the weights first is the right approach — the optimal splits use contiguous sorted elements.
- Describe the greedy strategy clearly: differences between adjacent sorted elements represent potential split costs.
- Mention that the minimum uses the k-1 smallest gaps and the maximum uses the k-1 largest gaps.