Ball picking game: take one or two from the front

0
⑂ RemixPractice
Practice

Balls stand in a single line. Each ball has an integer value, which may be positive, zero, or negative. Two players take turns, and player 1 moves first. Both start with a score of 0.

On each turn, the player to move must take either one or two balls from the front of the line and adds their values to their score. A player cannot pass, so when one ball is left the player to move must take it, even if its value is negative. The game ends when the line is empty.

Both players play optimally, and each wants to maximize their own final score.

Implement:

def final_scores(balls: list[int]) -> tuple[int, int]:
    """Return (player 1 score, player 2 score) under optimal play."""

def first_player_wins(balls: list[int]) -> bool:
    """Return True if player 1 ends with at least as many points as player 2."""

Constraints

  • 0 <= len(balls) <= 10^5
  • -10^4 <= balls[i] <= 10^4

Example 1

balls = [2, -1, 6]
final_scores(balls)      -> (2, 5)
first_player_wins(balls) -> False

If player 1 takes 2, player 2 takes -1, 6 for 5. If player 1 takes 2, -1 (1 point), player 2 takes 6. Player 1 picks the first line, and still loses 2 to 5.

Example 2

balls = [4, -9, 1, 3]
final_scores(balls) -> (7, -8)

Player 1 takes 4. Player 2 must now start with -9, and takes -9, 1. Player 1 takes 3.

Be ready to explain how your answer changes if a player may take up to k balls per turn, or may take from either end of the line.

Reconstructed from the reported question; details may differ from what interviewers ask.

GoogleCodingHard
by Frontier Interview· 1 day ago· 7 min read

What L5 looks like

  • Explains the zero-sum argument on their own and recovers both scores from the margin and the total.
  • Gets O(1) space and avoids recursion-depth limits without being prompted.
  • Handles follow-up 1 with prefix sums, and reconstructs an optimal line of play.
  • Writes a brute-force oracle and randomized tests, and shows a counterexample to greedy.
Interviewer expectations for every level ↓

Approach

The game is zero-sum with a fixed total. Every ball ends up with one of the two players, so mine + theirs = total at the end. Maximizing your own total is the same as maximizing mine - theirs. That turns "both players maximize their own profit" into a clean minimax problem with a single number to optimize.

State. Balls are always taken from the front, so the only thing that changes is how many are left. The state is the index i of the first remaining ball. Whose turn it is does not matter if we score the position from the point of view of the player to move.

Brute force. Recurse: the player to move tries taking 1 ball and taking 2 balls, and for each one subtracts the best the opponent can do on the rest. Without caching this is the Fibonacci tree, O(phi^n). Say this out loud and then add the cache.

DP on the margin. Let best[i] be the best margin (mover's points minus the other player's points from here on) that the player to move can force on balls[i:].

  • best[n] = 0 (no balls left).
  • best[i] = max(balls[i] - best[i+1], balls[i] + balls[i+1] - best[i+2]), using the second option only when i + 1 < n.

The minus sign is the whole trick. After you move, the opponent becomes "the player to move" and their best margin counts against you.

Getting the scores back. With d = best[0] and T = sum(balls), player 1 gets (T + d) / 2 and player 2 gets (T - d) / 2. The sum and the difference always have the same parity, so the division is exact.

Negative balls. A move must take at least one ball, and the game only ends when the line is empty. So a player can be forced to take a negative ball. The recurrence already handles this: it only offers legal moves, and with one ball left the only legal move is to take it. Do not add a "skip" or a max(0, ...) clamp. That would be a different game.

Invariant. When we fill best[i], best[i+1] and best[i+2] are already final. We sweep i from right to left. Only two later values are ever read, so the table shrinks to two variables for O(1) space.

Reconstructing play. Keep the full best array and, at each step, take the move that achieves best[i]. This gives one optimal line of play, which interviewers often ask for as a follow-up.

Code

from functools import lru_cache
from typing import List, Tuple


def margin_brute(balls: List[int]) -> int:
    """Memoized minimax. Best (mover - other) margin from the start."""
    n = len(balls)

    @lru_cache(maxsize=None)
    def go(i: int) -> int:
        if i == n:
            return 0
        res = balls[i] - go(i + 1)
        if i + 1 < n:
            res = max(res, balls[i] + balls[i + 1] - go(i + 2))
        return res

    return go(0)


def margin_table(balls: List[int]) -> List[int]:
    """best[i] = best margin for the player to move on balls[i:]."""
    n = len(balls)
    best = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        best[i] = balls[i] - best[i + 1]
        if i + 1 < n:
            best[i] = max(best[i], balls[i] + balls[i + 1] - best[i + 2])
    return best


def final_scores(balls: List[int]) -> Tuple[int, int]:
    """(player 1 score, player 2 score) under optimal play. O(n) time, O(1) space."""
    nxt1, nxt2 = 0, 0          # best[i+1], best[i+2]
    n = len(balls)
    for i in range(n - 1, -1, -1):
        cur = balls[i] - nxt1
        if i + 1 < n:
            cur = max(cur, balls[i] + balls[i + 1] - nxt2)
        nxt1, nxt2 = cur, nxt1
    total = sum(balls)
    d = nxt1
    return (total + d) // 2, (total - d) // 2


def first_player_wins(balls: List[int]) -> bool:
    """True if player 1 finishes with at least as much as player 2."""
    p1, p2 = final_scores(balls)
    return p1 >= p2


def optimal_play(balls: List[int]) -> List[int]:
    """One optimal sequence of move sizes (1 or 2), alternating players."""
    best = margin_table(balls)
    n, i, moves = len(balls), 0, []
    while i < n:
        take_one = balls[i] - best[i + 1]
        if i + 1 < n and balls[i] + balls[i + 1] - best[i + 2] > take_one:
            moves.append(2)
            i += 2
        else:
            moves.append(1)
            i += 1
    return moves


if __name__ == "__main__":
    import random

    assert final_scores([]) == (0, 0)
    assert final_scores([7]) == (7, 0)
    assert final_scores([-4]) == (-4, 0)
    assert final_scores([3, 5]) == (8, 0)
    assert final_scores([2, -1, 6]) == (2, 5)
    assert final_scores([4, -9, 1, 3]) == (7, -8)
    assert final_scores([-1, -1, -1]) == (-2, -1)
    assert first_player_wins([4, -9, 1, 3])
    assert not first_player_wins([2, -1, 6])
    assert optimal_play([4, -9, 1, 3]) == [1, 2, 1]
    assert final_scores([5, 1, 100]) == (6, 100)

    for _ in range(2000):
        arr = [random.randint(-10, 10) for _ in range(random.randint(0, 12))]
        best = margin_table(arr)
        assert best[0] == margin_brute(arr)
        p1, p2 = final_scores(arr)
        assert p1 + p2 == sum(arr) and p1 - p2 == best[0]
        # Replaying the reconstructed moves reproduces the scores.
        scores, i = [0, 0], 0
        for turn, k in enumerate(optimal_play(arr)):
            scores[turn % 2] += sum(arr[i:i + k])
            i += k
        assert tuple(scores) == (p1, p2)
    print("all tests passed")

Complexity

  • final_scores: O(n) time, O(1) extra space (two rolling values).
  • margin_table and optimal_play: O(n) time, O(n) space for the table.
  • margin_brute: O(n) time and O(n) space with the cache, but O(n) recursion depth, so it fails on long inputs in Python. Without the cache it is exponential.

Test cases

  • [] -> (0, 0). Empty line, nobody scores.
  • [7] -> (7, 0). Single ball goes to player 1.
  • [-4] -> (-4, 0). Player 1 is forced to take a negative ball.
  • [3, 5] -> (8, 0). Player 1 takes both.
  • [2, -1, 6] -> (2, 5). Every opening loses for player 1. Taking 2 leaves the opponent [-1, 6], and they take both for 5. Taking 2, -1 leaves them the 6. Player 2 wins.
  • [4, -9, 1, 3] -> (7, -8). Player 1 takes 4, so player 2 must start with -9. Their best reply is -9, 1, which leaves player 1 only the 3. Taking -9 alone would hand player 1 1, 3. Optimal moves: [1, 2, 1].
  • [-1, -1, -1] -> (-2, -1). Taking one ball leaves [-1, -1], where player 2 takes one and forces player 1 to take the last. Taking two leaves player 2 just one. Either way player 1 ends at -2. Negative balls can be a forced loss.
  • [1, 1, 1] -> (2, 1). Player 1 takes two.
  • [5, 1, 100] -> (6, 100). All-positive input can still lose for player 1: every opening hands the 100 to player 2. Taking two is best because it gives up only the 100.
  • Large n (say 10^6): the iterative version runs in linear time with no recursion limit issue.

Follow-ups

  1. Take 1 to k balls per turn. Same margin DP: best[i] = max over j in 1..k of (prefix[i+j] - prefix[i]) - best[i+j]. That is O(nk). Prefix sums make each option O(1). For large k, rewrite as max over j of (prefix[i+j] - best[i+j]) - prefix[i] and keep a sliding-window maximum (monotonic deque) over prefix[t] - best[t], which gives O(n).
  2. Take from either end (Predict the Winner style). The state becomes an interval [l, r]. best[l][r] = max(balls[l] - best[l+1][r], balls[r] - best[l][r-1]), plus the two-ball variants if allowed (both from the left, both from the right, or one from each end, depending on the rules you agree on). O(n^2) time, O(n) space if you fill by interval length with a rolling row.
  3. Who wins, and how are ties handled. Return p1 >= p2, p1 > p2, or a three-way result, depending on the stated tie rule. Ask before you code. Some versions also ask for the winning first move, which is the argmax at i = 0.
  4. Three or more players. The game is no longer two-player zero-sum, so a single margin is not enough. Each state stores a score vector, and the player to move picks the option that maximizes their own entry. Ties between options then affect other players, so you need a tie-break rule. O(n * p) time for p players.
  5. A player may pass, or the game ends early. Adding a pass creates cycles (both players pass forever), so you need a rule such as "two passes in a row end the game", and the state must include whether the last move was a pass. This is a good check that the candidate sees why "must take at least one" matters.

Interviewer expectations

Mid-level (L4)

  • Reduces "both maximize their own score" to a margin, or to a correct two-score recursion.
  • Writes a memoized recursion that is correct, including the forced move on the last ball and negative values.
  • Converts to bottom-up DP when asked and states O(n) time.

Senior (L5)

  • Explains the zero-sum argument on their own and recovers both scores from the margin and the total.
  • Gets O(1) space and avoids recursion-depth limits without being prompted.
  • Handles follow-up 1 with prefix sums, and reconstructs an optimal line of play.
  • Writes a brute-force oracle and randomized tests, and shows a counterexample to greedy.

Staff (L6+)

  • Pins down the rules first: where balls are taken from, tie rule, whether passing is allowed, what to return.
  • Gets the O(n) sliding-window version for large k, and the interval DP for picking from both ends.
  • Explains why the margin trick fails with three players and what replaces it, including tie-breaking.
Sign in to highlight and take notes

Make it yours

Write each chapter yourself, check it against this answer, then let the coach grill you.

PracticeGrill me
Related questions