Stone Game III

HardDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Stones are laid out in a row, and stoneValue[i] is the (possibly negative) value of the i-th stone. Alice and Bob alternate turns, with Alice moving first. On a turn, the current player takes the next **1, 2, or 3** stones from the front of the row and adds their values to their own score. The game ends when no stones remain. Both players start at score 0 and both play to maximize their own final result. Return "Alice" if Alice finishes with a higher score, "Bob" if Bob does, or "Tie" if the scores are equal.

Examples

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Whatever Alice takes, Bob can take the 7 and finish ahead.
Input: stoneValue = [1,2,3,-9]
Output: "Alice"
Alice takes 1, 2, 3 (score 6); Bob is forced to take -9.
Input: stoneValue = [1,2,3,6]
Output: "Tie"
Alice takes 1, 2, 3 and Bob takes 6: 6 to 6.

Constraints

  • 1 <= stoneValue.length <= 5 * 10^4
  • -1000 <= stoneValue[i] <= 1000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems