Determine winner in optimal-play card game
Company: Affirm
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a row of N cards with integer values (values may be positive, zero, or negative), two players alternately pick either the leftmost or rightmost card. Both play optimally to maximize their total sum. Implement a function winner_score(cards: List[int]) -> int that returns the maximum score difference (first − second). Then:
- Explain your time and space complexity.
- Modify the function to also return one optimal sequence of picks (as a list of indices).
Constraints: 1 ≤ N ≤ 2000.
Quick Answer: Determine winner in optimal-play card game evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a row of N cards with integer values (values may be positive, zero, or negative), two players alternately pick either the leftmost or rightmost card from the row. Player 1 moves first, and both players play optimally to maximize their own total sum.
Implement a function `winnerScore(cards)` that returns the **maximum score difference** (Player 1's total minus Player 2's total) achievable when both players play optimally.
A positive result means Player 1 ends up ahead; a negative result means Player 2 ends up ahead; zero is a tie.
**Example 1:**
```
Input: cards = [5, 3, 7, 10]
Output: 5
Explanation: Player 1 takes 10 (right). Remaining [5,3,7]. Optimal play
from here gives Player 1 a net advantage of 5.
```
**Example 2:**
```
Input: cards = [1, 100, 1]
Output: -98
Explanation: Player 1 must take a 1 (left or right). Player 2 then takes the
100. Player 1's score is 1 + 1 = 2, Player 2's is 100, difference = 2 - 100 = -98.
```
Follow-ups to discuss after solving: (1) state your time and space complexity, and (2) how you would modify the function to also return one optimal sequence of picks as a list of indices.
Constraints
- 1 <= N <= 2000
- Card values may be positive, zero, or negative
- Player 1 moves first; both play optimally to maximize their own total
Examples
Input: ([1, 2, 3, 4, 5],)
Expected Output: 3
Explanation: Optimal interval DP yields a net advantage of 3 for the first player.
Input: ([5, 3, 7, 10],)
Expected Output: 5
Explanation: Player 1 takes 10; remaining [5,3,7] gives a net advantage of 5.
Hints
- Define dp[i][j] as the best score difference (current mover's total minus the other player's total) achievable on the subarray cards[i..j].
- When it's your turn on cards[i..j], you take either cards[i] or cards[j]; the opponent then plays optimally on the remaining range. Since dp is from the mover's perspective, subtract the opponent's resulting difference: dp[i][j] = max(cards[i] - dp[i+1][j], cards[j] - dp[i][j-1]).
- Base case: dp[i][i] = cards[i]. Fill the table by increasing subarray length so smaller ranges are computed before larger ones. The answer is dp[0][n-1].
- To recover the picks, store which choice (left or right) achieved each dp[i][j], then walk from [0, n-1] following those choices.