Rearranging Fruits
Asked at Atlassian
Problem
You have two baskets of fruits, basket1 and basket2, each represented as an integer array. You can swap one fruit from basket1 with one fruit from basket2 at a cost equal to the minimum of the two fruit values. The goal is to make both baskets contain the same multiset of fruits (same elements with same frequencies). Return the minimum total cost to achieve this, or return -1 if it is impossible.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | HARD | View all Atlassian questions → |
How to Think About It
Check feasibility first: both baskets must have the same total number of elements, and each fruit value must appear an even number of times across both baskets combined.
Count the frequency of each value across both baskets. Values with odd counts make the problem impossible.
Identify mismatched elements: for each value, find the excess in one basket that needs to be swapped to the other.
Greedy strategy: for each pair of mismatched elements, swap the smaller pair directly if possible. Otherwise, use the globally smallest element as a swap intermediary.
Optimal: O(n log n) time using counting and sorting. The key insight is that you only need to consider the smaller of each mismatched pair or twice the global minimum.
Optimal Approach
First check if a solution is possible: both baskets must have the same length, and every fruit value must have an even total count across both baskets. Count frequencies of each value across both baskets. For each value, compute the excess in basket1 versus basket2 — this gives a list of values that need to be swapped. Split these into two groups: values that need to go from basket1 to basket2, and values that need to go the other way. Sort both lists. The minimum cost is the sum of min(directSwapCost, 2 * globalMin) for each pair, where directSwapCost is the smaller element in each mismatched pair. Use O(n log n) time for sorting.
What Trips People Up in Real Interviews
Start by stating the impossibility conditions clearly — this shows you think about edge cases.
Explain the frequency counting approach: if a value appears an odd total number of times, return -1.
Describe the greedy swap strategy: always try to swap the smaller element directly.
Discuss the role of the global minimum element: it serves as a swap intermediary when direct swap is suboptimal.
Walk through an example where the global minimum is needed to reduce total swap cost.
Solution Code
def minCost(basket1, basket2):
from collections import Counter
total = Counter(basket1) + Counter(basket2)
for v in total.values():
if v % 2 != 0:
return -1
c1 = Counter(basket1)
c2 = Counter(basket2)
swaps = []
for v in total:
diff = c1.get(v, 0) - c2.get(v, 0)
swaps.extend([v] * abs(diff // 2))
if not swaps:
return 0
swaps.sort()
global_min = min(min(basket1), min(basket2))
result = 0
for i in range(len(swaps) // 2):
result += min(swaps[i], 2 * global_min)
return resultFrequently Asked Questions
What is the Rearranging Fruits problem?
You have two baskets of fruits, basket1 and basket2, each represented as an integer array. You can swap one fruit from basket1 with one fruit from basket2 at a cost equal to the minimum of the two fruit values. The goal is to make both baskets contain the same multiset of fruits (same elements with same frequencies). Return the minimum total cost to achieve this, or return -1 if it is impossible.
How do you solve Rearranging Fruits?
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 Rearranging Fruits?
Rearranging Fruits is asked at Atlassian. It is a hard difficulty problem.
What are common mistakes on Rearranging Fruits?
- Start by stating the impossibility conditions clearly — this shows you think about edge cases.
- Explain the frequency counting approach: if a value appears an odd total number of times, return -1.
- Describe the greedy swap strategy: always try to swap the smaller element directly.
- Discuss the role of the global minimum element: it serves as a swap intermediary when direct swap is suboptimal.
- Walk through an example where the global minimum is needed to reduce total swap cost.