# Java Pots of gold game – Google Interview

Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot – perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to “maximize” the number of coins collected by A, assuming B also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

At the end I was asked to code this strategy!

```package com.omt.learn.algo;

import java.util.ArrayList;
import java.util.List;

public class PotsOfGold {

public static void main(String args[]) {
// int[] i = { 9, 2, 4, 8, 7 };
int[] i = { 5, 25, 4, 8, 32, 6 };
System.out.println("Coins Collected By A: " + 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') {