Coins in a Line

Source

Here is an interview question you would expect from a typical Google interview, which is an interesting problem itself. Different solutions from multiple perspectives are provided in this post.

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

U.S. coins in various denominations in a line. Two players take turn to pick a coin from one of the ends until no more coins are left. Whoever with the larger amount of money wins.

My Attempt

1. sum all even positions and odd positions. Whichever is greater players takes those positions.

2.

int optimalSequenceValue (int arr[ ] , int left, int right, bool player, int P[ ] [ ])

{

if (left == right) // last element

return 0;

if (player == PLAYER1) // pick one left or right and select max of the output

p[left] [right] = max (arr[left] + optimalSequenceValue (arr, left + 1, right, P) ,

arr[righjt] + optimalSequenceValue (arr, left, right -1 , P)

return p[left][right];

if(player == PLAYER2) // value doesnt count just skip

return max (optimalSequenceValue (arr, left + 1, right, P) ,

optimalSequenceValue (arr, left, right -1 , P)

}

with values in P[][] we could back track the pattern.