Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain the problem statement a little more? I understood the following, correct me if I am wrong anywhere.

Considering 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)

- Akhil November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think they mentioned any kind of "jump over" actions. Besides, jump size is measured by how many times you've jumped instead of how many blocks you have jumped.

- XiaoPiGu December 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dbhage November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

    }
    
}

- Krunal December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
    }
}

- sreevathsan.ravi January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you need to reset allPossibleLen also while resetting bookmarks.

- Venkata January 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did some one come up with a correct solution?

- Anonymous February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did some one come up with a solution?

- Anonymous February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}
}

- ms July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you post a direct link to the solution from geeksforgeeks then? "This is a classic DP question kindly refer to geeksforgeeks" is not a solution and is very vague.

- dbhage November 11, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More