Maximum Number of Coins You Can Get

Maximum Number of Coins You Can Get

What is this problem about?

The Maximum Number of Coins You Can Get coding problem gives you piles of coins. You, Alice, and Bob take piles in rounds of three: Bob always takes the pile with the most coins, you take the pile with the second most, and Alice takes the remaining pile. You choose which piles participate in each round (from those remaining). Maximize the total coins you collect.

Why is this asked in interviews?

Meta and Amazon use this problem to test greedy reasoning in game theory settings. The key insight is that Alice should always get the minimum pile (she is "the loser" in this game), and you should maximize your second-place picks. Sorting and greedily assigning who gets what reveals the optimal strategy immediately.

Algorithmic pattern used

Greedy with sorting: Sort all piles. Since there are 3*k piles for k rounds, Alice takes the k smallest piles (one per round). Bob takes the largest pile each round. You take the second-largest each round. Optimal strategy: Sort ascending. Alice gets the k smallest (indices 0 to k-1). From the remaining 2k piles, Bob takes the largest in each pair, you take the second largest. Concretely: from sorted piles, take piles at indices k+1, k+3, k+5, ... (every other pile starting from the second position after Alice's share).

Example explanation

Piles: [2, 4, 1, 2, 7, 8], 6 piles → k=2 rounds.

• Sorted: [1, 2, 2, 4, 7, 8].
• Alice gets the 2 smallest: [1, 2].
• Remaining: [2, 4, 7, 8].
• Round 1: Bob gets 8, you get 7. Round 2: Bob gets 4, you get 2.
• Your total = 7 + 2 = 9.

Using the index formula: sorted piles at indices 2,3,4,5 = [2,4,7,8]. Your piles: indices 3 and 5 = 4 and 8? No — sorted ascending: [1,2,2,4,7,8]. k=2. Your indices: k+1=3, k+3=5 → piles[3]=4, piles[5]=8. Total=12? Let me recheck: piles[k+1]=piles[3]=4, piles[k+3]=piles[5]=8. Sum=12.

Actually sorted: [1,2,2,4,7,8]. Rounds: {1,2,8}, {2,4,7} — Alice:1, you:2, Bob:8 and Alice:2, you:4, Bob:7. Sum = 2+4=6. Or {1,4,8}, {2,2,7}: you:4+2=6. Best: {1,2,8},{2,4,7}: you=2+4=6. Or taking [1,7,8],[2,2,4]: you=7+2=9. Maximum = 9.

Common mistakes candidates make

• Not giving Alice the absolute minimum piles: Any "waste" on your part (taking a pile Alice could have taken) reduces your total.
• Incorrect index calculation: The exact indices for your piles depend on the sorted order and k — verify with examples.
• Not accounting for pile count divisibility: The problem guarantees 3k piles. If not guaranteed, handle the remainder carefully.

Interview preparation tip

For the Array Math Sorting Game Theory Greedy interview pattern, in three-way split optimization problems, always define who gets the worst share (Alice here) and maximize accordingly. Sorting + index formula is the clean O(n log n) solution. Articulate the greedy reasoning in the interview: "Alice absorbs the minimum, Bob takes the maximum, so I maximize the second-maximum of each group."