Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
def longest_jump_path(i,j, player):
length_down, length_up, length_left, length_right = 0, 0, 0, 0
# down
if in_bounds(i+1,j) and in_bounds(i+2,j):
if grid[i+1][j] != 0 and grid[i+1][j] != player and grid[i+2][j] == 0:
if ((i+1, j) not in jumped):
jumped.append((i+1, j))
length_down = 1 + longest_jump_path(i+2, j, player)
jumped.remove((i+1,j))
# up
if in_bounds(i-1,j) and in_bounds(i-2,j):
if grid[i-1][j] != 0 and grid[i-1][j] != player and grid[i-2][j] == 0:
if ((i-1, j) not in jumped):
jumped.append((i-1, j))
length_up = 1 + longest_jump_path(i-2, j, player)
jumped.remove((i-1,j))
# left
if in_bounds(i,j-1) and in_bounds(i,j-2):
if grid[i][j-1] != 0 and grid[i][j-1] != player and grid[i][j-2] == 0:
if ((i, j-1) not in jumped):
jumped.append((i,j-1))
length_left = 1 + longest_jump_path(i, j-2, player)
jumped.remove((i,j-1))
# right
if in_bounds(i,j+1) and in_bounds(i,j+2):
if grid[i][j+1] != 0 and grid[i][j+1] != player and grid[i][j+2] == 0:
if ((i, j+1) not in jumped):
jumped.append((i,j+1))
length_right = 1 + longest_jump_path(i, j+2, player)
jumped.remove((i,j+1))
return max([length_down, length_up, length_left, length_right])
def in_bounds(i,j):
return i >= 0 and i < len(grid) and j >= 0 and j <= len(grid[0])
jumped = []
grid = [[0,0,0,0,0,0], [0,1,2,0,2,0], [0,2,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0]]
print (longest_jump_path(1,1,grid[1][1])) # start at 1,1
Still working on the requirement where player cannot jump above another opponent.I'll update that soon.. Till then here is code if some one wants to try.
public class JumpGame {
static int N = 10;
static int[][] grid;
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// grid of size N*N which can have values 0,1,2
grid = new int[N][N];
// suppose the player are in the grid and the value of grid is 0 if no player on that position
for(int i=0;i< N;i++){
for(int j=0;j< N;j++){
grid[i][j] = 0;
}
}
// let player 1 be at [0,2] , player 2 be at [0,4]
grid[2][1] = 1;
grid[2][2] = 2;
grid[0][0] = 3;
grid[1][1] = 4;
// longest possible jump in the grid
for(int i=0;i< N;i++){
for(int j=0;j< N;j++){
if(grid[i][j] > 0){
System.out.println( " The longest Jump distance for player"+ grid[i][j]+" is " +findLongestJump(i,j));
}
}
}
}
private static int findLongestJump(int i,int j) {
int jumpHorizontal = 0;
int jumpVertical = 0;
// looking for a highest horizontal jump distance
for(int y=N-1; y>=0;y--){
if(grid[i][y]== 0){
//check the distance form the end of the grid
if(jumpHorizontal < (N-1-j)){
jumpHorizontal = N-1-j;
}
//check the distance from the start of the grid
if(jumpHorizontal < j-1){
jumpHorizontal = j-1;
}
}
}
//for finding highest vertical jump distance similar logic like horizontal loop
for(int v=N-1; v>=0;v--){
if(grid[v][j] == 0){
if(jumpVertical < (N-1-i)){
jumpVertical = N-1-i;
}
if(jumpVertical < i-1){
jumpHorizontal = i-1;
}
}
}
return (jumpHorizontal> jumpVertical? jumpHorizontal:jumpVertical);
}
}
Logic:
findLength(row-1, col, len, playerCode);
findLength(row+1, col, len, playerCode);
findLength(row, col-1, len, playerCode);
findLength(row, col+1, len, playerCode);
Full Code:
Compiled and Tested, Works fine, please comment if there is any bug
package interviews;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Random;
public class JumperGame {
public static final int N = 3;
public static int[][] board;
public static boolean [][] visited;
public static boolean flagOther;
public static ArrayList<Integer> allPossibleLen;
public static void initializeBoard(){
Random rg = new Random();
board = new int[N][N];
visited = new boolean[N][N];
allPossibleLen = new ArrayList ();
flagOther = false;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int rndInt = rg.nextInt(5);
board[i][j] = rndInt%3;
visited[i][j] = false;
}
}
}
public static void displayBoard(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.print(board[i][j] + " ");
}
System.out.println("");
}
}
public static void resetBookMarks(){
flagOther = false;
//Reset visited matrix
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
visited[i][j] = false;
}
}
}
public static int findLength(int row, int col, int len, int playerCode){
if(row<0 || row>=N)
return len;
else if (col<0 || col>=N)
return len;
else if(board[row][col]==0){
visited[row][col] = true;
//board[row][col] = playerCode;
return len;
}
else if(visited[row][col])
return len;
else if(!flagOther && board[row][col]!=playerCode){ //Other players box can be visited only once
flagOther = true;
visited[row][col]=true;
len = len+1;
}
else if(board[row][col]==playerCode){
visited[row][col]=true;
len = len+1;
}
int newLen = findLength(row-1, col, len, playerCode);
allPossibleLen.add(newLen);
newLen = findLength(row+1, col, len, playerCode);
allPossibleLen.add(newLen);
newLen = findLength(row, col-1, len, playerCode);
allPossibleLen.add(newLen);
newLen = findLength(row, col+1, len, playerCode);
allPossibleLen.add(newLen);
return len;
}
public static boolean isGameOver(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(board[i][j]==0)
return false;
}
}
return true;
}
public static void playGame(){
Scanner in = new Scanner(System.in);
int player=1;
int row,col;
while(!isGameOver()){
System.out.println("Player "+player+" turn");
System.out.println("Enter row index");
row=in.nextInt();
System.out.println("Enter col index");
col=in.nextInt();
int len = 0;
len = findLength(row,col,len,player);
allPossibleLen.add(len);
//System.out.println("Possible lengths are");
//for(int i=0;i<allPossibleLen.size();i++)
// System.out.println(allPossibleLen.get(i));
System.out.println("Maximum length is:"+Collections.max(allPossibleLen));
player = (player%2)+1;
displayBoard();
resetBookMarks();
}
}
public static void main(String[] args){
initializeBoard();
displayBoard();
playGame();
}
}
#include <iostream>
#include<cmath>
using namespace std;
int turn=1, other=2, arr[4][4]={{1,0,0,0},{0,0,1,2},{2,0,0,2},{0,0,2,1}};
string motion="+x axis";
bool* processed=new bool[sizeof(arr)/sizeof(int)];
void initialize_processed();
void print_array();
void update(int i, int j,int max);
int jum(int p, int q, int turn)
{
if(turn!=arr[p][q])
{
cout<<"\n Attempting to move other teams object";
cout<<"\n Enter position: turn is on for "<<turn;
cin>>p>>q;
}
int i=p ,j=q,max,jumps=0;
//check horizontal +x-axis
while(j<(sqrt(sizeof(arr)/sizeof(int))-1))
{
if(arr[i][j+1]==0) jumps++;
else if(arr[i][j+1]==other)
{
if(processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]==true) break;
else
{
processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]=true;
jumps++;
}
}
else break;
j++;
}
max=jumps; jumps=0; j=q;
//check horizontal -x axis
while(j>0)
{
if(arr[i][j-1]==0) jumps++;
else if(arr[i][j-1]==other)
{
if(processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]==true) break;
else
{
processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]=true;
jumps++;
}
}
else break;
j--;
}
if(max<jumps) { max=jumps; motion="-x axis"; }
jumps=0; j=q;
//check horizontal -y axis
while(i<(sqrt(sizeof(arr)/sizeof(int))-1))
{
if(arr[i+1][j]==0) jumps++;
else if(arr[i+1][j]==other)
{
if(processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]==true)
break;
else
{
processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]=true;
jumps++;
}
}
else { break; }
i++;
}
if(max<jumps) { max=jumps; motion="-y axis"; }
jumps=0; i=p;
//check horizontal +y axis
while(i>0)
{
if(arr[i-1][j]==0) jumps++;
else if(arr[i-1][j]==other)
{
if(processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]==true) break;
else
{
processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]=true;
jumps++;
}
}
else break;
i--;
}
if(max<jumps) { max=jumps; motion="+y axis"; }
update(p,q,max);
return max;
}
int main()
{
int p,q,count;
bool more;
print_array();
initialize_processed();
do
{
cout<<"\n Enter position: turn is on for "<<turn;
cin>>p>>q;
count = jum(p,q,turn);
cout<<"\n Largest number of possible jumps are "<<count<<" in the direction of"<<motion<<endl;
print_array();
cout<<"\n Do you wish to play more? Type 1 for true / 0 for false";
cin>>more;
swap(turn,other);
}while(more);
return 0;
}
void print_array()
{
for(int i=0;i<sqrt(sizeof(arr)/sizeof(int));i++)
{
for(int j=0;j<sqrt(sizeof(arr)/sizeof(int));j++)
{
cout<<arr[i][j];
}
cout<<endl;
}
}
void initialize_processed()
{
for(int j=0;j<sizeof(arr)/sizeof(int);j++)
{
processed[j]=false;
}
}
void update(int i, int j,int max)
{
arr[i][j]=0;
int counter=0;
processed[(int)(sqrt(sizeof(arr)/sizeof(int))*i)+j]=false;
if(motion=="+x axis")
{
for(counter=j;counter<=max;counter++)
{
if(arr[i][counter]==other) max++;
}
arr[i][j+max]=turn;
}
else if(motion=="-x axis")
{
for(counter=j;counter>=0;counter--)
{
if(arr[i][counter]==other) max++;
}
arr[i][j-max]=turn;
}
else if(motion=="-y axis")
{
for(counter=i;counter<=max;counter++)
{
if(arr[counter][j]==other) max++;
}
arr[i+max][j]=turn;
}
else if(motion=="+y axis")
{
for(counter=i;counter>=0;counter--)
{
if(arr[counter][j]==other) max++;
}
arr[i-max][j]=turn;
}
}
Can you explain the problem statement a little more? I understood the following, correct me if I am wrong anywhere.
- Akhil November 11, 2014Considering the following 4x4 GRID
0202
0100
1020
0001
and the given position is (1, 2) which is a ZERO and its Player-1's turn to play
There are 3 possible Jumps
1. (1, 2) ---> (0, 2) => jump size = 1 block
2. (1, 2) ---> (1, 3) => jump size = 1 block
3. (1, 2) ---> (3, 2) => jump size = 3 blocks (jumping over player-2 in (2, 2))
There is another possible jump of size 3 blocks (1, 2) ---> (1, 0) but player-1 has to jump over his own block in (1, 1). If this is not accepted there is only 1 possible longest jump which is from (1, 2) ---> (3, 2) or else we have 2 possible longest jumps of size 3 blocks which are (1, 2) ---> (3, 2) and (1, 2) ---> (1, 0)