Epic Systems Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Every time X or Y moves, look at all eight spokes from the new position (N/S/W/E/NE/SE/SW/NW), and determine if any of the new spoke lengths will reach exactly 3, 6, or 8. Depending on whether it's X or Y, update the running score appropriately. For X reaching 6 marks, my interpretation is that you only incrementally increase the score by 2 points, but you should clarify with the interviewer.
For a large value of N, considering caching spoke lengths in all eight directions for any given point. You will only need to maintain values at the endpoints. If you place an X southwest of a square that also has an X, read the cache to determine the neighbor's northeasterly spoke length, rather than iterating all the way to the end of the segment.
import java.lang.Math;
public class NTicTacToe {
static class Cell {
int x;
int y;
char val;
boolean visited;
}
private static int Xscore;
private static int Oscore;
private static Cell[][] board;
private static int n;
public static void main(String[] args) {
n = Integer.parseInt(args[0]);
board = new Cell[n][n];
Cell c;
for(int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
c = new Cell();
c.x = i;
c.y = j;
c.visited = false;
if ( ((int)(Math.random()*10)) % 2 == 1)
c.val = 'X';
else
c.val = 'O';
board[j][i] = c;
System.out.print(c.val + " ");
}
System.out.println("");
}
Xscore = 0;
Oscore = 0;
findWinner();
System.out.println("Xscore = " + Xscore);
System.out.println("Oscore = " + Oscore);
}
public static void findWinner() {
for(int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!board[j][i].visited)
{
findNeighbors(i, j);
}
}
}
}
public static void findNeighbors(int x, int y) {
for(int dx = -1; dx <=1; dx++)
{
for(int dy = -1; dy <=1; dy++)
{
char _val = board[y][x].val;
if( isValid(x + dx, y + dy) && board[y +dy][x + dx].val == board[y][x].val && !(dx == 0 && dy ==0) )
score( countPattern(_val, x, y, dx, dy), _val );
}
}
}
public static int countPattern(char _val, int x, int y, int dx, int dy) {
int ctr = 0;
while( isValid(x, y) && board[y][x].val == _val ) {
ctr++;
board[y][x].visited = true;
x += dx;
y += dy;
}
return ctr;
}
public static void score( int length, char _val ) {
if( _val == 'X' ) {
if( length >= 6 )
Xscore += 3;
else if( length >= 3 )
Xscore += 1;
}
else {
if( length >= 8 )
Oscore += 3;
else if( length >= 3 )
Oscore += 1;
}
}
public static boolean isValid(int x, int y) {
return (x < n && x >= 0 && y < n && y >= 0);
}
}
package Epic;
enum Piece{
X,Y,Empty;
}
public class UpdatedTicTacToe {
static Piece tictactoe(Piece[][] matrix,int N){
int scoreX=0;
int Xnum=0;
int Ynum=0;
int scoreY=0;
Piece preX=Piece.Empty;
Piece preY=Piece.Empty;
for(int i=0;i<N;i++){
//row
for(int j=0;j<N;j++){
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
if(matrix[i][j]==Piece.X){
if(preX==Piece.X){Xnum++;}
else{Xnum=1;preX=Piece.X;}
}
else if(matrix[i][j]==Piece.Y){
if(preY==Piece.Y){Ynum++;}
else{Ynum=1;preY=Piece.Y;}
}
}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
Xnum=0;
Ynum=0;
preX=Piece.Empty;
preY=Piece.Empty;
//col
for(int j=0;j<N;j++){
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
if(matrix[j][i]==Piece.X){
if(preX==Piece.X){Xnum++;}
else{Xnum=1;preX=Piece.X;}
}
else if(matrix[j][i]==Piece.Y){
if(preY==Piece.Y){Ynum++;}
else{Ynum=1;preY=Piece.Y;}
}
}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
Xnum=0;
Ynum=0;
preX=Piece.Empty;
preY=Piece.Empty;
//diag
if(matrix[i][i]==Piece.X){
if(preX==Piece.X){Xnum++;}
else{Xnum=1;preX=Piece.X;}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
}
else if(matrix[i][i]==Piece.Y){
if(preY==Piece.Y){Ynum++;}
else{Ynum=1;preY=Piece.Y;}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
}
Xnum=0;
Ynum=0;
preX=Piece.Empty;
preY=Piece.Empty;
//diaother
if(matrix[i][N-i-1]==Piece.X){
if(preX==Piece.X){Xnum++;}
else{Xnum=1;preX=Piece.X;}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
}
else if(matrix[i][N-i-1]==Piece.Y){
if(preY==Piece.Y){Ynum++;}
else{Ynum=1;preY=Piece.Y;}
if(Xnum==6){scoreX+=3;preX=Piece.Empty;Xnum=0;}
else if(Xnum==3&&preX==Piece.Empty){scoreX+=1;Xnum=0;}
if(Ynum==8){scoreY+=6;preY=Piece.Empty;Ynum=0;}
else if(Ynum==3&&preY==Piece.Empty){scoreY+=1;Ynum=0;}
}
}
if(scoreX>scoreY)return Piece.X;
if(scoreX<scoreY)return Piece.Y;
else return Piece.Empty;
}
public static void main(String[] args) {
Piece[][] matrix=new Piece[8][8];
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(i==2){
matrix[i][j]=Piece.X;
}
if(j==4){
matrix[i][j]=Piece.Y;
}
}
}
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix.length;j++){
System.out.print(matrix[i][j]);
}
System.out.print("\n");
}
System.out.println(tictactoe(matrix,8));
}
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int check1(char **mat, int x, int y, int start, int end, int num) {
int i = x;
int j = y;
if(x >= start+num) {
for(i = x-1 ; i >= x-num ; i--) {
if(mat[i+1][j] != mat[i][j] || mat[i+1][j] == '#')
return 0;
}
for(i = x ; i >= x-num ; i--)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check2(char **mat, int x, int y, int start, int size, int num) {
int i = x;
int j = y;
if(x >= start+num && y <= size-num) {
for(i = x-1, j = y+1 ; i >= x-num && j <= y+num; i--, j++) {
if(mat[i+1][j-1] != mat[i][j] || mat[i+1][j-1] == '#')
return 0;
mat[i+1][j-1] = '#';
}
for(i = x, j = y; i >= x-num && j <= y+num; i--, j++)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check3(char **mat, const int x,const int y, int start, int size, int num) {
int i = x;
int j = y;
if(y <= size-num) {
for(j = y+1 ; j <= y+num ; j++) {
if(mat[i][j-1] != mat[i][j] || mat[i][j-1] == '#')
return 0;
}
for(j = y; j <= y+num ; j++)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check4(char **mat, int x, int y, int start, int size, int num) {
int i = x;
int j = y;
if(x <= size-num && y <= size-num) {
for(i = x+1, j = y+1 ; i <= x+num && j <= y+num; i++, j++) {
if(mat[i-1][j-1] != mat[i][j] || mat[i-1][j-1] == '#')
return 0;
}
for(i = x, j = y ; i <= x+num && j <= y+num; i++, j++)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check5(char **mat, int x, int y, int start, int size, int num) {
int i = x;
int j = y;
if(x <= size-num) {
for(i = x+1 ; i <= x+num ; i++) {
if(mat[i-1][j] != mat[i][j] || mat[i-1][j] == '#')
return 0;
}
for(i = x ; i <= x+num ; i++)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check6(char **mat, int x, int y, int start, int size, int num) {
int i = x;
int j = y;
if(x <= size-num && y >= start+num) {
for(i = x+1, j = y-1 ; i <= x+num && j >= y-num ; i++, j--) {
if(mat[i-1][j+1] != mat[i][j] || mat[i-1][j+1] == '#')
return 0;
}
for(i = x, j = y ; i <= x+num && j >= y-num ; i++, j--)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check7(char **mat, int x, int y, int start, int size, int num) {
int i = x;
int j = y;
if(y >= start+num) {
for(j = y-1 ; j >= y-num ; j--) {
if(mat[i][j+1] != mat[i][j] || mat[i][j+1] == '#')
return 0;
}
for(j = y ; j >= y-num ; j--)
mat[i][j] = '#';
return 1;
}
return 0;
}
int check8(char **mat, int x, int y, int start, int SIZE, int num) {
int i = x;
int j = y;
if(x >= start+num && y >= start+num) {
for(i = x-1, j = y-1 ; i >= x-num && j >= y-num ; i--, j--) {
if(mat[i+1][j+1] != mat[i][j] || mat[i+1][j+1] == '#')
return 0;
}
for(i = x, j = y ; i >= x-num && j >= y-num ; i--, j--)
mat[i][j] = '#';
return 1;
}
return 0;
}
int winner(char **mat, int start, int end) {
int i = start;
int j = start;
int count = 0;
int value_x = 0;
int value_o = 0;
int val = 3-1;
for(i = start ; i <= end ; i++) {
for(j = start ; j <= end ; j++) {
if(mat[i][j] == 'x') {
value_x += check1(mat, i,j, start, end, val)+check2(mat, i,j, start, end, val)+check3(mat, i,j, start, end, val)+
check4(mat, i,j, start, end, val)+check5(mat, i,j, start, end, val)+check6(mat, i,j, start, end, val)+
check7(mat, i,j, start, end, val)+check8(mat, i,j, start, end, val);
}
else if(mat[i][j] == 'o') {
value_o+= check1(mat, i,j, start, end, val)+check2(mat, i,j, start, end, val)+check3(mat, i,j, start, end, val)+
check4(mat, i,j, start, end, val)+check5(mat, i,j, start, end, val)+check6(mat, i,j, start, end, val)+
check7(mat, i,j, start, end, val)+check8(mat, i,j, start, end, val);
}
}
}
printf("X : %d O : %d\n", value_x, value_o);
if(value_x > value_o)
return 1;
else
return 0;
}
int main() {
char **mat = (char **)malloc(sizeof(char *)*6);
mat[0] = (char *)malloc(sizeof(char)*6);
strcpy(mat[0], "xxxooo");
mat[1] = (char *)malloc(sizeof(char)*6);
strcpy(mat[1], "xxxoxo");
mat[2] = (char *)malloc(sizeof(char)*6);
strcpy(mat[2], "oxoxox");
mat[3] = (char *)malloc(sizeof(char)*6);
strcpy(mat[3], "oooooo");
mat[4] = (char *)malloc(sizeof(char)*6);
strcpy(mat[4], "xooooo");
mat[5] = (char *)malloc(sizeof(char)*6);
strcpy(mat[5], "ooooox");
/*xxxooo
xoxoxo
oxoxox
oooooo
xooooo
ooooox
*/
if(winner(mat, 0, strlen(mat[0])-1)) {
printf("X wins\n");
}
printf("O wins\n");
return 0;
}
let num be number of elements which together in a line whether horizontal, vertical or diagonal adds to the total points.
Let us assume num == 3;
check1 function -- from a given co-ordinate (x,y) checks whether (x, y), (x-1,y), (x-2,y) are all equal. x denotes row number.
check2 function -- from a given co-ordinate (x,y) checks whether (x, y), (x-1,y+1), (x-2,y+2) are all equal.
and so on...for total of 8 rays from (x,y).
loop for each (x,y) and calculate check1+check2+....check8 for each (x,y), if any check function returns 1, we set all the values in matrix corresponding to that sequence as '#', so that we don't add it again
package p1;
import java.util.ArrayList;
import java.util.Random;
public class tic_toe {
public static void main(String args[])
{
char[][] tic=new char[3][3];
for(int i=0;i<tic.length;i++){
for(int j=0;j<tic.length;j++)
{
Random randomGenerator = new Random();
int randomInt = randomGenerator.nextInt(100);
char c= randomInt % 2 == 0 ? 'X' : 'O';
tic[i][j]=c;
}
}
for(int i=0;i<tic.length;i++){
System.out.println();
for(int j=0;j<tic.length;j++)
{
System.out.print(tic[i][j]+" ");
}
}
win(tic);
}
static void win(char[][] tic)
{ int sx=0,so=0;
String s1=new String();
for(int i=0;i<3;i++)
{
if(i==0)
{
for(int i1=0;i1<tic.length;i1++)
{
s1 +=tic[i1][i1];
}
score(s1,sx,so);
}
System.out.println();
if(i==1){
String s11=new String();
String s12=new String();
ArrayList<Integer> arr=new ArrayList<Integer>();
for(int i2=0;i2<tic.length;i2++)
{
for(int j2=0;j2<tic.length;j2++)
{
s11 +=tic[i2][j2];
}
s12=s11;
s11="";
arr=score(s12,sx,so);
sx=(int) arr.get(0);
so=(int) arr.get(1);
arr.clear();
}
}
System.out.println();
if(i==2){
String s11=new String();
String s12=new String();
ArrayList<Integer> arr=new ArrayList<Integer>();
for(int i2=0;i2<tic.length;i2++)
{
for(int j2=0;j2<tic.length;j2++)
{
s11 +=tic[j2][i2];
}
s12=s11;
s11="";
arr=score(s12,sx,so);
sx=(int) arr.get(0);
so=(int) arr.get(1);
arr.clear();
}
}
}
System.out.println();
System.out.print("value of sxfinal="+sx+" ");
System.out.print("value of sofinal="+so+" ");
System.out.println();
if(sx>so)
{
System.out.print("player X wins by "+(sx-so));
}
else if(sx<so)
{
System.out.print("player O wins by "+(so-sx));
}
else if(sx==so)
{
System.out.print("match tied");
}
}
static ArrayList<Integer> score(String s,int sx,int so)
{
ArrayList<Integer> ls=new ArrayList<Integer>();
String s1=s;
String input1="XXX";
String input2="OOO";
String input3="XXXXXX";
String input4="OOOOOOOO";
String s2=s1.replaceAll(input3,"r");
String s3=s2.replaceAll(input4,"s");
String s4=s3.replaceAll(input1,"p");
String s5=s4.replaceAll(input2,"q");
for(int i1=0;i1<s5.length();i1++)
{
if(s5.charAt(i1)=='p'){sx=sx+1;}
else if(s5.charAt(i1)=='q'){so=so+1;}
else if(s5.charAt(i1)=='r'){sx=sx+3;}
else if(s5.charAt(i1)=='s'){so=so+6;}
}
ls.clear();
ls.add(sx);
ls.add(so);
return ls;
}
}
Hey, can anybody clarify this problem.I didn't get it..???
- Sam May 02, 2013