The Rearranging Fruits problem gives you two baskets of fruits (as arrays). You can swap a fruit from basket1 with a fruit from basket2 at a cost equal to the minimum of the two fruit values. Find the minimum total cost to make both baskets contain the same multiset of fruits, or return -1 if impossible. This hard coding problem uses greedy matching with median-swapping optimization. The array, hash table, sort, and greedy interview pattern is the core.
Microsoft, Meta, Amazon, TikTok, and Bloomberg ask this hard problem because it requires recognizing the optimal swap strategy: pair each "excess" element in basket1 with each "deficit" element in basket2, sorted to minimize costs. The median-swap trick (swapping through the globally minimum fruit) further reduces costs.
Frequency balance + sorted greedy with median trick. Compute frequency difference: elements excess in basket1 matched with elements excess in basket2. The total excess must balance (same total elements). Sort excess lists. For each pair (excess from b1, excess from b2): cost = min(min(excess_val, other_val), 2 × global_min). The factor of 2 accounts for routing through the global minimum fruit.
basket1=[4,2,2,2], basket2=[1,4,1,2]. Freq diff: {1:has extra in basket2, 2:has extra in basket1}. Excesses: basket1 has extra 2, basket2 has extra 1. Sort both: [2],[1]. Swap 2↔1: cost=min(1,2,2*1)=1. Total = 1.
Rearranging Fruits requires the "median route" optimization — swapping through the cheapest element can be cheaper than direct swap. The pattern: pair excesses in sorted order, for each pair take the minimum of (direct swap cost, routing through global min × 2). Practice similar "two-basket balancing" problems where intermediate swaps are cheaper.
