Epic Systems Interview Question for Software Developers


Country: United States
Interview Type: Written Test




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

class Q1{
	
	public static void main(String[] args)
	{
	
		char[][] mat={ 
				{'t','b','c','h'},
				{'g','h','e','i'},
				{'g','h','i','w'},
				{'g','e','p','w'}
		};
		
		//char[] chars={'a','e','i'};
		//char[] chars={'g','h','w'};
		char[] chars={'g','h','i'};
		int matDim=4;
		
		int charIndex=0;
		
		boolean foundCharInCoord=false;
		
		boolean allFound=false;
		
		Coordinate aCoord=new Coordinate(-99,-99);
		
		abc:
		for(int i=0; i<matDim; i++)
		{
			for(int j=0; j<matDim;j++)
			{
				aCoord=new Coordinate(i,j);
				System.out.println("Checking coord: "+aCoord.toString());
				if(foundChar(chars[charIndex],aCoord,mat))
				{
					System.out.println("Found "+chars[charIndex]+" at "+aCoord.toString());
					boolean a=getSequenceFound(chars,charIndex,mat,matDim,aCoord);
					System.out.println(a);
					if(a)
					{
						allFound=true;
						System.out.println("breaking..");
						break abc;
					}
				}//end if foundChar

			}
		}
		if(allFound)
		{
			System.out.println("Found given word at "+aCoord.toString());
		}else
		{
			System.out.println("Could not find given word at "+aCoord.toString());
		}
		System.out.println("Done..");
		
		
		
		
	}
	
	public static boolean getSequenceFound(char[] chars,int posn,char[][] mat,int matDim,Coordinate aSoln)
	{
		
		
		boolean success=false;
		
		
		Coordinate nextPath=Q1.getNextPath(matDim, aSoln.row, aSoln.col);
		
		int tempLength=posn+1;
		
		if(tempLength==chars.length)
			return true;
		
		if(foundChar(chars[posn+1],nextPath,mat ))
		{
			System.out.println("--->Found "+chars[posn+1]+ " at "+nextPath.toString());
			
			success= getSequenceFound(chars,posn+1,mat,matDim,nextPath);
			
		}
		else
		{
			success=false;
			
		}
		return success;
	}

	public static Coordinate searchForCharInMat(int matDim,char[][] mat,char findChar,Coordinate aCoord)
	{
		Coordinate foundCoord=new Coordinate();
		iterRow:
		for(int i=0;i<matDim;i++)
		{
			iterCol:
			for(int j=0; j<matDim;j++)			
			{
				
				if(mat[i][j]==findChar)
				{
					System.out.println("Comparing:"+findChar+" to "+mat[i][j]+"\n");
					foundCoord.row=i;
					foundCoord.col=j;
					break iterRow;
				}
			
		
			}//end for (iterate through columns of mat)
		
		
		}//end for(iterate through rows of mat)
	
		return foundCoord;
		
	}
	public static boolean foundChar(char toFind,Coordinate searchCoord,char[][] mat)
	{
		//System.out.println("Found "+toFind+" in "+searchCoord.toString());
		if(mat[searchCoord.row][searchCoord.col]==(toFind)){
			
			return true;
		}
		else
			return false;
	}
	public static Coordinate getNextPath(int matDim,int row,int col)
	{
		Coordinate goRight=new Coordinate();
		goRight.col=col+1; //one on right
		goRight.row=row;   //same row
		
		//Maybe want to get next path in other directions as well...?

		return goRight;
	}
	
}

- Apil Tamang March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Uses recursion. Searches for a word only appearing horizontally and in the right hand-side, but it shouldn't be too hard to adapt it to look for words in any direction. Class coordinate is not shown, but it is a simple struct with two fields: int row, and int col.

class Q1{
	
	public static void main(String[] args)
	{
	
		char[][] mat={ 
				{'t','b','c','h'},
				{'g','h','e','i'},
				{'g','h','i','w'},
				{'g','e','p','w'}
		};
		
		//char[] chars={'a','e','i'};
		//char[] chars={'g','h','w'};
		char[] chars={'g','h','i'};
		int matDim=4;
		
		int charIndex=0;
		
		boolean foundCharInCoord=false;
		
		boolean allFound=false;
		
		Coordinate aCoord=new Coordinate(-99,-99);
		
		abc:
		for(int i=0; i<matDim; i++)
		{
			for(int j=0; j<matDim;j++)
			{
				aCoord=new Coordinate(i,j);
				System.out.println("Checking coord: "+aCoord.toString());
				if(foundChar(chars[charIndex],aCoord,mat))
				{
					System.out.println("Found "+chars[charIndex]+" at "+aCoord.toString());
					boolean a=getSequenceFound(chars,charIndex,mat,matDim,aCoord);
					System.out.println(a);
					if(a)
					{
						allFound=true;
						System.out.println("breaking..");
						break abc;
					}
				}//end if foundChar

			}
		}
		if(allFound)
		{
			System.out.println("Found given word at "+aCoord.toString());
		}else
		{
			System.out.println("Could not find given word at "+aCoord.toString());
		}
		System.out.println("Done..");
		
		
		
		
	}
	
	public static boolean getSequenceFound(char[] chars,int posn,char[][] mat,int matDim,Coordinate aSoln)
	{
		
		
		boolean success=false;
		
		
		Coordinate nextPath=Q1.getNextPath(matDim, aSoln.row, aSoln.col);
		
		int tempLength=posn+1;
		
		if(tempLength==chars.length)
			return true;
		
		if(foundChar(chars[posn+1],nextPath,mat ))
		{
			System.out.println("--->Found "+chars[posn+1]+ " at "+nextPath.toString());
			
			success= getSequenceFound(chars,posn+1,mat,matDim,nextPath);
			
		}
		else
		{
			success=false;
			
		}
		return success;
	}

	public static Coordinate searchForCharInMat(int matDim,char[][] mat,char findChar,Coordinate aCoord)
	{
		Coordinate foundCoord=new Coordinate();
		iterRow:
		for(int i=0;i<matDim;i++)
		{
			iterCol:
			for(int j=0; j<matDim;j++)			
			{
				
				if(mat[i][j]==findChar)
				{
					System.out.println("Comparing:"+findChar+" to "+mat[i][j]+"\n");
					foundCoord.row=i;
					foundCoord.col=j;
					break iterRow;
				}
			
		
			}//end for (iterate through columns of mat)
		
		
		}//end for(iterate through rows of mat)
	
		return foundCoord;
		
	}
	public static boolean foundChar(char toFind,Coordinate searchCoord,char[][] mat)
	{
		//System.out.println("Found "+toFind+" in "+searchCoord.toString());
		if(mat[searchCoord.row][searchCoord.col]==(toFind)){
			
			return true;
		}
		else
			return false;
	}
	public static Coordinate getNextPath(int matDim,int row,int col)
	{
		Coordinate goRight=new Coordinate();
		goRight.col=col+1; //one on right
		goRight.row=row;   //same row
		
		//Maybe want to get next path in other directions as well...?

		return goRight;
	}
	
}

- Apil Tamang March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <cstring>
#include <unordered_map> // for hashing
using namespace std;

//define directions
const int NW = 1;
const int NN = 2;
const int NE = 3;
const int WW = 4;
const int EE = 5;
const int SW = 6;
const int SS = 7;
const int SE = 8;


/*
N*N matrix having various alphabets in different cells is given. Also a word is given. You have to find the position of this word in the given matrix.


Approach:
1. set up double for loop to traverse the matrix, looking for the 1st char of target word
2. once found, search the rest chars from each of 8 possible directions, if mismatch or border condition happens, discard that direction and continue with the other one; if successfully locate all the chars, the function return true and stores the coordinate of 1st char and the direction info to array.
3. if all nxn trials failed, we return false to indicate non-existance of the word.
*/

int xof(int dir)
{
if (dir == NW || dir == NN || dir == NE)
return -1;
else if (dir == WW || dir == EE)
return 0;
else
return 1;
}
int yof(int dir)
{
if (dir == NW || dir == WW || dir == SW)
return -1;
else if (dir == NN || dir == SS)
return 0;
else
return 1;
}

// function takes matrix and target word and size n, stores the location of found word to res array
bool findWord(char** matrix, char* word, int n, int* res)
{
// set up double for loop to search for 1st char
for (int i =0; i<n; i++)
{
for (int j=0; j<n;j++)
{
//if found, go through all 8 directions to search for the rest
if (matrix[i][j] == word[0])
{
cout<< "find char "<<word[0]<<" at ("<< i<<", "<<j<<") "<<endl;
//number 1-8 indicates direction NW, N, NE, W, E, SW, S, SE
for (int k=1; k<=8; k++)
{
int x = i;
int y = j;
char* tmp_word = word; //local copy of word
tmp_word++; // delete first char
int count = strlen(tmp_word); //count = total_char - 1
bool canFind = false; //check condition
//search for rest chars; count decrements 1 each time a subsequent char is found, or instantly becomes 0 to indicate nonexistance in current direction, canFind will indicate the result of search
while(count)
{
x = x + xof(k);
y = y + yof(k);
//cout<< "(x,y) = ("<<x<<", "<<y<<") "<<endl;
//if find the next char, we gonna continue search for next char until tmp_word has no char
if (x>=0 && x<n && y>=0 && y<n && matrix[x][y] == tmp_word[0])
{
cout<< "find char "<<tmp_word[0]<<" at ("<< x<<", "<<y<<") "<<endl;
canFind = true;
tmp_word++;
count--;
}
// if x,y out of range or char mismatch, then return false for unable to find word
else
{
canFind = false;
count = 0;
}
}
// if found, we will save current i,j to locate 1st char, then the direction number to indicate the location of rest chars.
if (canFind)
{
res[0] = i;
res[1] = j;
res[2] = k;
return true;
}
}
}
}
}
//nothings foun, return nonexistance
return false;
}

int main()
{
int n = 5;
char** m = new char*[n];
for (int i=0; i<n; i++)
m[n] = new char[n];

// create a test matrix
m[0][0] = 'a'; m[0][1] = 'b'; m[0][2] = 'c'; m[0][3] = 'd'; m[0][4] = 'e';
m[1][0] = 's'; m[1][1] = 'g'; m[1][2] = 'a'; m[1][3] = 's'; m[1][4] = 'g';
m[2][0] = 'r'; m[2][1] = 'l'; m[2][2] = 'q'; m[2][3] = 'w'; m[2][4] = 'd';
m[3][0] = 't'; m[3][1] = 'h'; m[3][2] = 'u'; m[3][3] = 'e'; m[3][4] = 's';
m[4][0] = 'u'; m[4][1] = 'b'; m[4][2] = 'e'; m[4][3] = 't'; m[4][4] = 'd';

//set a test string word
char* word = (char*)"ubettt";
//cout<< word<<endl<<strlen(word)<<endl;
//print the table
for (int i =0; i<n; i++)
{
for (int j = 0; j< n; j++)
{
cout<<m[i][j]<<' ';
}
cout<<endl;
}
//
int* res = new int[3];
bool ot = findWord(m, word, n, res);
if(ot)
cout<<res[0] <<' '<<res[1]<<' '<<res[2]<<endl;
else
cout<<"no result"<<endl;
// the res array gives the location of word by giving first 2 elements as the corrdinates of first char, then direction.
}

- Anonymous July 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cpode

- nameli July 16, 2017 | Flag Reply


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