Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Aug 21, 2011
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Jan 29, 2012
A dumb solution, which goes through every option
public class TicTacToe {
public static boolean isWinner(int[][] arr, int player){
int count = 0;
for (int i=0; i<arr.length; ++i){
for (int j=0; j<arr.length; ++j){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int j=0; j<arr.length; ++j){
for (int i=0; i<arr.length; ++i){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int i=0; i<arr.length; ++i){
for (int j=i; j==i; ++j ){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int j=0; j<arr.length; ++j){
for (int i=j; i==j; ++i ){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
return false;
}
public static void main(String[] args) {
int[][] arr = new int[2][2];
arr[0][0] = 1;
arr[1][1] = 1;
System.out.println(isWinner(arr, 1));
}
}
public class TicTacToe {
public static boolean isWinner(int[][] arr, int player){
int count = 0;
for (int i=0; i<arr.length; ++i){
for (int j=0; j<arr.length; ++j){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int j=0; j<arr.length; ++j){
for (int i=0; i<arr.length; ++i){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int i=0; i<arr.length; ++i){
for (int j=i; j==i; ++j ){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
count = 0;
for (int j=0; j<arr.length; ++j){
for (int i=j; i==j; ++i ){
if (arr[i][j] == player){
++count;
}
else{
break;
}
}
}
if (count == arr.length){
return true;
}
return false;
}
public static void main(String[] args) {
int[][] arr = new int[2][2];
arr[0][0] = 1;
arr[1][1] = 1;
System.out.println(isWinner(arr, 1));
}
}
Helpful Answer?
Yes |
No
Inappropriate?
Apr 10, 2012
are you sure?
Helpful Answer?
Yes |
No
Inappropriate?
Apr 22, 2012
This is an interesting question. If you have a n*n board, then you might want to check all rows, all columns and the two diagonals, i.e., a running time of O(n^2). However, comparing rows and columns separately leads to traversing the board twice, so maybe there's a way to do it faster than that.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
1 of 9 people found this helpful
by reed: