Notfamous Interview Question for Developer Program Engineers


Country: United States
Interview Type: Written Test




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

Well looks like chinese chess horse move the same way as european chess horse, right?
Simple solution here is to find end with BFS and return backward path.
Here is my implementation. Memory complexity is O(n) and time complexity is O(n^2), where n = width*height

import java.util.List;
import java.util.LinkedList;

class ChessHorseMoves {
	
	static class ChessPoint {
		public final int x;
		public final int y;
		
		public ChessPoint (int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	private final int width;
	private final int height;
	
	private static final ChessPoint[] moves = {new ChessPoint(-2, -1), 
												new ChessPoint(-2, +1), 
												new ChessPoint(-1, -2), 
												new ChessPoint(-1, +2), 
												new ChessPoint(+1, -2), 
												new ChessPoint(+1, +2), 
												new ChessPoint(+2, -1), 
												new ChessPoint(+2, +1)};
						
	ChessHorseMoves (int width, int height) {
		this.width = width;
		this.height = height;
	}
	
	private boolean checkPoint (ChessPoint p) {
		if (p.x < 0 || p.x >= this.width || p.y < 0 || p.y >= this.height)
			return false;
		return true;
	}
	
	public List <ChessPoint> findMoves (ChessPoint start, ChessPoint end) {
		if (!checkPoint (start) || !checkPoint (end))
			throw new RuntimeException ("Out of desk");
		
		LinkedList <ChessPoint> path = new LinkedList <ChessPoint> ();
		if (start.x == end.x && start.y == end.y)
			return path;
		
		ChessPoint[][] pathMatrix = new ChessPoint[width][height];
		pathMatrix [start.x][start.y] = null;
		
		LinkedList <ChessPoint> queue = new LinkedList <ChessPoint> ();
		queue.add (start);
		
		while (!queue.isEmpty()) { // bfs
			ChessPoint curr = queue.poll();
				
			for (int i = 0; i < moves.length; i++) { // add all possible moves to processing queue	
				ChessPoint p = new ChessPoint (curr.x + moves[i].x, curr.y + moves[i].y);
				
				if (!checkPoint (p) || 
						(p.x == start.x && p.y == start.y) 
						|| pathMatrix [p.x][p.y] != null)
					continue;
					
				pathMatrix [p.x][p.y] = curr;
				
				if (p.x == end.x && p.y == end.y) { // end position found
					while (p != null) {
						path.addFirst (p);
						p = pathMatrix [p.x][p.y];
					}
					return path;
				}
				queue.add (p);
			}
		}
		
		throw new RuntimeException ("Path not found");
		
	}
	
	public static void main (String[] args) {
		ChessHorseMoves chm = new ChessHorseMoves (8, 8);
		ChessPoint start = new ChessPoint (0, 0);
		ChessPoint end = new ChessPoint (5, 4);
		
		List <ChessPoint> positions = chm.findMoves (start, end);
		for (ChessPoint position : positions)
			System.out.println (position.x + ":" + position.y);
	}
}

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

Oh, I'm sorry. Time complexity should be O(n) here, because we have fixed number of moves (and so fixed number of edges per vertex for moves graph)

- Anonymous November 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple BFS should be able to solve this reasonably fast.

public static ArrayList<int[]> getMoves(int[] start, int[] end){
	//first eliminate bad input conditions
	if(start == null || end == null){
		throw new NullPointerException();
	}
	if(start.length != 2 || start[0] < 0 || start[0] > 7 start[1] < 0 || start[1] > 7 || end.length != 2 ||
			end[0] < 0 || end[0] > 7 || end[1] < 0 || end[1] > 7){
		throw new IllegalArgumentException();
	}

	Worker worker = new Worker();
	return worker.execute(start, end);
}

//This class does all the BFS work
static class Worker{
	//true if the particular space has already been exposed as a viable search
	boolean[][] exposed;

	Worker(){
		this.exposed = new boolean[8][8];
	}

	//do the actual search.  Searches backwards so the results don't have to be reversed
	ArrayList<int[]> execute(int[] start, int[] end){
		//setup a search queue
		exposed[end[0]][end[1]] = true;
		Queue<Move> movesToExplore = new Queue<Move>();
		movesToExplore.add(new Move(end[0], end[1], null));
		Move dest = null;
		//do the search
		while(!movesToExplore.isEmpty()){
			Move move = movesToExplore.poll();
			for(Move nextMove : getNextMoves(move)){
				if(nextMove.pos[0] == start[0] && nextMove.pos[1] == start[1]){
					dest = nextMove;
					break;
				}
			}
		}
		//since moves store the path backwards, reverse it
		ArrayList<int[]> results = new ArrayList<int[]>();
		while(dest != null){
			results.add(dest.pos);
			dest = dest.lastMove;
		}
		return results;
	}

	//get all possible un exposed moves from a given move
	ArrayList<Move> getNextMoves(Move move){
		int x = move.pos[0];
		int y = move.pos[1];
		ArrayList<Move> results = new ArrayList<Move>();
		//if can move left
		if(x > 1){
			//if can move down
			if(y > 0)
				results.add(new Move(x -2, y -1, move));
			//if can move up
			if(y < 7){
				results.add(new Move(x-2, y+1, move));
		}
		//if can move up
		if(y < 6){
			//if can move left
			if(x > 0)
				results.add(new Move(x-1, y+2, move));
			//if can move right
			if(x < 7)
				results.add(new Move(x+1, y+2, move));
		}
		//if can move right
		if(x < 6){
			//if can move up
			if(y < 7)
				results.add(new Move(x+2, y+1, move));
			//if can move down
			if(y > 0
				results.add(new Move(x+2, y-1, move));
		}
		//if can move down
		if(y > 1){
			//if can move right
			if(x < 7){
				results.add(new Move(x+1, y-2, move));
			//if can move left
			if( x > 0)
				results.add(new Move(x-1, y-2, move));
		}
		ArrayList<Move> return = new ArrayList<Move>();
		for(Move : results){
			if(!exposed[move.pos[0]][move.pos[1]]){
				exposed[move.pos[0]][move.pos[1]] = true;
				return.add(move);
			}
		}
		return return;
	}
}

//possible moves
static class Move{
	int[] pos;
	Move lastMove;

	Move(int x, int y, Move last){
		pos = new int[]{x, y};
		lastMove = last;
	}
}

- zortlord December 01, 2014 | 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