## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
32
of 32 vote

This is a recursive version, alternatively it can be done using DP.

``````function max_coin( int *coin, int start, int end ):
if start > end:
return 0

int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )
int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )

return max(a,b)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

yeah, dp classical problem. in O(n^2)

Comment hidden because of low score. Click to expand.
0

Check the recurrence within the solution. Formulate it within a 2-D DP structure.

Comment hidden because of low score. Click to expand.
0

Can you explain the logic ?

Comment hidden because of low score. Click to expand.
6

For player A : he can pick up coin in first place or last place, for each of these case player B can further pick from first or last place from remaining coins. But for A to win/maximize coins, coins collected by B should be minimum while that of A should be maximized.

If A selects coin[i], then B can choose coin[i+1] or coin[array_size]

If A selects coin[array_last], then B can choose coin[i] or coin[array_last-1]

We will simulate such that every function call will start from A's turn. This will give us the given recursive function.

Comment hidden because of low score. Click to expand.
3

Add DP to it by using map (or you can use 2-D array too)

``````map<pair<int, int>, int, PairCmp> DP_map;
typedef pair<int, int> Key;
// Before that, you need to implement a comparison operator for pair<int, int>, say
struct PairCmp {
bool operator() (const Key& p1, const Key& p2) const {
if (p1.first < p2.first)
return true;
else if (p1.first = p2.first)
return p1.second < p2.second;
else
return false;
}

int max_coin( int *coin, int start, int end ):
if start > end:
return 0
if (DP_map.find(Key(start, end)) != DP_map.end())
return DP_map[Key(start, end)];

int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )
int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )

int ret = max(a, b);
DP_map[Key(start, end)] = ret;
return ret;
}``````

Comment hidden because of low score. Click to expand.
0

this solution does not scale. what happens if n is too large? recursion is practically impossible.

this problem is similar to the problem of finding 'perfect' chess strategy. Only that it is a reduced version. At each turn you only have to consider 2 choices, where as in chess it is many.

when n is large, the best you can do is some kind of 'look-ahead' algorithm to make sure by kth move you are not in a worse off position.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

The reason for the min function being used is that the opponent B is also going to want to maximize B's winning when picking the gold pot, essentially leaving A with
the minimum of the two options to choose from in the next round.

Comment hidden because of low score. Click to expand.
0

If we store profit values in 2-d DP array, it's much simpler.
Profit[i][j] = max(pots[i] - Profit[i+1][j] , pots[j] - Profit[i][j-1])

Comment hidden because of low score. Click to expand.
4
of 4 vote

Quick question: most (if not all) of the answers above follow this guideline: "for each move I make, calculate the minimum possible profit of the opponent, and select the move that yields the greatest profit", i.e.:

``F(a,b) = max(min(F(a+2, b), F(a+1, b-1)), min(F(a, b-2), F(a+1,b-1)))``

But shouldn't it be the other way around? "for each possible move I make, calculate the *maximum* possible profit of the opponent, and choose the move that yields minimum losses"? i.e.:

``F(a,b) = min(max(F(a+2, b), F(a+1, b-1)), max(F(a, b-2), F(a+1, b-1)))``

??

Comment hidden because of low score. Click to expand.
3

the thing is, you calculate the max profit of the opponent. suppose you take it from the front, your opponent can choose from F(a+2, b), F(a+1, b-1) , and since the opponent plays optimally, he/she would choose max(F(a+2, b), F(a+1, b-1)), which left you min(F(a+2, b), F(a+1, b-1));

same logic, if you choose from the end, your opponent can choose from F(a, b-2), F(a+1,b-1), and he/she would choose max(F(a, b-2), F(a+1,b-1)), which left you min(F(a, b-2), F(a+1,b-1))

so you actually need the max left-over so you max whatever your opponent left to you, which is the first formula above.

Comment hidden because of low score. Click to expand.
2
of 12 vote

1 2 3 4 5 6 ... 2*n

Player A can choose the pots in such a way that he has X = 1st + 3rd + + (2n-1)th pots' gold and the player B has Y = 2nd + 4th + ... + (2n)th or vice versa. Since player A can choose whether to end up with X or Y, player A always wins.

In case the number of pots is odd, player B can follow the same strategy right after player A makes first move, so the result depends on the exact amount of gold in the pots, so no 100% winning strategy in this case.

Comment hidden because of low score. Click to expand.
0

This is right, but the question asks for _the_ optimal winning solution (i.e. which maximizes the sum assuming best play from both sides). What you have here is _a_ winning position.

Very nice proof though...

Comment hidden because of low score. Click to expand.
3

It may not be the case as the pot can be picked from either end of the line. So 1st , 2nd , 3rd pot is possible as well.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It seems the question ask for __a__ winning strategy for player A, and not for __the__ winning position for player A, actually it may happen that player A has no way to win the game if player B plays optimally.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Mihail: If the question was asking for _a_ winning strategy, why even talk about maximizing and optimal solutions?

If it was as you say, this will become a purely mathematical problem, and an AHA question, not suitable for a tech-interview.

On the other hand, trying to maximize/finding optimal will be a good algorithmic problem.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This answer does not deserve a downvote.

Comment hidden because of low score. Click to expand.
0

this is nice Mihail!

When n is even, it is true who ever moves first can choose the odd-pot series or the even-pot series, so whoever moves first wins.

When n is odd, whoever first is guaranteed to lose unless the first pot can be big enough to offset the difference between odd-pot series and even-pot series!

Comment hidden because of low score. Click to expand.
0

hugh.hn, if the post is a strategy, it's not a winning one. Consider a four-pot game with the following pots:

6, 3, 1, 4

The first player can indeed choose to receive the first and third pots, but it results in a tie. The player can win, however, by choosing to receive the first and second pots.

Comment hidden because of low score. Click to expand.
2
of 2 vote

Obviously, this is reqursion/dynamic problem. So we need formula.

Let's say, that F(i, j) - is max possible coins that 'first' player can collect on board with packets from i to j. And by 'first' player I mean player whos turn now.
F(0, n-1) - will be the answer.

Ok, now for F(i, j), first player can take v[i] or v[j].

``````x = v[i] + (Sum[i+1, j  ] - F(i+1,   j  ) );
y = v[j] + (Sum[  i , j-1] - F(  i,    j-1) );``````

And he will collent x or y coints. Of course he will choose the maximum option:

``F(i, j) = MAX(x, y);``

Why (Sum[i+1, j ] - F(i+1, j ) )? Thats simply. After the first player took the coins, the turn passes to the second. And he also wnat to win. And now he is the first player but on the board (i+1, j) or (i, j-1). The Sum is fixed, so all that he will not take - is our coins.
_________________________________________________
But do we really need to calculate Sum? No!
Lets go deeper! in recursion : ) I skip here computing. In two words:
If we 'open' F(i+1, j ) and F( i, j-1) - sum will be reduced and using that

``-Max[-a, -b] == Min[a, b]``

and we will get:

``````a = F(i+2, j); b = F(i+1, j-1); c = F(i, j-2);
x = v[i] + MIN(a, b); y = v[j] + MIN(b, c);
F(i, j)  = MAX(x,  y);``````

On each iteration size of board will be reduced on 2.
_________________________________________________
To avoid re-computation, we need to store all done computation:

``ArrayInfo optimal_subset_sum;  //optimal_subset_sum( i, j ) = F(i, j)``

ArrayInfo can be simply int[n][n]. if you don't care about the amount of memory used.
But we'll get to that later.

First, we need to initialize the smallest boards answers. There are two different situation.
If N is odd, then F(i, j) = F(i, i) = v[i]

``````for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = data[i];``````

If N is even, then F(i, j) = F(i, i+1) = MAX(v[i], v[i+1])

``````for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = MAX(data[i], data[i+1]);``````

And now, we increasing the size of the board for 2 and calculate answers for all possible boards:

``````for(int k = smallest_lenght + 2; k<=n; k+=2)
for(int i=0, j=k-1; j<n; ++i, ++j)
{
int a = optimal_subset_sum( i+2,   j   );
int b = optimal_subset_sum( i+1, j-1 );
int c = optimal_subset_sum(   i,    j-2 );
int x = data[i] + MIN(a, b); int y = data[j] + MIN(b, c);
optimal_subset_sum(i, j) = MAX(x, y);
}``````

_________________________________________________
Returning to the ArrayInfo.
There is only 1 sub-board starting fron i=n-1. (n-1, n-1)
There are only 2 sub-board starting fron i=n-2. (n-2, n-2) and (n-2, n-1)
...
Additionaly, we have only odd or only even lenght sub-boards, because we reduce it on 2 each time.
So we don't need N*N space. We can impliment ArrayInfo such way:

``````class ArrayInfo
{
public:
ArrayInfo(size_t n)
{
data = new int*[n]();
for(int i=0; i<n; ++i)
{
data[i] = new int[(n-1-i)/2+1]();
for(int j=i; j<n; ++j)
data[i][j] = -1;
}
}
int& operator() (int i, int j)
{
return data[i][(j-i)/2];
}
private:
int** data;
};``````

And it will used

``Sum[(N-i-1)/2 + 1, { i, 0, N-1 } ] = N*(3+N)/4 = n^2/4 + 3*n/4``

that's in 4 time less.

working code: http://ideone.com/ZzbMRt

Comment hidden because of low score. Click to expand.
1
of 1 vote

F(i, j) = Max { pot[i] + Min { F(i+2, j), F(i+1, j-1) }, pot[j] + Min { F(i, j-2), F(i+1, j-1) } }

Comment hidden because of low score. Click to expand.
1
of 5 vote

This is a wrong question: 1, 3, 1. A cannot win. B wins.

Comment hidden because of low score. Click to expand.
1
of 1 vote

A C++ solution

The strategy here is to consider the best displacement in favor of yourself. In other words, consider the profit of the left two choices and the right two choices, which we will call a distance. We choose a side by grabbing the side with the smallest distance.

As for the code, it is done using sliding incides that slowly come together. Note the corner cases and edge cases.

``````int goldGame(const std::vector<int>& pots)
{
// Corner case - No pots of gold
if (pots.size() == 0) return 0;

// Prepare indices
int left = 0;
int right = pots.size() - 1;

// Gold accumulated
int gold = 0;

// Loop until done grabbing gold
while (left != right)
{
// Player A goes
gold += grab(left, right, pots);

// Player B goes (toss the value)
grab(left, right, pots);
}

// Edge case - We had an even number of pots therefore player A
//             gets the last pot
if (pots.size() % 2 != 0)
gold += grab(left, right, pots);

return gold;
}

int grab(int& left, int& right, const std::vector<int>& pots)
{
// Edge case - One pot left to choose from
if (left == right) return pots[left];

// Calculate distance on left side and right side
int leftDist  = pots[left  + 1] - pots[left];
int rightDist = pots[right - 1] - pots[right];

// Choose the lower distance to grab
if (leftDist < rightDist) return pots[left++];
return pots[right--];
}``````

Comment hidden because of low score. Click to expand.
0

This solution verbage is correct at four or more items.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int gold_pots(int *arr, int n)
{
int i;
int **A = (int **)malloc(sizeof(int *) * n);
int **B = (int **)malloc(sizeof(int *) * n);
for (i = 0; i < n; ++n) {
A[i] = (int *)malloc(sizeof(int) * (n + 1));
B[i] = (int *)malloc(sizeof(int) * (n + 1));
memset(A[i], 0, sizeof(int) * (n + 1));
memset(B[i], 0, sizeof(int) * (n + 1));
A[i][1] = arr[i];
}

for (int length = 2; length <= n; ++length) {
for (i = 0; i <= n - length; ++i) {
// arr[i] ... a[i + lenght - 1]
if (arr[i] + B[i+1][length - 1]  > arr[i + length - 1] + B[i][length -1]) {
A[i][length] = arr[i] + B[i+1][length - 1];
B[i][length] = A[i+1][length - 1];
} else {
A[i][length] = arr[i + length - 1] + B[i][length -1];
B[i][length] = A[i][length -1];
}
}
}

int best_first_player = A[0][n];
int best_sond_player = B[0][n];

for (i = 0; i < n; ++i) {
free(A[i]);
free(B[i]);
}
free(A);
free(B);
return best_first_player;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Here is a java program that solves this question and has a simulation of the moves (prints out players moves and coin sums along with remaining gold pots)

The main answer to this question is in the maxCoins function at the bottom. It's a little bit cluttered because I'm returning a MaxCoinResults object instead of just an int (has additional info stored in it such as the choice that was made (start or end).

I'm doing a recursive function and caching results (so DP). Similar to a lot of other suggested answers:

``````import java.util.HashMap;

public class GoldPot {

private static int numSimulationsToRun = 3;
private static int numGoldPots = 10;
private static int maxCoinsPerPot = 10;
private static enum Choice{First,End,NA};
private static enum Player{A,B};
private static Player currentTurn;

public static void main(String[] args) {
runSimulations();
}

private static void runSimulations(){
for(int i=0; i<numSimulationsToRun; i++){
System.out.println("SIMULATION -- " + i + " --\n---------------------------");
int[] goldPots = getRandomGoldPots();
int start,end;
start =0;
end = goldPots.length-1;
currentTurn = Player.A;
MaxCoinResult maxCoinResult = maxCoins(goldPots,start,end, new HashMap<String,MaxCoinResult>());
System.out.println("Initial Coins:" + printGoldPots(goldPots,start,end));
System.out.println("Expected A Winnings:" + maxCoinResult.coinMaxSum);

//Simulate each turn and print results
String playerName;
String choiceStr;
int playerASum = 0;
int playerBSum = 0;
do{
playerName = currentTurn == Player.A ? "Player A" : "Player B";
choiceStr = maxCoinResult.choice == Choice.First ? "first" : "last";
if(currentTurn == Player.A){
playerASum += maxCoinResult.immediateCoinValue;
}
else{
playerBSum += maxCoinResult.immediateCoinValue;
}
System.out.println(playerName + " chooses the " + choiceStr + " coin with a value of:" + maxCoinResult.immediateCoinValue);
int currentPlayerSum = (currentTurn == Player.A) ? playerASum : playerBSum;
System.out.println(playerName + " now has a sum of " +  currentPlayerSum);
//update pointers according to coin chosen
if(maxCoinResult.choice == Choice.First){
start++;
}
else{
end--;
}
currentTurn = currentTurn == Player.A ? Player.B : Player.A; //Switch turns
System.out.println("RemainingCoins:" + printGoldPots(goldPots,start,end));
//Get new results
maxCoinResult = maxCoins(goldPots,start,end, maxCoinResult.cachedResults);
}while(start <= end);
System.out.println("Final Results \n-------------");
System.out.println("Player A:" + playerASum);
System.out.println("Player B:" + playerBSum);
System.out.println("END GAME.\n\n");
}
}

public static String printGoldPots(int[] arr, int start, int end){
StringBuilder sb = new StringBuilder();
if(start > end) return "";
sb.append(arr[start]);
for(int i=start+1; i<=end; i++){
sb.append("," + arr[i]);
}
return sb.toString();
}

private static int[] getRandomGoldPots(){
int[] goldPots = new int[numGoldPots];
for(int i=0; i<numGoldPots; i++){
goldPots[i]= (int) Math.ceil(Math.random()*maxCoinsPerPot);
}
return goldPots;
}

//Simple class for result - holds choice made, max value, and initial value of choice
//Also storing cached results so that I can pass it back into maxCoins when running simulations
private static class MaxCoinResult{
int immediateCoinValue;
int coinMaxSum;
Choice choice = null;
HashMap<String,MaxCoinResult> cachedResults;
MaxCoinResult(int coinMaxSum,Choice choice,int immediateCoinValue,
HashMap<String,MaxCoinResult> cachedResults){
this.coinMaxSum = coinMaxSum;
this.immediateCoinValue = immediateCoinValue;
this.choice = choice;
this.cachedResults = cachedResults;
}
}

private static MaxCoinResult maxCoins(int[] coins, int start,int end, HashMap<String,MaxCoinResult> cachedResults){
//Base Case - 0 coins remaining
if(start > end){
MaxCoinResult result = new MaxCoinResult(0,Choice.NA,0, cachedResults);
return result;
}

String cacheKey = start + ":" + end;
//If result for start/end pair has already been cached, just return it
if(cachedResults.containsKey(cacheKey)){
return cachedResults.get(cacheKey);
}

//  3 Possibilities of remaining coins after both players move
//  Recursively find max of possible remainders
//1). Both Players Choose Front
//2). 1 Player Chooses Front and 1 Player Chooses End
//3). Both Players choose End
int maxCoins2F = maxCoins(coins,start+2,end,cachedResults).coinMaxSum;
int maxCoins1F1E = maxCoins(coins,start+1,end-1,cachedResults).coinMaxSum;
int maxCoins2E = maxCoins(coins,start,end-2,cachedResults).coinMaxSum;

// 4 Possible outcomes, assuming we haven't limited them yet by the fact that B is going to make
// The optimal move on next turn
int AMaxSumAFBF = coins[start] + maxCoins2F;   //A & B Choose Front
int AMaxSumAFBE = coins[start] + maxCoins1F1E; //A Chooses Front, B Chooses End
int AMaxSumAEBF = coins[end]   + maxCoins1F1E; //A Chooses End, B Chooses Front
int AMaxSumAEBE = coins[end]   + maxCoins2E;   //A & B Choose End

// Get the max results of whether A takes First or End, now taking into account the knowledge that
// B will counter with the best move to minimize A's winnings
int AMaxSumAF = Math.min(AMaxSumAFBF, AMaxSumAFBE);
int AMaxSumAE = Math.min(AMaxSumAEBF, AMaxSumAEBE);

//Make a choice based on whether First Or end Sum is greater
Choice choice = AMaxSumAF > AMaxSumAE ? Choice.First : Choice.End;
int immediateCoinValue = (choice == Choice.First) ? coins[start] : coins[end];
int maxSum = (choice == Choice.First) ? AMaxSumAF : AMaxSumAE;
MaxCoinResult result = new MaxCoinResult(maxSum, choice,immediateCoinValue,cachedResults);

//Cache result
cachedResults.put(cacheKey, result);

//Finally return the result of A's best move
return result;
}

}``````

Here is some sample output:
SIMULATION -- 2 --
---------------------------
Initial Coins:5,5,10,5,9,9,3,9,5,1
Expected A Winnings:33
Player A chooses the first coin with a value of:5
Player A now has a sum of 5
RemainingCoins:5,10,5,9,9,3,9,5,1
Player B chooses the last coin with a value of:1
Player B now has a sum of 1
RemainingCoins:5,10,5,9,9,3,9,5
Player A chooses the first coin with a value of:5
Player A now has a sum of 10
RemainingCoins:10,5,9,9,3,9,5
Player B chooses the first coin with a value of:10
Player B now has a sum of 11
RemainingCoins:5,9,9,3,9,5
Player A chooses the first coin with a value of:5
Player A now has a sum of 15
RemainingCoins:9,9,3,9,5
Player B chooses the last coin with a value of:5
Player B now has a sum of 16
RemainingCoins:9,9,3,9
Player A chooses the last coin with a value of:9
Player A now has a sum of 24
RemainingCoins:9,9,3
Player B chooses the last coin with a value of:3
Player B now has a sum of 19
RemainingCoins:9,9
Player A chooses the last coin with a value of:9
Player A now has a sum of 33
RemainingCoins:9
Player B chooses the last coin with a value of:9
Player B now has a sum of 28
RemainingCoins:
Final Results
-------------
Player A:33
Player B:28
END GAME.

Comment hidden because of low score. Click to expand.
0

Maybe 32 / 29 ?

``````var pots = [5,5,10,5,9,9,3,9,5,1];
var playerA,
playerB = 0;

playerA = Math.max(calcLeft(pots), calcRight(pots));

function calc(pots) {
var left = [...pots];
var right = [...pots];

left.shift();
right.pop();

return Math.min(
Math.max(calcLeft(left), calcRight(left)),
Math.max(calcLeft(right), calcRight(right)),
);
}

function calcLeft(pots) {
if (!pots.length) {
return 0;
}

var coins = pots.shift();

return coins + calc(pots);
}

function calcRight(pots) {
if (!pots.length) {
return 0;
}

var coins = pots.pop();

return coins + calc(pots);
}``````

Comment hidden because of low score. Click to expand.
0

``````var pots = [5,5,10,5,9,9,3,9,5,1];
var playerA,
playerB = 0;

playerA = Math.max(calcLeft(pots), calcRight(pots));

function calc(pots) {
var left = [...pots];
var right = [...pots];

left.shift();
right.pop();

return Math.min(
Math.max(calcLeft(left), calcRight(left)),
Math.max(calcLeft(right), calcRight(right)),
);
}

function calcLeft(pots) {
if (!pots.length) {
return 0;
}

var coins = pots.shift();

return coins + calc(pots);
}

function calcRight(pots) {
if (!pots.length) {
return 0;
}

var coins = pots.pop();

return coins + calc(pots);
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Many people A always win, this is not the case. It depends on the randomness of the gold distribution, we can only maximize.
Here is a test run with 100 pots each time, and run 10000 times.
B consistently wins around 35% of the time, I did 10 different runs, so that's 100,000 times.

The actual % depends many variables, including, number of integers, and the random range of each integer.

Here is a prove: 1 3 1, A loses no matter what.

Here is the full code you can run it yourself, have fun.

``````static int count = 0;

public static void main(String[] args)
{
for (int j = 0; j < 10000; j++)
{

List<Integer> a = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0; i < 100; i++)
{
int temp = r.nextInt(5) + 1;
System.out.print(temp);
}
System.out.println();
}
System.out.println("b wins " + count / 10000d * 100 + "%");
}

public static void game(LinkedList<Integer> ll, int a, int b)
{
if (ll == null)
return;

if (ll.size() == 0)
printResult(a, b);

else if (ll.size() == 1)
printResult(a + ll.poll(), b);

else if (ll.size() == 2)
{
int tail = ll.poll();
printResult(a + head, b + tail);
else
printResult(a + tail, b + head);
} else
{
a = optimalPick(ll, a);
b = optimalPick(ll, b);
game(ll, a, b);
}
}

public static int optimalPick(LinkedList<Integer> ll, int playerGold)
{
int gain1 = ll.peekFirst() - (Math.max(ll.peekLast(), ll.get(1)));
int gain2 = ll.peekLast() - (Math.max(ll.peekFirst(), ll.get(ll.size() - 2)));

if (gain1 > gain2)
return playerGold + ll.pollFirst();
else
return playerGold + ll.pollLast();
}

public static void printResult(int a, int b)
{

System.out.println("A has " + a);
System.out.println("B has " + b);
if(b > a)
count++;
}``````

Comment hidden because of low score. Click to expand.
0

Your optimalPick function is not actually always optimal.
For example consider:
5,7,20,24,6,3
According to your optimal pick function
5 - max (7, 3) = -2
3 - max (6, 5) = -3

So A would choose the pot with 5 coins.
Then according to your algorithm, B would choose 3 next. Because:
(7 - 20 )= -13 < (3 - 6) = -3
But if you think for a second it would be a better move for B to choose the pot with 7 coins (because if A chooses the pot with 20 coins on B's next turn, then B can then take the pot with 24 coins).

So if A chose 5 at the beginning, and B chose 7, depending on what A did on their next turn this game would end up:
A = 5 + 3 + 24 = 32 OR 5 + 20 + 6 = 31
B = 7 + 20 + 6 = 33 OR 7 + 24 + 3 = 34

As you can see B won in both instances.

It actually would have been optimal for A to choose the pot with 3 coins in the beginning. With both players playing optimally the results would have been:
A = 3 + 24 + 7 = 34
B = 6 + 5 + 20 = 31

This is an example of why you need to recurse deeper to get the optimal solution rather than just peak at the next move.

You are right however, that with an odd number of pots B has a chance of winning depending on how the coins are set up.

But if there are an even # of coins I believe A has an optimal strategy that will help him/her to win or tie every time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried the code for min max rule above but did not get a correct answer. Please let me know what's wrong

``````package careercup.com;

public class PotOfGold {
public static void main(String args[]) {
int[] coinPots = {4,10,29,12,26,7,21};
int start =0;
int end = coinPots.length -1;
int aCoin =0;
int bCoin =0;
int bestIndex;

while(end >= start) {

bestIndex = findBestCoinPot(coinPots, start,end);
aCoin = aCoin+ coinPots[bestIndex];
if(bestIndex == start){
start = start+1;
System.out.println("start aCoin" + aCoin + "Best "+coinPots[bestIndex]);
} else {
end = end-1;
System.out.println("end aCoin" + aCoin+ "Best "+coinPots[bestIndex]);
}
if(end >= start) {
bestIndex = findBestCoinPot(coinPots, start,end);
bCoin = bCoin+ coinPots[bestIndex];
if(bestIndex == start){
start = start+1;
System.out.println("start bCoin" + bCoin+ "Best "+coinPots[bestIndex]);
} else {
end = end-1;
System.out.println("End bCoin" + bCoin+ "Best "+coinPots[bestIndex]);
}}
}

System.out.println(" aCoin Final " + aCoin);
System.out.println(" bCoin Final " + bCoin);
}

private static int findBestCoinPot(int[] coinPots, int start, int end) {
// TODO Auto-generated method stub
int chooseCoina;
int chooseCoinb;

chooseCoina = coinPots[start] + Math.min(Math.max(coinPots[start+2],coinPots[end]),Math.max(coinPots[start+1],coinPots[end-1]));
chooseCoinb = coinPots[end] +  Math.min(Math.max(coinPots[start+1],coinPots[end-1]),Math.max(coinPots[start],coinPots[end-2]));

if(chooseCoina > chooseCoinb) {
return start;
} else {
return end;
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this problem listed on any of the online judges? I need to code this up and test it thoroughly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

By using Profit values in 2-D DP array, it's much simpler.
Profit[i][j] = max(pots[i] - Profit[i+1][j] , pots[j] - Profit[i][j-1])

We can also find A's sum by,
A's sum + B's sum = total coins
A's sum - B's sum = A's Profit(Profit[0][n-1])

Comment hidden because of low score. Click to expand.
0
of 0 vote

After hours of head scratching was still not able to understand the min logic that is used in the most accepted answer. But came up with my own in Python that is quite straightforward to understand.

``````#!/usr/bin/env python

def my_func(my_list, start, end):
if start > end:
return 0

value = DP_state.get((start, end), False)
if value:
return value

a = my_list[start]
b = my_list[end]

# - For the 'a' case
if my_list[start + 1] < my_list[end]:
res_a = a + my_func(my_list, start + 1, end - 1)
else:
res_a = a + my_func(my_list, start + 2, end)

# - For the 'b' case
if my_list[start] < my_list[end-1]:
res_b = b + my_func(my_list, start, end - 2)
else:
res_b = b + my_func(my_list, start + 1, end - 1)

if res_a > res_b:
DP_state[(start, end)] = res_a
return res_a
else:
DP_state[(start, end)] = res_b
return res_b

DP_state = dict()
print my_func([5, 3, 7, 10, 6, 9], 0, 5)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm taking AI right now and we just covered minimax, which seems perfect for this scenario.The algorithm assumes your opponent is playing optimally in a zero sum game. Even better if you use with alpha beta pruning and likely a depth limit to reduce the number of paths you have to explore.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int[] i = { 5, 25, 4, 8, 32, 6 };
System.out.println(startGame('a', i, 0, i.length - 1, new ArrayList<>()));``````

``````private static List<Integer> startGame(char startWith, int[] coins, int start, int end, List coinsCollectedByA) {

if (start >= end) {
if (startWith == 'a') {
}
return coinsCollectedByA;
}

int coinCollected = ((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end])) ? coins[start]
: coins[end];

if (((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end]))) {
start++;
} else {
end--;
}

if (startWith == 'a') {
startWith = 'b';
} else {
startWith = 'a';
}

return startGame(startWith, coins, start, end, coinsCollectedByA);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

java code using DP, also gives the moves

``````public class PotOfGold {
static int[] arr;
static int playerInd = 0;
public static void main(String args[]){
arr = new int[]{3, 4, 5, 7, 12, 13, 6, 1};
int len = arr.length;
Strategy strategy = maxGold(0, len-1);
System.out.println(strategy.sum);
System.out.println(strategy.moves);
}
static Map<String, Strategy> map = new HashMap();
private static Strategy maxGold(int start, int end) {
//System.out.println(start+" "+end);
Strategy strategy;
if(start > end){
strategy = new Strategy();
strategy.sum = 0;
strategy.moves = "";
return strategy;
}
String key = start+"-"+end;
if(map.containsKey(key)){
return map.get(key);
}
Strategy strategy1 = new Strategy(min(maxGold(start+2, end), maxGold(start+1, end-1)), arr[start]);
Strategy strategy2 = new Strategy(min(maxGold(start+1, end-1), maxGold(start, end-2)), arr[end]);;
strategy = max(strategy1, strategy2);
map.put(key, strategy);
return strategy;
}

public static Strategy min(Strategy strategy1, Strategy strategy2){
if(strategy1.compareTo(strategy2) < 0){
return strategy1;
}
return strategy2;
}

public static Strategy max(Strategy strategy1, Strategy strategy2){
if(strategy1.compareTo(strategy2) >= 0){
return strategy1;
}
return strategy2;
}
}
class Strategy implements Comparable{
int sum;
String moves;

Strategy(){

}

Strategy(Strategy strategy1, int val){
sum = val+strategy1.sum;
moves = val+" "+strategy1.moves;
}

@Override
public int compareTo(Object o) {
Strategy strategy1 = (Strategy)o;
return this.sum - strategy1.sum;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is one more way of formulating the dp.

``````int coin[n];
int fun(int i, int j){
if(i>j) return 0;
if(i==j)
return coin[i];
return max(-fun(i+1, j)+coin[i], -fun(i, j-1)+coin[j]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there no better solution than O(2^n)???

Comment hidden because of low score. Click to expand.
0
of 0 vote

I might be over simplifying but I used a deque and just popped the end that had the highest value.

[1,9,3,4,2,5,6,2]

def solution():
a=[]
b=[]
lst = input('Enter here --> ')
d = deque()
d.extend(lst)
while len(d)>0:
if len(d)>0:
if d[0]>d[len(d)-1]:
a.append(d.popleft())
else:
a.append(d.pop())
if len(d)>0:
if d[0]>d[len(d)-1]:
b.append(d.popleft())
else:
b.append(d.pop())
print 'Player A ', sum(a), ' ', a
print 'Player B ', sum(b), ' ', b

solution()

I got the same results as other people.

Comment hidden because of low score. Click to expand.
0
of 0 vote

here i write a code which prints first number is number of gold coins collect by A and second one is for B when A plays optimally

``````#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define mod 1000000007
#define pii pair<int,int>

vector<vector<pii>> dp(1001,vector<pii>(1001,pii{0,0}));
int A[1001];

void solve(int l,int r) {
if(l>r)
return ;
if(dp[l][r].first!=0||dp[l][r].second!=0)
return ;
solve(l+1,r);solve(l,r-1);
pii a=dp[l+1][r];
pii b=dp[l][r-1];
if(a.second+A[l]>=b.second+A[r]) {
dp[l][r]={a.second+A[l],a.first};
}
else {
dp[l][r]={b.second+A[r],b.first};
}
return ;
}
int32_t main() {
int N; cin>>N;
for(int i=1;i<=N;i++) {
cin>>A[i];
}
solve(1,N);
cout<<dp[1][N].first<<" "<<dp[1][N].second;
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

``````#include <iostream>

using namespace std;

int min(int i, int j)
{
return (i<j)?i:j;
}

int max(int i, int j)
{
return (i>j)?i:j;
}

int find_max_coins(int pots[], int start, int end)
{
if(start > end)
return 0;
else
return max(
(pots[start] + min(find_max_coins(pots, start+1, end-1), find_max_coins(pots, start+2, end) ) ),
(pots[end]   + min(find_max_coins(pots, start+1, end-1), find_max_coins(pots, start, end-2) ) )
);
}

int main()
{
int pots[] = {1,2,3,4,5};
cout << find_max_coins(pots, 0, 4) << endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````int maxCoins(vector<int> coins , int start , int end ,int sum[] ,map<pair<int,int>,int>& visit )
{
if(start > end)
return 0;
if(start == end)
return coins[start];
if(end == start +1)
return max(coins[start],coins[end]);

if(visit.get(make_pair(start,end))!=visit.end())
return visit.get(make_pair(start,end));

int pickFirst = maxCoins(coins,start+1,end);
int pickSecond = maxCoins(coins , start , end -1);

int sumCoins =  sum[end+1] - sum[start+1] ;

int value = sumCoins - min(pickFirst,pickSecond);
visit.insert(make_pair(make_pair(start,end),value));
return value;

}``````

Comment hidden because of low score. Click to expand.
-1

IMO in such games it is a norm to assume that number of moves made by both players is the same and no one is at advantage by having extra moves. The fact that you have odd number of pots violates this essential condition. My small thought. Any comments?

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Not necessary that A Win... Consider the below example.....
in any case A will lose...

Ex 1: 26, 70 ,11
Ex 2: 26,25,78,12,17

BR,
Asheesh Goyal

Comment hidden because of low score. Click to expand.
-1

IMO in such games it is a norm to assume that number of moves made by both players is the same and no one is at advantage by having extra moves. The fact that you have odd number of pots violates this essential condition. My small thought. Any comments?

Comment hidden because of low score. Click to expand.
0

we should assume A and B both want to win. In example (26, 1, 70 ,11) there is no way an 'A' can win. For 'A' to win B has to choose (11,1) or (26,1). But given problem statement that B also wants to win, he will definitely select (1,70). There is no way 'A' can restrict 'B' from selecting '1,70'.

Comment hidden because of low score. Click to expand.
2

@sagar: In the case of (26, 1, 70, 11), A can win as follows:

1. A selects 26
2. Now B has to select either 1 or 11 from (1, 70, 11).
3. B selects either 11 or 1.
4. A selects 70.
5. B gets the other one.

So A can make a decision which forces B to not be able to choose 70. I think you probably read the question wrong.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Guys I need bit more explanation here.
As per the given question, player's don't have any benefit or restriction. I mean, how can a player A choose ?? as it is certain he must have to pick a pot and that too present in a certain position.. Is there any option for him to skip a pot if he did not wish to collect it ?? How can the decision is been generated ? without that the game is straight forward and is totally depends upon arrangement of pots rather than player

Comment hidden because of low score. Click to expand.
0

If they allowed players to "pass" on a turn, an algorithm could be written such that the game would never end.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

- If number of pots of gold is odd: There's no optimal strategy that makes A win knowing that B is playing optimally as well. (Ex: [1,3,1]);

- Else: Player A must always pick the pot which produces the larger result for the equation (Number - Immediate Neighbor).

Ex:
pots = [1,1,10,15,1,2]

A: picks pot[5] (2-1 > 1-1);
B: picks pot[0] (1-1 > 1-15);
So on...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

DP implementation in C lang. for recursive algo. stated by Cerberuz
===================================================

``````// utility function
int max(int a, int b) {
if( a > b )
return a;
else
return b;
}

// utility function
int min(int a, int b) {
if( a < b )
return a;
else
return b;
}

// DP version
int max_coin_DP (int * coin, int n) {
int L, i, j;
int maxStart, maxEnd, result;
int ** maxArr = NULL;

maxArr = (int **) calloc(1+n, sizeof(int *));
for(L=0; L<=n; ++L) {
// for L=0, maxArr[0][i]=0;
maxArr[L] = (int *) calloc(n, sizeof(int));
}

// for L=1
for(i=0; i<=(n-1); ++i) {
maxArr[1][i] = coin[i];
}

// for L=2
for(i=0; i<=(n-2); ++i) {
maxArr[2][i] = max(coin[i], coin[i+1]);
}

// for L>=3
for(L=3; L<=n; ++L) {
for(i=0; i<n; ++i) {
j=(i+L-1);

maxStart = coin[i] + min(maxArr[i+2][j], maxArr[i+1][j-1]);
maxEnd   = coin[j] + min(maxArr[i+1][j-1], maxArr[i][j-2]);

maxArr[i][j] = max(maxStart, maxEnd);
}
}

result=maxArr[n][0]; // final result
for(L=0; L<=n; ++L) {
free(maxArr[L]);
}
free(maxArr);

return(maxStart);
}

int getMaxCoins(int * coin, int n, int player) {
int start=0;
int end=(n-1);

if(player==1)
return (max_coin_DP(coin, n));

if(player==2)
return ( max(max_coin_R(coin, 1+start, end), max_coin_R(coin, start, end-1)) );

return (-1);
}``````

I hope the code is self explanatory in the meaning.

Comment hidden because of low score. Click to expand.
1
of 1 vote

max_coin_R() method is a recursive method:

``````// This is a recursive version, alternatively it can be done using DP.
int max_coin_R( int * coin, int start, int end ) {
int a, b;

if (start > end)
return 0;

a = coin[start] + min( max_coin_R(coin, start+2,end), max_coin_R(coin, start+1, end-1) );
b = coin[end] + min( max_coin_R(coin, start+1 ,end-1), max_coin_R(coin, start, end-2) );

return max(a,b);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

dp:

``````int max_coin(vector<int> pots)
{
vector<vector<int>> dp_table;
int pot_num=pots.size();
dp_table.resize(pot_num);
for(int i=0;i<pot_num;i++)
{
dp_table[i].resize(pot_num);
for(int j=0;j<i;j++)
dp_table[i][j]=0;
}
for(int k=0;k<pot_num;k++)
{
for(int i=0;i<pot_num;i++)
{
int j=i+k;
if(j>=pot_num)
continue;
double pots1,pots2;
if(i+2<pots.size() && j-1>=0)
pots1=pots[i]+min(dp_table[i+2][j],dp_table[i+1][j-1]);
else
pots1=pots[i];
if(i+1<pots.size() && j-2>=0)
pots2=pots[j]+min(dp_table[i+1][j-1],dp_table[i][j-2]);
else
pots2=pots[j];
dp_table[i][j]=max(pots1,pots2);
}
}
return dp_table[0][pot_num-1];
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python Recursive algorithm with Caching.

``````def strategy(pots):
cache = {}
def s(i, j):
# Given: pots from i to j
# Assuming rational players, return this tuple
#   only, L, R
#   how much gold in this pot
#   1st player bounty
#   2nd player bounty
#   rest of the game
if i == j:
return ('only', pots[i], pots[i], 0, None)
if (i,j) in cache:
return cache[(i,j)]
l_next = s(i+1, j)
r_next = s(i, j-1)
_, _, l1, l2, _ = l_next
_, _, r1, r2, _ = r_next
l_outcome = pots[i] + l2
r_outcome = pots[j] + r2
if l_outcome > r_outcome:
result = ('L', pots[i], l_outcome, l1, l_next)
else:
result = ('R', pots[j], r_outcome, r1, r_next)
cache[(i,j)] = result
return result
return s(0, len(pots)-1)

pots = [6, 2, 3, 4, 7]
print pots
print strategy(pots)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include <iostream>
#include <vector>

int choose(int* head, int* tail, char& choice)
{
return 0;

int middle = choose(head + 1, tail - 1, choice); // memoization
int tail_first = *tail + std::min(middle, choose(head, tail - 2, choice));

choice = head_first >= tail_first ? 'H' : 'T';
}

int main()
{
std::vector<int> v = { 10, 2, 6, 10, 4, 7, 100, 100 };

char choice;
int i = choose(&v.data()[0],
&v.data()[0] + v.size() - 1,
choice);

std::cout << choice << " gives you " << i
<< " pieces of gold" << std::endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static class PotsOfGold
{
/// <summary>
/// Computes the optimal strategy where a player can pick pots from the beginning or end of the array
/// </summary>
/// <param name="pots">Array of pots each having gold value</param>
/// <returns>Indices that should be chosen</returns>
public static Stack<int> Compute(int[] pots, out int totalValue)
{
return Compute(pots, 0, pots.Length - 1, null, out totalValue);
}

/// <summary>
/// Computes optimal strategy to pick pots, given that the other player is also playing optimally
/// </summary>
/// <param name="pots">Array of pot gold values</param>
/// <param name="startIndex">Next left pot to pick</param>
/// <param name="endIndex">Next right pot to pick</param>
/// <param name="cache">Cache - without it, the algorithm is exponential</param>
/// <param name="totalValue">The difference between next player's value and the one of his opponents</param>
/// <returns>Stack of indices to pick next</returns>
private static Stack<int> Compute(int[] pots, int startIndex, int endIndex, Dictionary<string, Tuple<int[], int>> cache, out int totalValue)
{
if (startIndex == endIndex)
{
totalValue = pots[startIndex];
return new Stack<int>(new int[] {startIndex });
}
else
{
if (cache == null)
{
cache = new Dictionary<string,Tuple<int[],int>>();
}

string cacheKey = string.Format("{0}_{1}", startIndex, endIndex);
if (cache.ContainsKey(cacheKey))
{
var cachedValue = cache[cacheKey];
totalValue = cachedValue.Item2;
return new Stack<int>(cachedValue.Item1);
}
else
{

int lPotValue = pots[startIndex];
int rPotValue = pots[endIndex];

int lCost;
int rCost;

Stack<int> lStrategy = Compute(pots, startIndex + 1, endIndex, cache, out lCost);
Stack<int> rStrategy = Compute(pots, startIndex, endIndex - 1, cache, out rCost);

// this is where we strategy is chosen
// what's better take pot from the left or from the right
if (lPotValue - lCost > rPotValue - rCost)
{
// take left
lStrategy.Push(startIndex);
totalValue = lPotValue - lCost;
cache[cacheKey] = new Tuple<int[], int>(lStrategy.ToArray(), totalValue);
return lStrategy;
}
else
{
// take right
rStrategy.Push(endIndex);
totalValue = rPotValue - rCost;
cache[cacheKey] = new Tuple<int[], int>(rStrategy.ToArray(), totalValue);
return rStrategy;
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

given {12,60,28,4} and the condition that A picks first, the algorithm mentioned in the first comment makes A lose.
but A can win if it picks 4 and then 60.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I believe that this does the trick... simple recursion using golang, could be optimized to suit various requirements...

``````package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

type Pot struct {
value  int
choice *Choice
}
type Choice struct {
scoreA, scoreB    int
leftPot, rightPot *Pot
}

func main() {
out := bufio.NewWriter(os.Stdout)
potvals, err := getPots(out)
if err != nil {
out.WriteString(fmt.Sprintln("ERROR: ", err))
out.Flush()
return
}
buildSolveAndPrintChoiceTree(potvals,out);
}

func getPots(out *bufio.Writer) ([]int, error) {
out.WriteString(fmt.Sprintln("type a space separated list of pot values and hit 'enter' key, or just hit 'enter' key to use default game"))
out.Flush()
scanner := bufio.NewScanner(os.Stdin)
if scanner.Scan() {
fmt.Println(scanner.Text()) // Println will add back the final '\n'

pots := strings.Split(scanner.Text(), " ")
// Assign cap to avoid resize on every append.
potvals := make([]int, 0, len(pots))

for _, p := range pots {
// Empty line occurs at the end of the file when we use Split.
if len(p) == 0 {
continue
}
// Atoi better suits the job when we know exactly what we're dealing
// with. Scanf is the more general option.
n, err := strconv.Atoi(p)
if err != nil {
return nil, err
}
potvals = append(potvals, n)
}
if len(potvals) > 0{
return potvals, nil
}
}
//default values for testing
potvals := make([]int, 4)
potvals[0] = 3
potvals[1] = 8
potvals[2] = 7
potvals[3] = 3
out.WriteString(fmt.Sprintln("using default testing game: ",potvals))
out.Flush()
return potvals, nil
}

func buildSolveAndPrintChoiceTree(potvals []int,out *bufio.Writer){
mychoice := buildChoiceTree(potvals)
solveChoiceTree(mychoice)
printSolvedChoiceTree(mychoice, out)
out.Flush()
}

/*recursively build a funny binary tree sort of thing from input*/
func buildChoiceTree(potvals []int) *Choice {
thelen := len(potvals)
choice := new(Choice)
choice.leftPot = new(Pot)
choice.leftPot.value = potvals[0]
if thelen > 1 {
choice.rightPot = new(Pot)
choice.rightPot.value = potvals[thelen-1]
choice.leftPot.choice = buildChoiceTree(potvals[:1])
choice.rightPot.choice = buildChoiceTree(potvals[:thelen-1])
}
return choice
}

func solveChoiceTree(tree *Choice) int {
scoreA, _ := solveChoiceTreeR(tree, true)
return scoreA
}

func solveChoiceTreeR(tree *Choice, turnA bool) (int, int) {
//terminal node
if tree.rightPot == nil {
if turnA {
tree.scoreA = tree.leftPot.value
tree.scoreB = 0
} else {
tree.scoreA = 0
tree.scoreB = tree.leftPot.value
}
} else {
//we're at a choice with two viable pots leading to new choices
scoreAL, scoreBL := solveChoiceTreeR(tree.leftPot.choice, !turnA)
scoreAR, scoreBR := solveChoiceTreeR(tree.rightPot.choice, !turnA)

if turnA {
//A's turn; trim nonoptimal choice for a
scoreAL += tree.leftPot.value
scoreAR += tree.rightPot.value
if scoreAL >= scoreAR {
//trim off right from tree
tree.rightPot = nil
tree.scoreA = scoreAL
tree.scoreB = scoreBL
} else {
tree.leftPot = nil
tree.scoreA = scoreAR
tree.scoreB = scoreBR
}
} else {
//B's turn; trim nonoptimal choice for a
scoreBL += tree.leftPot.value
scoreBR += tree.rightPot.value
if scoreBL >= scoreBR {
//trim off right from tree
tree.rightPot = nil
tree.scoreA = scoreAL
tree.scoreB = scoreBL
} else {
tree.leftPot = nil
tree.scoreA = scoreAR
tree.scoreB = scoreBR
}
}
}

return tree.scoreA, tree.scoreB
}

func printSolvedChoiceTree(tree *Choice, out *bufio.Writer) {
printSolvedChoiceTreeR(tree, out, true)
out.WriteString(fmt.Sprintln("Final score (Player A vs Player B):  (", tree.scoreA, " vs ", tree.scoreB, ")"))
}

func printSolvedChoiceTreeR(tree *Choice, out *bufio.Writer, turnA bool) {
if turnA {
if tree.leftPot != nil {
out.WriteString(fmt.Sprintln("Player A chooses the L pot: ", tree.leftPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.leftPot.choice != nil {
printSolvedChoiceTreeR(tree.leftPot.choice, out, !turnA)
}
} else {
if tree.rightPot != nil {
out.WriteString(fmt.Sprintln("Player A chooses the R pot: ", tree.rightPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.rightPot.choice != nil {
printSolvedChoiceTreeR(tree.rightPot.choice, out, !turnA)
}
}
}
} else {
if tree.leftPot != nil {
out.WriteString(fmt.Sprintln("Player B chooses the L pot: ", tree.leftPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.leftPot.choice != nil {
printSolvedChoiceTreeR(tree.leftPot.choice, out, !turnA)
}
} else {
if tree.rightPot != nil {
out.WriteString(fmt.Sprintln("Player B chooses the R pot: ", tree.rightPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.rightPot.choice != nil {
printSolvedChoiceTreeR(tree.rightPot.choice, out, !turnA)
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//Note : turn 1 -> A's turn,  turn 2 -> B's turn

int collectCoins(int turn, int coins[], int front_index, int back_index){

//if there is only one item
if(front_index == back_index){
//A turn
if(turn == 1){
return coins[front_index];
}
else
{
return 0;
}

}

//A turn
if(turn == 1){

return max(coins[front_index] + collectCoins(2, coins, front_index+1, back_index),
coins[back_index] + collectCoins(2, coins, front_index, back_index-1));

}
else
{

//B turn
//takes out the element that is biggest in either side

if(coins[front_index] >= coins[back_index]){

return collectCoins(1, coins, front_index+1, back_index);

}
else
{

return collectCoins(1, coins, front_index, back_index-1);

}

}

}

int main()
{

int coins[] = {10, 100, 1000, 15, 25, 200, 45, 70, 100};

cout << collectCoins(1, coins, 0, 8) << endl;

return 0;
}``````

Please check if this is correct. Thanks! :D

Comment hidden because of low score. Click to expand.
-1
of 1 vote

A - input array.
S(x,y) - sum of element from x to y. We can get it for O(1) with O(n) preproccesing using 2 array. Of course, with solution with Max of two Min of two F(...) is a bit faster (no need to calculate sum), but as for me - this is simple to understand.

F(x, x) := A[x]
F(x, y) := Max( A[x] + S(x+1, y) - F(x+1, y), A[y] + S(x, y-1) - F(x, y-1) )

We get first or last: A[x] or A[y]
Then see how many can get opponent in new array: F(x+1, y) or F(x, y-1)
Because of constant amount of points: S(x+1, y) - F(x+1, y) or S(x, y-1) - F(x, y-1)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

HERE ARE A SIMULATION:

``````public static void main(String [] args){

System.out.println();
int coins[] = new int[]{100,1,20,30,40,10,20,30,90};
for(int i = 0 ; i < coins.length; i++)
System.out.print(coins[i] + " , ");
System.out.println();
playGame(coins);
System.out.println("Recursive call result: : " + max_coin(coins,0,coins.length-1));

}
public static void playGame(int array[])
{
// taking the first one.
int sum = array[0];
int sumB = 0;
int i = 1;
int j = array.length-1;
String paths = "" + array[0] + " + ";
String pathsB ="";
while(i<j){

// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;
}
// Time for player A
if(i>j)break;

if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{

paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the first one:");
if(sumB>sum){
System.out.println("B WINS ");
}else{
System.out.println("A WINS " );
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " +sumB);
// Start by taking the last one
sum = array[array.length-1];
i = 0;
j = array.length-2;
paths = "" + array[array.length-1] + " + ";
while(i<j){
// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;

}
// Time for player A
if(i>j)break;

if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{

paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the Last one:");
if(sumB>sum){
System.out.println("B WINS");
}else{
System.out.println("A WINS");
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " + sumB);

}
public static int max_coin( int coin[], int start, int end ){
if (start > end)
return 0;

int a = coin[start] + Math.min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) );
int b = coin[end] + Math.min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) );

return Math.max(a,b);
}``````

mafafito@mafafito-Aspire-4752:~/programming\$ java Amazon

100 , 1 , 20 , 30 , 40 , 10 , 20 , 30 , 90 ,
Taking the first one:
A WINS
PLAYER A 100 + 30 + 10 + 30 + 1 + = 171
PLAYER B 90 + 20 + 40 + 20 + = 170
Taking the Last one:
B WINS
PLAYER A 90 + 30 + 10 + 30 + 1 + = 161
PLAYER B 90 + 20 + 40 + 20 + 100 + 20 + 40 + 20 + = 350
Recursive call result: : 171

Comment hidden because of low score. Click to expand.
0

Upvoting yourself doesn't work axeliux

Comment hidden because of low score. Click to expand.
0

why it doesnt work?

Comment hidden because of low score. Click to expand.
0

Oh. you are not taking about my code.

about the upvoting thing, of course I know it does not work. ( or at least it shouldn't work) But I wonder, how do you know that I did try anyway?

Comment hidden because of low score. Click to expand.
0

we are all in love with ourselves
that's what careercup is for
broken egos finding a playground to repair egos

Comment hidden because of low score. Click to expand.
0

you havent break my ego anyway. But lets go back to bussiness:

What do you think about my program?

What about print the wining path inside the recursive call, do you think It could be interesting?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Implemented a solution using the minimax algorithm in C++ on github: github.com/benmurrell/PotsOfGold

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import com.google.common.collect.Maps;

import java.util.Map;

public class PotsOfGold {
private static int [] pots = new int[1000];
public static void main(String[] args) {
double sqrt = Math.sqrt(pots.length);
for(int i=0;i<pots.length;i++){
pots[i]= (int)(Math.random()*sqrt);
}
long start = System.currentTimeMillis();
System.out.println(takeBrute(0, pots.length - 1));
System.out.println("brute took "+(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
System.out.println(takeAlgo());
System.out.println("algo took "+(System.currentTimeMillis()-start));
}
private static int takeAlgo() {
if (pots.length==1) return pots[0];
if (pots.length==2) return Math.max(pots[0],pots[1]);

if (pots.length%2==0){
int sumEven = sum(0, pots.length-1, 0),
sumOdd = sum(0, pots.length-1, 1);
return Math.max(sumEven, sumOdd);
}else{
int takeHead = pots[0]+Math.min(sum(1, pots.length-1, 0),sum(1, pots.length-1, 1));
int takeTail = pots[pots.length-1]+Math.min(sum(0, pots.length-2, 0),sum(0, pots.length-2, 1));
}
}
private static int sum(int headIndex,int tailIndex, int oddOrEven){
int sum = 0;
if (i%2==oddOrEven){
sum+=pots[i];
}
}
return sum;
}

private static final Map<String,Integer> cache = Maps.newHashMap();
private static int takeBrute(int headIndex, int tailIndex) {

Integer ret = cache.get(key);
if (ret!=null) return ret;

int takeHH = takeBrute(headIndex + 2, tailIndex);
int takeHT = takeBrute(headIndex + 1, tailIndex - 1);

int takeTail = pots[tailIndex] + Math.min(takeTT, takeHT);
cache.put(key, ret);
return ret;
}
}``````

Output for 1k pots :
7726
brute took 454
7711
algo took 0

N.B. The fast algo is pretty damn close and very fast but it's not accurate. Times are in milliseconds.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If you need the values as well
{{
def mc(l):
if len(l) <= 2:
return sorted(l, reverse=True)
v1 = mc(l[1:])
v2 = mc(l[:-1])
if (l[0] + sum(v1[i] for i in range(1, len(v1), 2))) > \
(l[-1] + sum(v2[i] for i in range(1, len(v2), 2))):
return [l[0]] + v1
else:
return [l[-1]] + v2

def wsa(l):
v = mc(l)
return [v[i] for i in range(len(v)) if i % 2 == 0]

print wsa([13, 25, 20, 12, 3])
}}

Comment hidden because of low score. Click to expand.
-2
of 4 vote

google search for minimax algorithm. That's the answer to this problem. Given all the information, one can say that person who plays first will ALWAYS win...

Comment hidden because of low score. Click to expand.
2

Consider the pot's structure

1 3 1

Player A ends up with 2, and player B with 3 no matter how player A performs.

Comment hidden because of low score. Click to expand.
0

I was wondering why non one mentioned minimax? Not everything HAS to be solved by DP!

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

I added some more comments to the question, however it was pretty much just that :-(

Comment hidden because of low score. Click to expand.
0

It may not be the case as the pot can be picked from either end of the line. So 1st , 2nd , 3rd pot is possible as well.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2

If the input is {1, 10, 1000, 10}, then the optimal strategy is to pick the 1. Picking the best of left and right doesn't work.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.