How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Affirm.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Affirm during technical interviews.

Determine winner in optimal-play card game

Quick Overview

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.

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.

Input: ([8, 15, 3, 7],)

Expected Output: 11

Explanation: First player can secure a large lead by controlling access to 15.

Input: ([10],)

Expected Output: 10

Explanation: Single card: Player 1 takes it, difference is 10.

Input: ([2, 2],)

Expected Output: 0

Explanation: Two equal cards: each player takes one, difference is 0.

Input: ([-1, -2, -3],)

Expected Output: -2

Explanation: All negative values; optimal play forces Player 1 behind by 2.

Input: ([0, 0, 0, 0],)

Expected Output: 0

Explanation: All zeros: any sequence of picks yields a difference of 0.

Input: ([1, 100, 1],)

Expected Output: -98

Explanation: Player 1 is forced to leave the 100 for Player 2, ending 98 behind.

Input: ([4, -1, 2, -3, 5],)

Expected Output: -5

Explanation: Mixed signs with an odd count; optimal play leaves Player 1 behind by 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.

Quick Overview