Trusted answers to developer questions

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

In the **coin in a line problem**, two players are given an even number of coins in a single row.
The players take turns alternatively. For each turn, a player selects a coin from either the beginning or the end of the row. The player with the maximum total value wins.
â€‹

So, the goal is to provide a strategy in which the player with the first move gets the maximum value coins in the end.

There is an even amount of coins (i.e., 1 to n ) and the two players take their turns alternatively.

If *player1* picks the coin at position 1, then *player2* (who is equally clever) will pick up a coin and leave *player1* with the less valuable coin.

If *player1* picks the coin at position n, then *player2* (who is equally clever) will pick up a coin, and leave *player1â€‹* with the less valuable coin.

```
Max_Value(1,n) = Maximum {coin[1] + Minimum{Max_Value(3,n),
Max_Value(2,n-1)} , coin[n] +
Minimum{Max_Value(2,n-1),Max_Value(1,n-2)}};
```

# Python Implementationdef Coin_in_a_line(arr, n):# Creating a table to store max value.Max_Value = [[0 for i in range(n)]for i in range(n)]# Fill the table using the above method.for k in range(n):for j in range(k, n):i = j - kx = 0if((i + 2) <= j):x = Max_Value[i + 2][j]y = 0if((i + 1) <= (j - 1)):y = Max_Value[i + 1][j - 1]z = 0if(i <= (j - 2)):z = Max_Value[i][j - 2]Max_Value[i][j] = max(arr[i] + min(x, y),arr[j] + min(y, z))return Max_Value[0][n - 1]# Sample codearr = [ 5, 16, 3, 7 ]print(Coin_in_a_line(arr, 4))

This problem can be solved most efficiently by **dynamic programming**. The main logic behind the code is explained best by the `Max_Value`

array:

The row number specifies the starting position and the column number specifies the ending position within the coin line. We must pick a coin at either end of this range. So, `Max_Value[i][j]`

would mean the range from `i`

to `j`

.

In the code, `k`

is the interval or window. The base case is when `k`

is `0`

or `i = j`

. This means that there is only one coin to choose. Hence, the diagonal of the array will be filled first:

Next, the interval is `1`

, meaning there are `2`

choices to pick from, namely `arr[i]`

or `arr[j]`

. We must pick the maximum between these two. These values are filled out in the array:

Now, the interval is `2`

or larger. There are a few possible scenarios we need to cover. At the start, we can pick either `arr[i]`

(first) or `arr[j]`

(last).

If we pick the first value, our opponent can choose either `arr[i+1]`

or `arr[j]`

.

- If they pick
`arr[i+1]`

, our next choice will be`arr[i+2]`

or`arr[j]`

. But since we built up from the base case, we already have the max value for this in`Max_Value[i+2][j]`

! We will store this in`x`

. - If they pick
`arr[j]`

, our next choice will be`arr[i+1]`

or`arr[j-1]`

. This can be found in`Max_Value[i+1][j-1]`

. We will store this in`y`

.

So, for this scenario, what we have as our choice of moves is:

```
arr[i] + min(x, y)
```

If we pick the last value, our opponent can choose either `arr[i]`

or `arr[j-1]`

.

- If they pick
`arr[i]`

, our next choice will be`arr[i+1]`

or`arr[j-1]`

. This can be found in`Max_Value[i+1][j-1]`

. Like before, we will store this in`y`

. - If they pick
`arr[j-1]`

, our next choice will be`arr[i]`

or`arr[j-2]`

. This can be found in`Max_Value[i][j-2]`

. We will store this in`z`

.

So, for this scenario, what we have as our choice of moves is:

```
arr[j] + min(y, z)
```

Lastly, we must take the maximum out of these two scenarios:

```
max(arr[i] + min(x, y), arr[j] + min(y, z))
```

This will help us find `Max_Value[0][3]`

, which is the answer!

RELATED TAGS

coin in a line

coins

Copyright Â©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses