Notfamous Interview Question
Developer Program EngineersCountry: United States
Interview Type: Written Test
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;
}
}
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
- Anonymous November 30, 2014