Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Nice solution, complexity O(V+E).
V = N
E = 8N
far better than recursive algo which takes exponential time.
This pseudocode is for the case of a board of -infinity to + infinity
it also works for n>2 except for the corner cases (which need additional conditions)
Requirement - board origin = 0,0
int hops;
int quotient = (abs(p-x) + abs(q-y))/3;
int remainder = (abs(p-x) + abs(q-y))%3;
int adjustment = 0
if (remainder == 1) then adjustment = 3;
else if (remainder ==2) then adjustment = 2;
hops = quotient + adjustment;
-- validated the above with http :// tacticstime . com/wp-content/uploads/2011/09/chess_knight_all.png
-- There seems to be some cases when x=p or y=q that this does not give the least hops (eg. (x,y)=(0,0) and (p,q) = (4,0), so some additional conditions needed there as well.
The A* Algorithm would work here, I think. For each of the squares you can reach from the start position, get the linear distance to the goal and add 1. Select the square where this value is the smallest and repeat, adding 2 instead of 1. The function for A* is g(x)+h(x), where g(x) is a cost function (here, merely a number of moves) and h(x) is a heuristic function (we decided on linear distance to the goal) for a square x.
1) Build a graph of (NxN) vertices that there exist an edge (v->w) if the knight can move from v to w. The maximum order of a vertices is 8 so the maximum number of edge is 8xNxN.
- LinhHA05 October 08, 2013We perform the BFS from the source to find
- If the destination is reachable from the source
- if there're a path, then BFS give the minimum number of hops
Node : there're no need to build the graph explicitly we only want to do the BFS on the implicit graph.
2. I believe for infinite chess board all the positions are reachable so
- the solution is not extendable if the destination is unreachable from the source
- Otherwise, the solution on the infinite chess board is at least as good as NxN that gives us the upper bound for the search on the infinite chess board. Again we can rerun the BFS with the bound from the previous step to check if we can find a better solution.