Maximum Score From Removing Stones

Maximum Score From Removing Stones

1. What is this problem about?

The Maximum Score From Removing Stones interview question is a game-like optimization problem. You have three piles of stones with sizes a, b, and c. In each turn, you can take one stone from two different non-empty piles and add 1 to your score. The goal is to maximize the total score you can get until at most one pile is non-empty.

This problem can be solved either by simulating the process with a greedy approach or by finding a mathematical formula.

2. Why is this asked in interviews?

Google and other companies ask the Maximum Score From Removing Stones coding problem to test a candidate's ability to identify optimal strategies and simplify mathematical relationships. It evaluates whether you can recognize that to stay in the game as long as possible, you should always remove stones from the two largest piles. It also checks if you can derive the $O(1)$ mathematical solution based on the sum and the maximum pile size.

3. Algorithmic pattern used

The Math, Heap (Priority Queue), Greedy interview pattern covers the different approaches.

• Greedy (Simulation): Put the pile sizes into a Max-Heap. In each step, extract the two largest, decrement them, and if they are still > 0, push them back.
• Mathematical: Let the sum be S = a + b + c and the largest pile be M = max(a, b, c).
  • If M > S - M, then the other two piles will be exhausted first, and the score is S - M.
  • Otherwise, you can perfectly (or almost perfectly) pair all stones, and the score is floor(S / 2).

4. Example explanation

Piles: 2, 4, 6. Sum S=12, Max M=6.

• M=6, S-M=6. Since M is not greater than S-M, score = S/2 = 6. Check via simulation:
• (2, 4, 6) -> (2, 3, 5) -> (2, 2, 4) -> (1, 1, 4) -> (0, 0, 4). Stop. Wait, simulation:
• (2, 4, 6) -> (2, 3, 5) [Score 1]
• (2, 2, 4) [Score 2]
• (1, 2, 3) [Score 3]
• (1, 1, 2) [Score 4]
• (0, 1, 1) [Score 5]
• (0, 0, 0) [Score 6] Max score is 6.

5. Common mistakes candidates make

A common error in the Maximum Score From Removing Stones coding problem is not always picking the two largest piles. If you pick smaller piles first, you might end up with one very large pile and two empty ones sooner than necessary. Another mistake is over-complicating the logic with recursion when a simple while-loop (greedy) or a formula (math) is much better.

6. Interview preparation tip

For "game" problems involving piles or counts, always explore the greedy strategy of "balancing" the piles first. If you can keep the piles as even as possible, you can usually continue the game for more turns. Also, try to find an $O(1)$ formula after you've implemented the simulation—interviewers love to see that extra bit of mathematical insight.