Amazon Interview Question
Software DevelopersCountry: United States
public static boolean isSomeoneWonGame(char[][] game) {
int top = 1;
int bottom = 1;
int left = 1;
int right = 1;
for (int i = 1; i < 3; i++) {
if (game[0][i] == game[0][i - 1]) {
top++;
}
if (game[i][0] == game[i - 1][0]) {
left++;
}
if (game[2][i] == game[2][i - 1]) {
bottom++;
}
if (game[i][2] == game[i - 1][2]) {
right++;
}
if (top == 3 || left == 3 || right == 3 || bottom == 3) {
return true;
}
}
int topLeft = 1;
int topRight = 1;
for (int i = 1; i < 3; i++) {
if (game[i][i] == game[i - 1][i - 1]) {
topLeft++;
}
if (game[i][2 - i] == game[i - 1][2 - i + 1]) {
topRight++;
}
if (topLeft == 3 || topRight == 3) {
return true;
}
}
return false;
}
public static void testSolution() {
// test win row
Character[][] board = new Character[][] {
{'X', 'X', 'X'},
{'O', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
// test win col
board = new Character[][] {
{'X', 'O', 'X'},
{'X', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
// test win diag
board = new Character[][] {
{'X', 'O', 'O'},
{'O', 'X', 'O'},
{'X', 'O', 'X'}
};
// test no win
board = new Character[][] {
{'X', 'O', 'X'},
{'O', 'O', 'X'},
{'X', 'X', 'O'}
};
System.out.println(detectWin(board));
// test win col O
board = new Character[][] {
{'X', 'O', 'O'},
{'O', 'X', 'O'},
{'X', 'O', 'O'}
};
System.out.println(detectWin(board));
}
public static boolean detectWin(Character[][] board) {
return (testToken(board, 'X') || testToken(board, 'O'));
}
public static boolean testToken(Character[][] board, Character token) {
// check rows
int seq = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j].equals(token)) {
seq++;
}
}
if (seq == 3) {
return true;
}
seq = 0;
}
seq = 0;
// check cols
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[j][i].equals(token)) {
seq++;
}
}
if (seq == 3) {
return true;
}
seq = 0;
}
// check diagonals
if ((board[0][0].equals(token) &&
board[1][1].equals(token) &&
board[2][2].equals(token)) ||
(board[2][0].equals(token) &&
board[1][1].equals(token) &&
board[0][2].equals(token))) {
return true;
}
return false;
}
public static boolean isSomeoneWonGame(char[][] game) {
int top = 1;
int bottom = 1;
int left = 1;
int right = 1;
int topLeft = 1;
int topRight = 1;
for (int i = 1; i < 3; i++) {
if (game[0][i] == game[0][i - 1]) {
top++;
}
if (game[i][0] == game[i - 1][0]) {
left++;
}
if (game[2][i] == game[2][i - 1]) {
bottom++;
}
if (game[i][2] == game[i - 1][2]) {
right++;
}
if (top == 3 || left == 3 || right == 3 || bottom == 3) {
return true;
}
if (game[i][i] == game[i - 1][i - 1]) {
topLeft++;
}
if (game[i][2 - i] == game[i - 1][2 - i + 1]) {
topRight++;
}
if (topLeft == 3 || topRight == 3) {
return true;
}
}
return false;
}
Assumption int t[3][3] is initialized with zero, consider 'x' as 1 and '0' as 2.
public static boolean findWon(int [][] t) {
int a=0;
int b=0;
for (int i = 0; i < 3; i++) {
a=0;
b=0;
for (int j = 0; j < 3; j++) {
a+=t[i][j];
b+=t[j][i];
}
if(a==3 || a==6 || b==3 || b==6) {
return true;
}
}
for (int i = 0; i < 3; i++) {
a+=t[i][i];
}
if(a==3 || a==6) {
return true;
}
for (int i = 0, j=2; i < 3; i++) {
a+=t[i][j-i];
}
if(a==3 || a==6) {
return true;
}
return false;
}
Assume tic-tac-toe table is initialized with zero, then consider 'X' as 1 and 'O' as 2;
public static boolean findWon(int [][] t) {
int a=0;
int b=0;
for (int i = 0; i < 3; i++) {
a=0;
b=0;
for (int j = 0; j < 3; j++) {
a+=t[i][j];
b+=t[j][i];
}
if(a==3 || a==6 || b==3 || b==6) {
return true;
}
}
for (int i = 0; i < 3; i++) {
a+=t[i][i];
}
if(a==3 || a==6) {
return true;
}
for (int i = 0, j=2; i < 3; i++) {
a+=t[i][j-i];
}
if(a==3 || a==6) {
return true;
}
return false;
}
public static boolean findWon(int [][] t) {
int a=0;
int b=0;
for (int i = 0; i < 3; i++) {
a=0;
b=0;
for (int j = 0; j < 3; j++) {
a+=t[i][j];
b+=t[j][i];
}
if(a==3 || a==6 || b==3 || b==6) {
return true;
}
}
for (int i = 0; i < 3; i++) {
a+=t[i][i];
}
if(a==3 || a==6) {
return true;
}
for (int i = 0, j=2; i < 3; i++) {
a+=t[i][j-i];
}
if(a==3 || a==6) {
return true;
}
return false;
}
public class TicTacToe {
public static boolean isWon(char board[][]) {
if (board.length != 3 || board[0].length != 3) {
throw new IllegalArgumentException("Wrong Game");
}
for (int i = 0; i < 3; i++) {
if (checkRow(board, i))
return true;
if (checkColumn(board, i))
return true;
}
if (checkDiagonals(board)) {
return true;
}
return false;
}
private static boolean checkRow(char board[][], int row) {
if (board[row][0] == board[row][1] && board[row][1] == board[row][2])
return true;
return false;
}
private static boolean checkColumn(char board[][], int column) {
if (board[0][column] == board[1][column]
&& board[1][column] == board[2][column])
return true;
return false;
}
private static boolean checkDiagonals(char board[][]) {
if (board[0][0] == board[1][1] && board[1][1] == board[2][2])
return true;
if (board[2][0] == board[1][1] && board[1][1] == board[0][2])
return true;
return false;
}
}
public class TicTacToe {
public static boolean isWon(char board[][]) {
if (board.length != 3 || board[0].length != 3) {
throw new IllegalArgumentException("Wrong Game");
}
for (int i = 0; i < 3; i++) {
if (checkRow(board, i))
return true;
if (checkColumn(board, i))
return true;
}
if (checkDiagonals(board)) {
return true;
}
return false;
}
private static boolean checkRow(char board[][], int row) {
if (board[row][0] == board[row][1] && board[row][1] == board[row][2])
return true;
return false;
}
private static boolean checkColumn(char board[][], int column) {
if (board[0][column] == board[1][column]
&& board[1][column] == board[2][column])
return true;
return false;
}
private static boolean checkDiagonals(char board[][]) {
if (board[0][0] == board[1][1] && board[1][1] == board[2][2])
return true;
if (board[2][0] == board[1][1] && board[1][1] == board[0][2])
return true;
return false;
}
}
public class TicTacToe {
public static boolean isWon(char board[][]) {
if (board.length != 3 || board[0].length != 3) {
throw new IllegalArgumentException("Wrong Game");
}
for (int i = 0; i < 3; i++) {
if (checkRow(board, i))
return true;
if (checkColumn(board, i))
return true;
}
if (checkDiagonals(board)) {
return true;
}
return false;
}
private static boolean checkRow(char board[][], int row) {
if (board[row][0] == board[row][1] && board[row][1] == board[row][2])
return true;
return false;
}
private static boolean checkColumn(char board[][], int column) {
if (board[0][column] == board[1][column]
&& board[1][column] == board[2][column])
return true;
return false;
}
private static boolean checkDiagonals(char board[][]) {
if (board[0][0] == board[1][1] && board[1][1] == board[2][2])
return true;
if (board[2][0] == board[1][1] && board[1][1] == board[0][2])
return true;
return false;
}
}
My C/C++ solution
//
// Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
#include "stdafx.h"
#include <string.h>
#include <process.h>
int gMat[3][3]=
{
{1,1,0},
{1,0,0},
{1,2,2}
};
int gWinner=0;
char gSeqName[32];
bool check(int r, int c, int dr, int dc, int& winner, char* posname )
{
if ((gMat[c][r] !=0) && (gMat[c][r] == gMat[c+dc][r+dr]) &&(gMat[c][r] == gMat[c+dc+dc][r+dr+dr]) )
{
winner = gMat[c][r];
strcpy(gSeqName, posname);
return true;
}
winner = 0;
return false;
}
int main(int argc, char* argv[])
{
// check vertical
gWinner = 0;
strcpy(gSeqName,"");
if ( check(0,0, +1,0, gWinner, "first row")
|| check(0,1, +1,0, gWinner, "second row")
|| check(0,2, +1,0, gWinner, "third row")
|| check(0,0, 0,+1, gWinner, "first col")
|| check(1,0, 0,+1, gWinner, "second col")
|| check(2,0, 0,+1, gWinner, "third col")
|| check(0,0, +1,+1, gWinner, "Top left diagonal")
|| check(0,2, +1,-1, gWinner, "Top right diagonal") )
{
printf("Player[%d] Wins in[%s]\n", gWinner, gSeqName);
}
else
{
printf("No winners\n", gWinner, gSeqName);
}
system("PAUSE");
return 0;
}
- techinterviewquestion.com May 12, 2016