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)
				list = new LinkedList<Index>();
			list.add(new Index(y,x));
			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;
		}
	}

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

Can any one give the algorithm???

- ps.sarath21 August 05, 2015 | 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