StartUp Amazon Interview Question
Software Architects Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Also, Model/Viewer/Controller is your friend for this problem:
model = matrix of (X/Y/None) values
view = code that draws the board and displays notifications (Alice Won!)
controller = code that prompts users for their next entries
The model for tic-tac-toe is dead simple. The view and controller is where this problem gets interesting, because depending on your notion of MVC, some responsibilities will be a bit blurry as to whether they go into the controller or the view.
Main Class will be as follows:
package tictactoe;
public class Main {
public void play() {
TicTacToe game = new TicTacToe();
System.out.println("Welcome! Tic Tac Toe is a two player game.");
System.out.print("Enter player one's name: ");
game.setPlayer1(game.getPrompt());
System.out.print("Enter player two's name: ");
game.setPlayer2(game.getPrompt());
boolean markerOk = false;
while (!markerOk) {
System.out.print("Select any letter as " + game.getPlayer1() + "'s marker: ");
String marker = game.getPrompt();
if (marker.length() == 1 &&
Character.isLetter(marker.toCharArray()[0])) {
markerOk = true;
game.setMarker1(marker.toCharArray()[0]);
} else {
System.out.println("Invalid marker, try again");
}
}
markerOk = false;
while (!markerOk) {
System.out.print("Select any letter as " + game.getPlayer2() + "'s marker: ");
String marker = game.getPrompt();
if (marker.length() == 1 &&
Character.isLetter(marker.toCharArray()[0])) {
markerOk = true;
game.setMarker2(marker.toCharArray()[0]);
} else {
System.out.println("Invalid marker, try again");
}
}
boolean continuePlaying = true;
while (continuePlaying) {
game.init();
System.out.println();
System.out.println(game.getRules());
System.out.println();
System.out.println(game.drawBoard());
System.out.println();
String player = null;
while (!game.winner() && game.getPlays() < 9) {
player = game.getCurrentPlayer() == 1 ? game.getPlayer1() : game.getPlayer2();
boolean validPick = false;
while (!validPick) {
System.out.print("It is " + player + "'s turn. Pick a square: ");
String square = game.getPrompt();
if (square.length() == 1 && Character.isDigit(square.toCharArray()[0])) {
int pick = 0;
try {
pick = Integer.parseInt(square);
} catch (NumberFormatException e) {
//Do nothing here, it'll evaluate as an invalid pick on the next row.
}
validPick = game.placeMarker(pick);
}
if (!validPick) {
System.out.println("Square can not be selected. Retry");
}
}
game.switchPlayers();
System.out.println();
System.out.println(game.drawBoard());
System.out.println();
}
if (game.winner()) {
System.out.println("Game Over - " + player + " WINS!!!");
} else {
System.out.println("Game Over - Draw");
}
System.out.println();
System.out.print("Play again? (Y/N): ");
String choice = game.getPrompt();
if (!choice.equalsIgnoreCase("Y")) {
continuePlaying = false;
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Main main = new Main();
main.play();
}
}
//Tic Tac toe Class
package tictactoe;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class TicTacToe {
private char[][] board = new char[3][3];
private String player1;
private String player2;
private int currentPlayer;
private char marker1;
private char marker2;
private int plays;
private BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
protected void init() {
int counter = 0;
for (int i = 0; i < 3; i++) {
for (int i1 = 0; i1 < 3; i1++) {
board[i][i1] = Character.forDigit(++counter, 10);
}
}
currentPlayer = 1;
plays = 0;
}
protected void switchPlayers() {
if (getCurrentPlayer() == 1) {
setCurrentPlayer(2);
} else {
setCurrentPlayer(1);
}
setPlays(getPlays() + 1);
}
protected boolean placeMarker(int play) {
for (int i = 0; i < 3; i++) {
for (int i1 = 0; i1 < 3; i1++) {
if (board[i][i1] == Character.forDigit(play, 10)) {
board[i][i1] = (getCurrentPlayer() == 1) ? getMarker1() : getMarker2();
return true;
}
}
}
return false;
}
protected boolean winner() {
//Checking rows
char current = ' ';
for (int i = 0; i < 3; i++) {
int i1 = 0;
for (i1 = 0; i1 < 3; i1++) {
if (!Character.isLetter(board[i][i1])) {
break;
}
if (i1 == 0) {
current = board[i][i1];
} else if (current != board[i][i1]) {
break;
}
if (i1 == 2) {
//Found winner
return true;
}
}
}
//Checking columns
for (int i = 0; i < 3; i++) {
current = ' ';
int i1 = 0;
for (i1 = 0; i1 < 3; i1++) {
if (!Character.isLetter(board[i1][i])) {
break;
}
if (i1 == 0) {
current = board[i1][i];
} else if (current != board[i1][i]) {
break;
}
if (i1 == 2) {
//Found winner
return true;
}
}
}
//Checking diagonals
current = board[0][0];
if (Character.isLetter(current) && board[1][1] == current && board[2][2] == current) {
return true;
}
current = board[2][0];
if (Character.isLetter(current) && board[1][1] == current && board[0][2] == current) {
return true;
}
return false;
}
protected String getRules() {
StringBuilder builder = new StringBuilder();
builder.append("Players take turns marking a square. Only squares \n");
builder.append("not already marked can be picked. Once a player has \n");
builder.append("marked three squares in a row, they win! If all squares \n");
builder.append("are marked and no three squares are the same, a tied game is declared.\n");
builder.append("Have Fun! \n\n");
return builder.toString();
}
protected String getPrompt() {
String prompt = "";
try {
prompt = reader.readLine();
} catch (IOException ex) {
ex.printStackTrace();
}
return prompt;
}
protected String drawBoard() {
StringBuilder builder = new StringBuilder("Game board: \n");
for (int i = 0; i < 3; i++) {
for (int i1 = 0; i1 < 3; i1++) {
builder.append("[" + board[i][i1] + "]");
}
builder.append("\n");
}
return builder.toString();
}
public int getCurrentPlayer() {
return currentPlayer;
}
public void setCurrentPlayer(int currentPlayer) {
this.currentPlayer = currentPlayer;
}
public char getMarker1() {
return marker1;
}
public void setMarker1(char marker1) {
this.marker1 = marker1;
}
public char getMarker2() {
return marker2;
}
public void setMarker2(char marker2) {
this.marker2 = marker2;
}
public int getPlays() {
return plays;
}
public void setPlays(int plays) {
this.plays = plays;
}
public String getPlayer1() {
return player1;
}
public void setPlayer1(String player1) {
this.player1 = player1;
}
public String getPlayer2() {
return player2;
}
public void setPlayer2(String player2) {
this.player2 = player2;
}
}
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
char bord[3][3]={{'1','2','3'},{'4','5','6'},{'7','8','9'}};
char win_status='\0',turn='\0';
char win_check(char);
void add_on_board(char);
void print(void);
void main()
{
printf("Welcome to Tic Toc Game\n");
printf("Rule-1: Two players, A and B.\n");
printf("Rule-2: A has 'X' and B has 'O' piece on board. \n");
printf("Initial status of board\n");
print();
char e='\0',f;
int n=1;
printf("ready to play?(y/n):");
scanf("%c",&f);
f=getchar();
while(win_status=='\0' && n<;5)
{
system("clear");
printf("For A ==> X\nFor B ==> O\n\n");
print();
if(win_status=='\0')
{
turn='A';
printf("A 's turn: press number:");
fflush(stdin);
//sleep(3);
scanf("%c",&e);
f=getchar();
//scanf("%c",&f);
add_on_board(e);
win_status=win_check('X');
print();
}
if(win_status=='\0')
{
turn='B';
printf("B 's turn: press number:");
fflush(stdin);
scanf("%c",&e);
f=getchar();
add_on_board(e);
win_status=win_check('O');
print();
}
n++;
}
switch(win_status)
{
case 'A':
printf("Winner is ---A---\nCongrates\n");
break;
case 'B':
printf("Winner is ---B---\nCongrates\n");
break;
default:
printf("Match draw!\n");
}
}
char win_check(char p)
{
char temp[3]={'\0'};
int i=0,j=0,k=0;
for(i=0;i<;3;i++)
{
for(j=0;j<;3;j++) temp[j]=bord[i][j];
for(k=0;k<;3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
}
for(i=0;i<;3;i++)
{
for(j=0;j<;3;j++) temp[j]=bord[j][i];
for(k=0;k<;3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
}
for(i=0;i<;3;i++) temp[i]=bord[i][i];
for(k=0;k<;3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
for(i=0;i<;3;i++) temp[i]=bord[i][2-i];
for(k=0;k<;3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
return '\0';
}
void add_on_board(char c)
{
int i=0,j=0;
for(i=0;i<;3;i++)
{
for(j=0;j<;3;j++)
{
if(bord[i][j]==c)
{
bord[i][j]=(turn=='A'?'X':'O');
return;
}
}
}
}
void print(void)
{
int i=0,j=0;
printf("\n");
for(i=0;i<;3;i++)
{
for(j=0;j<;3;j++)
{
printf("%-4c",bord[i][j]);
}
printf("\n");
}
}
//Tic Toc game simulation..........
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
char bord[3][3]={{'1','2','3'},{'4','5','6'},{'7','8','9'}};
char win_status='\0',turn='\0';
char win_check(char);
void add_on_board(char);
void print(void);
void main()
{
printf("Welcome to Tic Toc Game\n");
printf("Rule-1: Two players, A and B.\n");
printf("Rule-2: A has 'X' and B has 'O' piece on board. \n");
printf("Initial status of board\n");
print();
char e='\0',f;
int n=1;
printf("ready to play?(y/n):");
scanf("%c",&f);
f=getchar();
while(win_status=='\0' && n<5)
{
system("clear");
printf("For A ==> X\nFor B ==> O\n\n");
print();
if(win_status=='\0')
{
turn='A';
printf("A 's turn: press number:");
fflush(stdin);
//sleep(3);
scanf("%c",&e);
f=getchar();
//scanf("%c",&f);
add_on_board(e);
win_status=win_check('X');
print();
}
if(win_status=='\0')
{
turn='B';
printf("B 's turn: press number:");
fflush(stdin);
scanf("%c",&e);
f=getchar();
add_on_board(e);
win_status=win_check('O');
print();
}
n++;
}
switch(win_status)
{
case 'A':
printf("Winner is ---A---\nCongrates\n");
break;
case 'B':
printf("Winner is ---B---\nCongrates\n");
break;
default:
printf("Match draw!\n");
}
}
char win_check(char p)
{
char temp[3]={'\0'};
int i=0,j=0,k=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++) temp[j]=bord[i][j];
for(k=0;k<3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++) temp[j]=bord[j][i];
for(k=0;k<3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
}
for(i=0;i<3;i++) temp[i]=bord[i][i];
for(k=0;k<3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
for(i=0;i<3;i++) temp[i]=bord[i][2-i];
for(k=0;k<3;k++) if(temp[k]!=p) break;
if(k==3) return (p=='X'?'A':'B');
return '\0';
}
void add_on_board(char c)
{
int i=0,j=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(bord[i][j]==c)
{
bord[i][j]=(turn=='A'?'X':'O');
return;
}
}
}
}
void print(void)
{
int i=0,j=0;
printf("\n");
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%-4c",bord[i][j]);
}
printf("\n");
}
}
The key thing on this type of question is not to freeze up. Get something on the whiteboard:
- showell30@yahoo.com March 19, 20131) You want to draw the board. Have a DrawBoard class (or function).
2) You have players. Have a Player class.
3) Players take turns. Have a GamePlay class.
4) You need to keep track which moves have been made. Have a Game class.
5) You need to decide if somebody won. Have a GameEvaluate class.
Get something out there, then work with the interviewer to simplify things. Do you really need a special GameEvaluate class? Maybe a Game object can supply the method that says whether a game is over. Seems like a reasonable responsibility for the game class. But maybe the actual calculation drives out a simple Matrix class.
The key thing here is to be flexible and brainstorm.
Also, don't let the full complexity of the problem overwhelm you. Before you figure out how to orchestrate players taking turns, simplify the problem. Say that you just read the player's answers from a file, fill in the grid, and then say who won. If you can figure out how to model that, you have a good foundation for the rest of the problem.