Google Interview Question
Country: United States
Interview Type: Phone Interview
Ouch that hurt :). lets try this. ofcourse its easier said than done, but here's what I think.
1. Design a UI to display two boards. one for player other for opponent.
2. Allow user to place ship before game starts. For every placement, you are making an ajax call to updare player board object.
3. provide a button for user to start playing.
4. once user clicks the button, submit the request to servlet
5. maintain a available players and occupied players list in an object. this class could be a singleton. or you could maintain to database if you want to maintain user base.
6. If the user is first to click the button, generate a key/sessionid and assign it to user. And wait for opponent.
7. When opponent clicks button, check for available user having a key/sessionid. If not found do step 6, else assign same key/sessionid to opponent and move both players to occupied list and redirect them to same url.
8. now every click in the board, send co-ordinates to servlet by making an ajax call, Blacken the co-ordinate for both the boards. For every request made, you are going to alternate enable/disable hits for players using response from ajax call.
9. have session timeout set incase one or both users close their browser.
10. For tracking the game, you can use the code above.
At any time, available player list will have zero or one player in waiting.
I think the solution should be focused on overall design of the whole web based application. How services are distributed and how data is verified and communicated through distributed system.
package battleship;
public enum ShipType {
DESTROYER(1),
CRUISER(3),
AIRCRAFTCARIER(5);
private int size;
private ShipType(int size) {
// TODO Auto-generated constructor stub
this.size = size;
}
public int getSize() {
return size;
}
}
package battleship;
public enum Layout {
HORIZONTAL,
VERTICAL;
}
package battleship;
public abstract class Ship {
private Layout layout;
private ShipType shipType;
private Coordinates coordinates;
public Ship(Coordinates coordinates, Layout layout, ShipType shipType) {
// TODO Auto-generated constructor stub
this.coordinates = coordinates;
this.layout = layout;
this.shipType = shipType;
}
public Layout getLayout() {
return layout;
}
public ShipType getShipType() {
return shipType;
}
public Coordinates getCoordinates() {
return coordinates;
}
}
package battleship;
public class Destroyer extends Ship {
public Destroyer(Coordinates coordinates, Layout layout) {
super(coordinates, layout, ShipType.DESTROYER);
// TODO Auto-generated constructor stub
}
}
package battleship;
public class Cruiser extends Ship {
public Cruiser(Coordinates coordinates, Layout layout) {
super(coordinates, layout, ShipType.CRUISER);
// TODO Auto-generated constructor stub
}
}
package battleship;
public class AircraftCarrier extends Ship {
public AircraftCarrier(Coordinates coordinates,Layout layout) {
super(coordinates, layout, ShipType.AIRCRAFTCARIER);
// TODO Auto-generated constructor stub
}
}
package battleship;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class Board {
String playerName;
public final static int SIZE = 20;
private Set<Coordinates> coordinates = new HashSet<Coordinates>();
Map<ShipType, Integer> remaining = new HashMap<ShipType, Integer>() {{
put(ShipType.DESTROYER, 2);
put(ShipType.CRUISER, 2);
put(ShipType.AIRCRAFTCARIER, 1);
}};
public Board(String playerName) {
// TODO Auto-generated constructor stub
this.playerName = playerName;
}
public boolean layShip(Ship ship) {
Coordinates c = ship.getCoordinates();
if(c.getX() < 0 || c.getX() > SIZE) return false;
if(c.getY() < 0 || c.getY() > SIZE) return false;
if(ship.getLayout() == Layout.HORIZONTAL && c.getX() + ship.getShipType().getSize() >= SIZE) return false;
if(ship.getLayout() == Layout.VERTICAL && c.getY() + ship.getShipType().getSize() >= SIZE) return false;
Set<Coordinates> tmp = new HashSet<Coordinates>();
if(ship.getLayout() == Layout.HORIZONTAL) {
for(int x = ship.getCoordinates().getX(); x < ship.getCoordinates().getX() + ship.getShipType().getSize(); ++x) {
Coordinates tmpC = new Coordinates(x, ship.getCoordinates().getY());
tmp.add(tmpC);
if(coordinates.contains(tmpC)) return false;
}
} else {
for(int y = ship.getCoordinates().getY(); y < ship.getCoordinates().getY() + ship.getShipType().getSize(); ++y) {
Coordinates tmpC = new Coordinates(ship.getCoordinates().getX(), y);
tmp.add(tmpC);
if(coordinates.contains(tmpC)) return false;
}
}
ShipType type = ship.getShipType();
if(remaining.get(type) <= 0) return false;
remaining.put(type, remaining.get(type) - 1);
coordinates.addAll(tmp);
return true;
}
public boolean destroy(Coordinates c) {
if(!coordinates.contains(c)) return false;
coordinates.remove(c);
return true;
}
public int gameProgress() {
return coordinates.size();
}
}
package battleship;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Game {
List<Board> boards;
int turn = 0;
Layout getLayout() {
return ( new Random().nextBoolean() ? Layout.HORIZONTAL : Layout.VERTICAL);
}
void fillInBoard(Board board) {
while(board.remaining.get(ShipType.DESTROYER) > 0) {
board.layShip(new Destroyer(new Coordinates(new Random().nextInt(Board.SIZE), new Random().nextInt(Board.SIZE)), getLayout()));
}
while(board.remaining.get(ShipType.CRUISER) > 0) {
board.layShip(new Cruiser(new Coordinates(new Random().nextInt(Board.SIZE), new Random().nextInt(Board.SIZE)), getLayout()));
}
while(board.remaining.get(ShipType.AIRCRAFTCARIER) > 0) {
board.layShip(new AircraftCarrier(new Coordinates(new Random().nextInt(Board.SIZE), new Random().nextInt(Board.SIZE)), getLayout()));
}
}
public Game(String player1, String player2) {
// TODO Auto-generated constructor stub
boards = new ArrayList<Board>();
boards.add(new Board(player1));
boards.add(new Board(player2));
fillInBoard(boards.get(0));
fillInBoard(boards.get(1));
}
boolean play() {
Coordinates c = new Coordinates(new Random().nextInt(Board.SIZE), new Random().nextInt(Board.SIZE));
System.out.println(turn + " " + c.getX() + " " + c.getY());
boards.get(turn % 2).destroy(c);
boolean ret = boards.get(turn % 2).gameProgress() > 0;
turn ++;
return ret;
}
}
package battleship;
import java.util.Random;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Game game = new Game("P1", "P2");
while(game.play());
}
}
This is just to give an idea. A skeleton you can improve on. There are lot of improvements we can do here. Dynamic ship count and type selection, providing proper access modifiers and setters getters, have separate ship classes for each type if you want, provide utility for each player to enter their placement choices via console etc.
- AlgoAlgae June 16, 2014import java.util.Set; import java.util.TreeSet; enum Ship{ Large,Medium,Small; } enum Orientation{ Vertical,Horizontal; } class Coordinate implements Comparable<Coordinate>{ private int x; private int y; public Coordinate(int x,int y){ this.x = x; this.y = y; } @Override public int compareTo(Coordinate c) { // TODO Auto-generated method stub if(this.x==c.x && this.y==c.y) return 0; return 1; } } class Board{ public String playerName; private int[][] board = new int[20][20]; public boolean gameOver = false; private int s1 = 2; private int s2 = 2; private int s3 = 1; Set<Coordinate> taken = new TreeSet<Coordinate>(); int remainingShips = 5; public Board(String name){ this.playerName = name; } public void placeShip(Ship s,int x,int y,Orientation o) throws Exception{ if(remainingShips==0) throw new Exception("No more ship left"); Set<Coordinate> tmp = new TreeSet<Coordinate>(); switch(s){ case Large: if(s3==0) throw new Exception("No more large ship left"); if(o==Orientation.Horizontal){ if(x+5>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<5;i++){ Coordinate c = new Coordinate(x+i,y); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } }else{ if(y+5>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<5;i++){ Coordinate c = new Coordinate(x,y+i); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } } taken.addAll(tmp); tmp.clear(); --s3; break; case Medium : if(s2==0) throw new Exception("No more medium ship left"); if(o==Orientation.Horizontal){ if(x+3>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<3;i++){ Coordinate c = new Coordinate(x+i,y); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } }else{ if(y+3>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<5;i++){ Coordinate c = new Coordinate(x,y+i); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } } taken.addAll(tmp); tmp.clear(); --s2; break; case Small : if(s1==0) throw new Exception("No more small ship left"); if(o==Orientation.Horizontal){ if(x+3>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<3;i++){ Coordinate c = new Coordinate(x+i,y); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } }else{ if(y+3>19){ throw new Exception("cannot place ship there"); } for(int i=0;i<5;i++){ Coordinate c = new Coordinate(x,y+i); if(taken.contains(c)) throw new Exception("cannot place over another ship"); tmp.add(c); } } taken.addAll(tmp); tmp.clear(); --s1; break; } } public boolean bombard(int x,int y, String name){ Coordinate c = new Coordinate(x,y); if(this.board[x][y]==1){ System.out.println("already hit, try again"); return true; } this.board[x][y]=1; if(taken.contains(c)){ taken.remove(c); } if(taken.size()==0){ System.out.println(name+" WINNER"); this.gameOver=true; } return false; } } public class BattleShipGame { public static void main(String[] arg){ Board player1 = new Board("A"); Board player2 = new Board("B"); try { player1.placeShip(Ship.Large, 0, 0, Orientation.Horizontal); player1.placeShip(Ship.Medium, 1, 1, Orientation.Vertical); player1.placeShip(Ship.Medium, 4, 5, Orientation.Horizontal); player1.placeShip(Ship.Small, 11, 12, Orientation.Vertical); player1.placeShip(Ship.Small, 19, 7, Orientation.Horizontal); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } try { player2.placeShip(Ship.Large, 0, 0, Orientation.Horizontal); player2.placeShip(Ship.Medium, 1, 1, Orientation.Vertical); player2.placeShip(Ship.Medium, 4, 5, Orientation.Horizontal); player2.placeShip(Ship.Small, 11, 12, Orientation.Vertical); player2.placeShip(Ship.Small, 19, 7, Orientation.Horizontal); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } int turn = 0; while(!player1.gameOver && !player2.gameOver){ if(turn==0){ while(player2.bombard(5, 5, player1.playerName)){} }else{ while(player1.bombard(5, 5, player2.playerName)){} } turn = (turn+1)%2; } } }