Epic Systems Interview Question
Java DevelopersCountry: United States
int N = 100;
int[][] G = new int[N][N];
String S;
void findWord(String S)
{
this.S = S;
int ResultR = -1, ResultC = -1;
int DirR,DirC;
for(int Or = 0;Or < N;Or++)
{
for(int Oc = 0;Oc < N ;Oc++)
{
if((int Index = find(G[Or][Oc])) != -1)
{
if( dirFind(Or,Oc,Index,1,1,1) && dirFind(Or,Oc,Index,-1,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 1;
DirC = 1;
break;
}
if( dirFind(Or,Oc,Index,-1,1,1) && dirFind(Or,Oc,Index,1,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = -1;
DirC = 1;
break;
}
if( dirFind(Or,Oc,Index,1,0,1) && dirFind(Or,Oc,Index,-1,0,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 1;
DirC = 0;
break;
}
if( dirFind(Or,Oc,Index,0,1,1) && dirFind(Or,Oc,Index,0,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 0;
DirC = 1;
break;
}
}
}
if(ResultR != -1)
break;
}
for(int i = 0; i < S.Length(); i++)
{
System.PrintLn("[" + ResultR + "," + ResultC + "]");
ResultR += DirR;
ResultC += DirC;
}
}
int find(char c)
{
for(int i = 0; i < S.Length(); i++)
{
if(S[i] == c)
return i;
}
return -1;
}
bool dirFind(int Or, int Oc, int Index, int RowIncr, int ColIncr, int IndexIncr)
{
if(Index == S.Length() - 1 || Index == 0)
return true;
else
{
Or += RowIncr;
Oc += ColIncr;
Index += IndexIncr;
if((Or < N && Oc < N) || (Or >= 0 && Oc >= 0)
dirFind(Or,Oc,I,RowIncr,ColIncr,IndexIncr);
else
return false;
}
}
int N = 100;
int[][] G = new int[N][N];
String S;
void findWord(String S)
{
this.S = S;
int ResultR = -1, ResultC = -1;
int DirR,DirC;
for(int Or = 0;Or < N;Or++)
{
for(int Oc = 0;Oc < N ;Oc++)
{
if((int Index = find(G[Or][Oc])) != -1)
{
if( dirFind(Or,Oc,Index,1,1,1) && dirFind(Or,Oc,Index,-1,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 1;
DirC = 1;
break;
}
if( dirFind(Or,Oc,Index,-1,1,1) && dirFind(Or,Oc,Index,1,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = -1;
DirC = 1;
break;
}
if( dirFind(Or,Oc,Index,1,0,1) && dirFind(Or,Oc,Index,-1,0,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 1;
DirC = 0;
break;
}
if( dirFind(Or,Oc,Index,0,1,1) && dirFind(Or,Oc,Index,0,-1,-1))
{
ResultR = Or - Index;
ResultC = Oc - Index;
DirR = 0;
DirC = 1;
break;
}
}
}
if(ResultR != -1)
break;
}
for(int i = 0; i < S.Length(); i++)
{
System.PrintLn("[" + ResultR + "," + ResultC + "]");
ResultR += DirR;
ResultC += DirC;
}
}
int find(char c)
{
for(int i = 0; i < S.Length(); i++)
{
if(S[i] == c)
return i;
}
return -1;
}
bool dirFind(int Or, int Oc, int Index, int RowIncr, int ColIncr, int IndexIncr)
{
if(Index == S.Length() - 1 || Index == 0)
return true;
else
{
Or += RowIncr;
Oc += ColIncr;
Index += IndexIncr;
if((Or < N && Oc < N) || (Or >= 0 && Oc >= 0)
dirFind(Or,Oc,I,RowIncr,ColIncr,IndexIncr);
else
return false;
}
}
#include<stdio.h>
int main()
{
/* word=mango and grid initialized here */
int i,j,success,done;
for (i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if (grid[i]!='m'&&grid[i]!='a'&&grid[i]!='n'&&grid[i]!='g'&&grid[i]!='0')
continue;
success=checkOccurence(word,grid,i,j);
if (success)
{
printf("Found!\n");
done=1;
break;
}
i=i+(j-success)/n;
j=(j-success)%n;
}
if (done) break;
}
return 0;
}
int checkOccurence(char *word, char grid[][],int i,int j) //method signature isn't rigorous here
{
char c = grid[i][j];
switch(c)
{
case: 'm'
//check on 4 directions. if mango found, return 1, else return -4
case: 'a'
//check on 4 directions. if mango found, return 1, else return -3
//similary for 'n' 'g' 'o' , return -2,-1 and 0 respectively
}
This seems to be a version of finding a sub-string in a set of string but in this case there is a vertical horizontal and such.
Where you could use a rolling hash in order to find the word.
I rushed a little bit but hopefully you get the idea at least from the vertical or horizontal versions.
class WordCoordinate
{
public int StartX {get;set;}
public int StartY {get;set;}
public int EndX {get;set;}
public int EndY {get;set;}
}
public static WordCoordinate FindWord(char[][] grid, string word)
{
WordCoordinate result = null;
List<Func<WordCoordinate, char[][], string>> functions =
new List<Func<WordCoordinate, char[][], string>>()
{
FindWordVertical,
FindWordHorizontal;
FindWordDiagonal1,
FindWordDiagonal2
}
foreach(var func in functions)
{
result = func(grid, word);
if(result != null)
{
break;
}
}
return result;
}
private static long GetHash(IEnumerable<char> chars)
{
long result = 0;
foreach(char c in chars)
{
result += c.GetHashCode();
}
return result;
}
private static WordCoordinate FindwordVertical(char[][] grid, string word)
{
long wordHash = GetHash(word);
for(int i = 0; i < grid.Length; i++)
{
int j = 0;
int runningHash = 0;
for(; j < grid[i].Length ; j++)
{
runningHash += grid[i][j].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[i][j - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[i][j - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = j - word.Length,
StartY = i,
EndX = j,
EndY = i);
}
}
}
}
}
return null;
}
private static WordCoordinate FindwordHorizontal(char[][] grid, string word)
{
long wordHash = GetHash(word);
for(int i = 0; i < grid.Length; i++)
{
int runningHash = 0;
for(int j = 0; j < grid[i].Length ; j++)
{
runningHash += grid[j][i].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[j][i - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[j][i - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = i - word.Length,
StartY = j,
EndX = i,
EndY = j);
}
}
}
}
}
return null;
}
private static WordCoordinate FindWordDiagonal1(char[][] grid, string word)
{
long wordHash = GetHash(word);
for(int i = 0; i < grid.Length; i++)
{
int runningHash = 0;
for(int j = 0; j < grid[0].Length ; j++)
{
runningHash += grid[j+i][j].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[j+i][j - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[j+i][j - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = j+i - word.Length,
StartY = j - word.Length,
EndX = i+j,
EndY = j);
}
}
}
}
}
for(int j = 0; j < grid.Length;j++)
{
int runningHash = 0;
for(int i = 0; i < grid[0].Length ; i++)
{
runningHash += grid[j+i][j].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[j+i][j - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[j+i][j - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = j+i - word.Length,
StartY = j - word.Length,
EndX = i+j,
EndY = j);
}
}
}
}
}
return null;
}
private static WordCoordinate FindWordDiagonal1(char[][] grid, string word)
{
long wordHash = GetHash(word);
for(int i = 0; i < grid.Length; i++)
{
int runningHash = 0;
for(int j = grid[0].Length - 1; j >=0 ; j--)
{
runningHash += grid[j+i][j].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[j+i][j - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[j+i][j - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = j+i - word.Length,
StartY = j - word.Length,
EndX = i+j,
EndY = j);
}
}
}
}
}
for(int j = 0; j < grid.Length;j++)
{
int runningHash = 0;
for(int i = grid[0].Length - 1; i >=0 ; i--)
{
runningHash += grid[j+i][j].GetHashCode();
if(j >= word.Length)
{
runningHash -= grid[j+i][j - word.Length;
if(runningHash == wordHash)
{
bool equal = true;
for(int k = 0; k <= word.Length; k++)
{
if(grid[j+i][j - word.Length + k] != word[k])
{
equal != false;
break;
}
}
if(equal)
{
return new WordCoordinate() {
StartX = j+i - word.Length,
StartY = j - word.Length,
EndX = i+j,
EndY = j);
}
}
}
}
}
return null;
}
I couldn't bother returning all coordinates, so I return only the coordinate where the first occurrence found - if any - starts. Cost is O(N^2*L), with N being the lateral size of the grid and L the length of the string searched.
public static boolean findStringInGrid(char[][] grid, String str, int startX, int startY, int direction) {
int xOffset = 0;
int yOffset = 0;
// Set the offsets according to the direction
switch (direction) {
case 0:
xOffset = -1;
yOffset = -1;
break;
case 1:
yOffset = -1;
break;
case 2:
xOffset = 1;
yOffset = -1;
break;
case 3:
xOffset = 1;
break;
case 4:
xOffset = 1;
yOffset = 1;
break;
case 5:
yOffset = 1;
break;
case 6:
yOffset = 1;
xOffset = -1;
break;
case 7:
xOffset = -1;
break;
default:
return false;
}
// If the end coordinates would be out of the grid, we return false
int endX = startX + (str.length() * xOffset);
int endY = startY + (str.length() * yOffset);
if (endX < 0 || endY < 0 || endY >= grid.length || endX >= grid[endY].length)
return false;
// Check char correspondence in the specified direction
for (int i = 0; i < str.length(); i++) {
if (grid[startX + (i * xOffset)][startY + (i * yOffset)] != str.charAt(i))
return false;
}
return true;
}
public static int[] findStringInGrid(char[][] grid, String str) {
if (grid == null)
return null;
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[x].length; y++) {
for (int k = 0; k < 8; k++) {
// Search the string from cell [x,y] of the grid in each of the 8 possible directions
if (findStringInGrid(grid, str, x, y, k)) {
int[] res = { x, y };
return res;
}
}
}
}
return null;
}
void wordsearch(string sWord,vector<string> v,int x,int y,vector<string> vCoord)
{
if(y < v.size() && x < v[y].length())
{
if(sWord[vCoord.size()] == v[y][x])
{
stringstream ss;
ss << v[y][x];
ss << " (" << x << "," << y << ")";
vCoord.push_back(ss.str());
if(vCoord.size() == sWord.length())
{
for(int i=0;i<vCoord.size();i++)
printf("%s ",vCoord[i].c_str());
vCoord.clear();
}
}else
{
vCoord.clear();
}
wordsearch(sWord,v,x+1,y,vCoord);
wordsearch(sWord,v,x,y+1,vCoord);
wordsearch(sWord,v,x+1,y+1,vCoord);
}
}
public static String findWordInGrid(Character[][] grid,String word)
{
int gridsize = grid.length-1;
if(word.isEmpty())
return null;
if(word.length()-1 > gridsize)
return null;
char[] strarr = word.toCharArray();
String[] start;
for(int i=0;i<gridsize;i++)
{
for(int j=0;j<gridsize;j++)
{
if(grid[i][j] == strarr[0])
{
System.out.println("yippi found first alphabet"+i+" "+j);
ArrayList<String> values = new ArrayList<String>();
values.add(new String(i+" "+j));
checkgrid(grid,strarr,1,-1,0,values);
checkgrid(grid,strarr,1,1,1,values);
checkgrid(grid,strarr,1,1,0,values);
checkgrid(grid,strarr,1,0,1,values);
checkgrid(grid,strarr,1,-1,-1,values);
checkgrid(grid,strarr,1,-1,1,values);
checkgrid(grid,strarr,1 ,1,-1,values);
checkgrid(grid,strarr,1,0,-1,values);
}
}
}
return word;
}
public static void checkgrid(Character[][] grid ,char[] strarr,int strindex,int nexti,int nextj,ArrayList<String> path)
{
int max = grid.length;
int min =0;
for(int m =1;m<strarr.length;m++)
{
String[] s = path.get(path.size()-1).split(" ");
System.out.println("hey this is my input "+path.get(path.size()-1));
int i= Integer.parseInt(s[0])+nexti;
int j= Integer.parseInt(s[1])+nextj;
if(i<min || i>max || j<min || j>max )
{ System.out.println("nope:- out of bounds");
return;
}
System.out.println(strarr[m]+" "+grid[i][j]+ " "+i+ ""+j);
if(strarr[m]==grid[i][j])
{
path.add(i+" "+j);
if(m == strarr.length-1)
{
for(String p:path)
{
System.out.print(p);
}
System.out.println("");
System.out.println("yippi got the answer");
return;
}
}
else
{
System.out.println("Sorry not found hey \n");
return;
}
}
System.out.println("sorry not found") ;
}
public static void main(String[] args)
{
Character[][] arr = new Character[4][4];
arr[0][0] ='a';
arr[0][1] ='c';
arr[0][2] ='e';
arr[0][3] ='f';
arr[1][0] ='b';
arr[1][1] ='b';
arr[1][2] ='c';
arr[1][3] ='m';
arr[2][0] ='d';
arr[2][1] ='a';
arr[2][2] ='c';
arr[2][3] ='v';
arr[3][0] ='l';
arr[3][1] ='d';
arr[3][2] ='s';
arr[3][3] ='q';
findWordInGrid( arr,"abc");
}
import java.util.LinkedList;
import java.util.List;
public class NByNGridWord {
public static void main(String[] args){
char [][]grid =
{{'b','a','d'},
{'y','i','r'},
{'b','m','g'}};
LinkedList<Coordinate> crds = new LinkedList<Coordinate>();
System.out.println("there is a match: "+isThereAMatch(grid,"aim",crds));
for(Coordinate c: crds){
System.out.println("coordinate:("+c.i+","+c.j+")");
}
}
public static boolean isThereAMatch(char[][] grid, String word,LinkedList<Coordinate> crds){
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]==word.charAt(0)){
if(matchesHorizantally(grid,word,i,j,crds)){
return true;
}
if(matchesVertically(grid,word,i,j,crds)){
return true;
}
if(matchesDiagonally(grid,word,i,j,crds)){
return true;
}
}
}
}
return false;
}
public static boolean matchesHorizantally(char[][] grid, String word, int i, int j,LinkedList<Coordinate> crds){
LinkedList<Coordinate> foundCrds = new LinkedList<Coordinate>();
for(int n=0;n<word.length()&&j+n<grid[i].length;n++){
if(grid[i][j+n]!=word.charAt(n)){
break;
}else{
foundCrds.add(new Coordinate(i,j+n));
}
}
//found the word or else check horizontal left direction
if(foundCrds.size()==word.length()){
crds.addAll(foundCrds);
return true;
}else{
foundCrds.clear();
for(int n=0;n<word.length()&&j-n>=0;n++){
if(grid[i][j-n]!=word.charAt(n)){
return false;
}else{
foundCrds.add(new Coordinate(i,j-n));
}
}
}
crds.addAll(foundCrds);
return true;
}
public static boolean matchesVertically(char[][] grid, String word,int i, int j,LinkedList<Coordinate> crds){
LinkedList<Coordinate> foundCrds = new LinkedList<Coordinate>();
for(int n=0;n<word.length()&&i+n<grid.length;n++){
if(grid[i+n][j]!=word.charAt(n)){
break;
}else{
foundCrds.add(new Coordinate(i+n,j));
}
}
//found the word or else check horizontal left direction
if(foundCrds.size()==word.length()){
crds.addAll(foundCrds);
return true;
}else{
foundCrds.clear();
for(int n=0;n<word.length()&&i-n>=0;n++){
if(grid[i-n][j]!=word.charAt(n)){
return false;
}else{
foundCrds.add(new Coordinate(i-n,j));
}
}
}
crds.addAll(foundCrds);
return true;
}
public static boolean matchesDiagonally(char[][] grid, String word,int i,int j,LinkedList<Coordinate> crds){
LinkedList<Coordinate> foundCrds = new LinkedList<Coordinate>();
for(int n=0;n<word.length()&&i+n<grid.length&&j+n<grid[i].length;n++){
if(grid[i+n][j+n]!=word.charAt(n)){
break;
}else{
foundCrds.add(new Coordinate(i+n,j+n));
}
}
//found the word or else check horizontal left direction
if(foundCrds.size()==word.length()){
crds.addAll(foundCrds);
return true;
}else{
foundCrds.clear();
}
for(int n=0;n<word.length()&&i-n>=0&&j+n<grid[i].length;n++){
if(grid[i-n][j+n]!=word.charAt(n)){
break;
}else{
foundCrds.add(new Coordinate(i-n,j+n));
}
}
//found the word or else check horizontal left direction
if(foundCrds.size()==word.length()){
crds.addAll(foundCrds);
return true;
}else{
foundCrds.clear();
}
for(int n=0;n<word.length()&&i+n<grid.length&&j-n>=0;n++){
if(grid[i+n][j-n]!=word.charAt(n)){
break;
}else{
foundCrds.add(new Coordinate(i+n,j-n));
}
}
//found the word or else check horizontal left direction
if(foundCrds.size()==word.length()){
crds.addAll(foundCrds);
return true;
}else{
foundCrds.clear();
}
for(int n=0;n<word.length()&&i-n>=0&&j-n>=0;n++){
if(grid[i-n][j-n]!=word.charAt(n)){
return false;
}else{
foundCrds.add(new Coordinate(i-n,j-n));
}
}
crds.addAll(foundCrds);
return true;
}
public static class Coordinate{
public int i;
public int j;
public Coordinate(int i, int j){
this.i = i;
this.j = j;
}
}
}
package Interview;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] a = new char[3][3];
char[] c = {'C','A','T'};
a[0] = c;
char[] b = {'O','P','T'};
a[1] = b;
char[] d = {'W','S','D'};
a[2] = d;
for(int i=0;i<3;i++)
System.out.println(new String(a[i]));
boolean flag =false;
String input ="";
char[] v=new char[3];
String h="";
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
v[j] = a[j][i];
}
h = new String(a[i]);
if(h.equals(input)){
System.out.println(i+",0\t"+i+",1\t"+i+",2\t");
flag =true;
break;
}
if(new String(v).equals(input)){
System.out.println("0,"+i+"\t1,"+i+"\t2,"+i);
flag =true;
break;
}
}
}
}
package Interview;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] a = new char[3][3];
char[] c = {'C','A','T'};
a[0] = c;
char[] b = {'O','P','T'};
a[1] = b;
char[] d = {'W','S','D'};
a[2] = d;
for(int i=0;i<3;i++)
System.out.println(new String(a[i]));
boolean flag =false;
String input ="";
char[] v=new char[3];
String h="";
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
v[j] = a[j][i];
}
h = new String(a[i]);
if(h.equals(input)){
System.out.println(i+",0\t"+i+",1\t"+i+",2\t");
flag =true;
break;
}
if(new String(v).equals(input)){
System.out.println("0,"+i+"\t1,"+i+"\t2,"+i);
flag =true;
break;
}
}
}
}
Complexity: L*N*N
- Anonymous April 16, 2015L = Length of string
Assumption Words Only from right to left OR top to bottom Or Mixture for diagonals