## zoho question

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

Using recursion, you can keep track of the previous direction and compare it to the next direction.

``````private static enum direction { BEGIN, END, UL, U, UR, L, R, LL, D, LR, UNKNOWN }

private static direction direction(Index me, Index to) {
if (me==null)
return direction.BEGIN;

int x = to.x - me.x;
int y = to.y - me.y;
if        (x==-1 && y==-1) {
return direction.UL;
} else if (x==0  && y==-1) {
return direction.U;
} else if (x==1  && y==-1) {
return direction.UR;
} else if (x==-1 && y==0) {
return direction.L;
} else if (x==1  && y==0) {
return direction.R;
} else if (x==-1 && y==1) {
return direction.LL;
} else if (x==0  && y==1) {
return direction.D;
} else if (x==1  && y==1) {
return direction.LR;
}
return direction.UNKNOWN;
}

private static direction find(	Index[] indices, Map<Character,List<Index>> map, String find,
int lastIdx, Index lastIndex, direction lastDir) {
char c = find.charAt(lastIdx);
List<Index> list = map.get(c);
if (list==null)
return direction.UNKNOWN;
for (Index index : list) {
direction dir = direction(lastIndex,index);
if ((dir==direction.BEGIN) ||
(lastDir==direction.BEGIN && dir!=direction.UNKNOWN) ||
(dir!=direction.UNKNOWN && lastDir==dir))
{
if (dir==direction.BEGIN)
indices[0] = index;
int idx = lastIdx+1;
if (idx==find.length()) {
indices[1] = index;
return direction.END;
}
dir = find(indices, map, find, idx, index, dir);
if (dir==direction.END)
return dir;
}
}
return direction.UNKNOWN;
}

private static Index[] find(Map<Character,List<Index>> map, String find, int idx) {
Index[] indices = new Index[2];
find(indices, map, find, 0, null, direction.UNKNOWN);
return indices;
}

private static Index[] solve(String string, int dim, String find) {
Map<Character,List<Index>> map = new HashMap<Character,List<Index>>();
char[][] matrix = new char[dim][dim];
int y = 0;
int x = 0;
for (int i=0; i<string.length(); i++) {
char c = string.charAt(i);
List<Index> list = map.get(c);
if (list==null)
map.put(c, list);
matrix[y][x++] = c;
if (x==dim) {
y++;
x=0;
}
}
return find(map,find,0);
}

private static final class Index {
private int x;
private int y;
private Index(int y, int x) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "<"+y+", "+x+">";
}

@Override
public boolean equals(Object obj) {
if (!(obj instanceof Index))
return false;

Index idx = (Index)obj;
if (this.x==idx.x && this.y==idx.y)
return true;
return false;
}
}``````

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

Can any one give the algorithm???

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.

### 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.