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') { 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); } }
Output :
Coins Collected By A: [5, 4, 32]