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)

- Cerberuz February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- zyfo2 February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Can you explain the logic ?

- Nitin Gupta February 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 votes

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.

- Cerberuz February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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;
}

- zippon.wu March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hugh.hn November 21, 2013 | Flag
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.

- mick00304 April 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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])

- riku May 05, 2015 | Flag
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)))

??

- E November 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

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.

- meow March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 12 vote

Say we start with an even number of pots

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.

- Mihail February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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...

- Anonymous February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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.

- CodeSurfer February 13, 2013 | Flag
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.

- Mihail February 13, 2013 | Flag
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.

- Anonymous February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This answer does not deserve a downvote.

- Anonymous February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- hugh.hn November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous January 28, 2014 | Flag
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

- Darida October 29, 2013 | Flag Reply
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) } }

- Chaitanya August 19, 2013 | Flag Reply
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.

- Paul December 28, 2013 | Flag Reply
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--];
}

- Josh June 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution verbage is correct at four or more items.

- Cullen Bond October 22, 2019 | Flag
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;
}

- Anonymous February 18, 2013 | Flag Reply
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.

- ksun.mc August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- Alex June 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- Alex June 16, 2019 | Flag
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;
                a.add(temp);
                System.out.print(temp);
            }
            System.out.println();
            game(new LinkedList<Integer>(a), 0, 0);
        }
        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 head = ll.poll();
            int tail = ll.poll();
            if (head >= tail)
                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++;
    }

- benny.chaucc August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ksun.mc August 14, 2014 | Flag
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;
		}
	}

}

- Himani December 21, 2014 | Flag Reply
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.

- Sankalp January 15, 2015 | Flag Reply
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])

- riku May 05, 2015 | Flag Reply
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)

- RGK June 14, 2015 | Flag Reply
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.

- Max November 02, 2015 | Flag Reply
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') {
				coinsCollectedByA.add(coins[end]);
			}
			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') {
			coinsCollectedByA.add(coinCollected);
			startWith = 'b';
		} else {
			startWith = 'a';
		}

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

- dhiralpandya March 24, 2016 | Flag Reply
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;
    }

- turukmakto1990 December 20, 2016 | Flag Reply
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]);
}

- dayalsahoo September 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ryan Burgert October 15, 2018 | Flag Reply
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.

- jkatzwhitew December 14, 2018 | Flag Reply
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;
}

- raashid12anwar October 18, 2019 | Flag Reply
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;
}

- Jack February 12, 2013 | Flag Reply
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;
   
}

- zip February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

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?

- helloworld February 13, 2013 | Flag
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

- asheesh.goyal February 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

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?

- helloworld February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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'.

- sagar August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@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.

- anotherguy September 04, 2013 | Flag
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

- hprem991 February 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- David.1138 March 15, 2014 | Flag
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...

- BigD February 13, 2013 | Flag Reply
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.

- czar February 15, 2013 | Flag Reply
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);
}

- czar February 15, 2013 | Flag
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];
}

- leehomyc February 21, 2013 | Flag Reply
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 
        # to represent your strategy:
        #   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)

- showell30@yahoo.com February 26, 2013 | Flag Reply
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)
{
	if (head > tail)
		return 0;

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

	choice = head_first >= tail_first ? 'H' : 'T';
	return std::max(head_first, tail_first);
}

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;
}

- lori May 09, 2013 | Flag Reply
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;
                    }
                }
            }
        }
    }

- alexb7 June 21, 2013 | Flag Reply
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.
clarify this for me please

- CuriousBenji August 25, 2013 | Flag Reply
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)
				}
			}
		}
	}
}

- iliketoprogram August 28, 2013 | Flag Reply
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

- sanjaygir October 08, 2013 | Flag Reply
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)

- Darida October 12, 2013 | Flag Reply
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

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Upvoting yourself doesn't work axeliux

- crossover dbm November 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why it doesnt work?

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- crossover dbm November 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 19, 2013 | Flag
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

- Ben Murrell July 17, 2014 | Flag Reply
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));
            return Math.max(takeHead, takeTail);
        }
    }
    private static int sum(int headIndex,int tailIndex, int oddOrEven){
        int sum = 0;
        for(int i=headIndex;i<=tailIndex;i++){
            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) {
        if (headIndex>tailIndex) return 0;
        if (headIndex==tailIndex) return pots[headIndex];
        if (headIndex+1==tailIndex) return Math.max(pots[headIndex],pots[tailIndex]);

        String key = headIndex+" "+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 takeTT = takeBrute(headIndex, tailIndex-2);

        int takeHead = pots[headIndex] + Math.min(takeHT, takeHH);
        int takeTail = pots[tailIndex] + Math.min(takeTT, takeHT);
        ret = Math.max(takeHead, takeTail);
        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.

- petko.ivanov September 24, 2014 | Flag Reply
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])
}}

- Anonymous November 30, 2014 | Flag Reply
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...

- simplicity February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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.

- Mihail February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Deep_Black July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 352905 February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- CodeSurfer February 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 votes

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.

- Bob February 19, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More