Amazon Interview Question Software Engineer / Developers
Country: United States
Haha.
>> he rest is just... coding.
Don't take things in so light vein mate! People are here to do serious coding not just coding. BTW, BFS on a graph searches for a node and returns whether or not the given node is present.
The question that is being asked is to find a path from a source position to destination. You'd probably need to give an algorithm that prints a sequence of coordinates of locations on the chessboard from src to dest.
Look, you starts your BFS from the "source", and terminate it at the "target", the path is the one you want, and it is also guaranteed to be the shortest path... right? To generate the path at least you could copy/paste the "predecessor tree" idea from Introduction to Algorithm book, or find your own clever ways. Also you can use any data structure to store the position on the board, ranging from int[2] to class() { public int x; public int y; } to the ones using getter/setters, to simply (x,y) in Python --- your choice :)
I don't think an interviewer would like answers like:
>> To generate the path at least you could copy/paste the "predecessor tree" idea from Introduction to Algorithm book, or find your own clever ways.
Haha you are right :) Ok, fine, here is my first draft of the code in Python...
def generatePath(source, target, n): # source, target = (i,j); n=size
travelled = { target: target} # { child : parent }
bufferQueue = [target] # backward search
while bufferQueue:
underProcessing = bufferQueue.pop()
if underProcessing == source:
return travelled
for eachNeighbor in getNeighbors(underProcessing, n):
if travelled.has_key(eachNeighbor):
continue
else:
travelled[eachNeighbor] = underProcessing
bufferQueue.append(eachNeighbor)
return {} # no path
def getNeighbors(location, n):
neighbors = []
i, j = location
for k, l in ( (i+2,j+1), (i+2,j-1), (i+1,j+2), (i+1,j-2), (i-1,j+2), (i-1,j-2), (i-2,j+1), (i-2,j-1) ):
if k>=0 and k<n and l>=0 and l<n:
neighbors.append( (k, l) )
return neighbors
def printPath(source, paths):
if paths:
while paths.has_key(source):
print(source)
if source == paths[source]:
return
else:
print("-->")
source = paths[source]
if __name__ == '__main__':
# test
source = (1, 2)
target = (2, 5)
printPath( source, generatePath(source, target, 8))
Output (from (1,2) to (2,5) in a 8x8 board):
(1, 2)
-->
(0, 4)
-->
(2, 5)
Here given Brute force algorithm.... Done a long time back... So sorry for so many switches... Given here is solution for knights tour prob....
This will run for nearly one hour to generate the 1st solution...
#include <stdio.h>
#include <conio.h>
#define FREE 1
#define NOT_FREE 0
#define NOT_EXIST 0
#define EXIST 1
int nok = 0; // number of knights placed!!!
int pos = 0;
int knight[8][8] = {0};
void fill() {
//gotoxy(18,6);
//printf("K");
int ctr1, ctr2;
int c,r;
for( ctr1 = 0 ; ctr1 < 8 ; ctr1++ )
for( ctr2 = 0 ; ctr2 < 8 ; ctr2++ ) {
if( knight[ ctr1 ][ ctr2 ] != 0 ) {
c = 18 + ( ctr2 * 6 );
r = 6 + ( ctr1 * 2 );
gotoxy(c,r);
printf("%d", knight[ ctr1 ][ ctr2 ]);
}
}
}
int isitfree( int row, int col ) {
if( knight[ row ][ col ] != 0 ) {
return NOT_FREE;
}
else {
return FREE;
}
}
int doesitexist( int row, int col ) {
if( row < 0 || col < 0 || row > 7 || col > 7 )
return NOT_EXIST;
else
return EXIST;
}
int whatsnext( int row, int col, int comb) {
int r,c;
int ctr;
for( ctr = comb ; ctr < 8 ; ctr++ ) {
switch( ctr ) {
case 0: r = row - 2;
c = col - 1;
break;
case 1: r = row - 2;
c = col + 1;
break;
case 2: r = row - 1;
c = col - 2;
break;
case 3: r = row - 1;
c = col + 2;
break;
case 4: r = row + 1;
c = col - 2;
break;
case 5: r = row + 1;
c = col + 2;
break;
case 6: r = row + 2;
c = col - 1;
break;
case 7: r = row + 2;
c = col + 1;
break;
}
if( doesitexist(r,c) == EXIST ) {
if( isitfree( r , c ) == FREE )
return ctr;
}
}
return -1;
}
void place( int row, int col ) {
knight[row][col] = ++nok;
gotoxy( 18 + ( col * 6 ), 6 + ( row * 2 ) );
printf(" ");
gotoxy( 18 + ( col * 6 ), 6 + ( row * 2 ) );
printf("%d", knight[ row ][ col ] );
}
void whereis( int num, int *row, int *col ) {
int ctr1, ctr2;
for( ctr1 = 0 ; ctr1 < 8 ; ctr1++ ) {
for( ctr2 = 0 ; ctr2 < 8 ; ctr2++ ) {
if( knight[ ctr1 ][ ctr2 ] == num ) {
*row = ctr1;
*col = ctr2;
}
}
}
}
int whichcomb( int r, int c, int row, int col ) {
if( r == row - 2 && c == col - 1 )
return 0;
else if( r == row - 2 && c == col + 1 )
return 1;
else if( r == row - 1 && c == col - 2 )
return 2;
else if( r == row - 1 && c == col + 2 )
return 3;
else if( r == row + 1 && c == col - 2 )
return 4;
else if( r == row + 1 && c == col + 2 )
return 5;
else if( r == row + 2 && c == col - 1 )
return 6;
else if( r == row + 2 && c == col + 1 )
return 7;
return -1;
}
void play() {
int row = 0, col = 0;
unsigned long int ctr = 0;
int where;
int r,c;
int comb;
gotoxy(55,24);
printf("Counter : ");
if( isitfree( row, col ) == FREE ) {
place( row, col );
}
while( nok < 65 ) {
ctr++;
gotoxy( 66, 24 );
printf("%lu", ctr );
//
where = whatsnext(row, col,0);
while( where == -1 ) {
r = row;
c = col;
whereis( knight[ row ][ col ] - 1 , &row, &col );
comb = whichcomb(r,c,row,col);
comb++;
knight[ r ][ c ] = 0;
gotoxy( 18 + ( c * 6), 6 + ( r * 2 ));
printf(" ");
nok--;
where = whatsnext(row,col,comb);
}
switch( where ) {
case 0: r = row - 2;
c = col - 1;
break;
case 1: r = row - 2;
c = col + 1;
break;
case 2: r = row - 1;
c = col - 2;
break;
case 3: r = row - 1;
c = col + 2;
break;
case 4: r = row + 1;
c = col - 2;
break;
case 5: r = row + 1;
c = col + 2;
break;
case 6: r = row + 2;
c = col - 1;
break;
case 7: r = row + 2;
c = col + 1;
break;
}
place( r , c );
if( nok == 64 ) {
getch();
}
row = r;
col = c;
}
}
void main() {
clrscr();
play();
getch();
}
BFS won't solve the problem.
There is a simple recursive solution to it...
A knight can move in one of the possible 8 ways from its current location:
i+2, j+1
i+2, j-1
i-2, j+1
i-2, j-1
i+1, j+2
i-1, j+2
i+1, j-2
i-1, j-2
After checking the bounds of the chess board for every move, do a recursive search on each of the 8 directions. As you make every recursive call, do some book keeping to store the points. In this way, once you reach your target, you have a list of points that led you to this point.
use BFS. there are max 8 point to the starting point with MinStep 1.(considering as level 1) from these 8 point, each point will have max 8 point with MinStep 2 to the starting point.(level 2). if the level 2 point hit the level 1 point, skip. and out of boundary skip too. use this method to fill up all 8x8 point. if it hit the destination point during this process, will return the MinStep at that level.
in C++, using a queue to track each level point, start with starting point,
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
bool validmove(int i,int j,int move,int *ni,int *nj){
if(move==0){
*ni=i+1;
*nj=j+2;
}
else if(move==1){
*ni=i+1;
*nj=j-2;
}
else if(move==2){
*ni=i-1;
*nj=j+2;
}
else if(move==3){
*ni=i-1;
*nj=j-2;
}
else if(move==4){
*ni=i+2;
*nj=j+1;
}
else if(move==5){
*ni=i+2;
*nj=j-1;
}
else if(move==6){
*ni=i-2;
*nj=j+1;
}
else if(move==7){
*ni=i-2;
*nj=j-1;
}
else return false;
if((*ni>=0)&&(*ni<8)&&(*nj>=0)&&(*nj<8))
return true;
else return false;
}
int knightMinStepPath(int sx,int sy,int dx,int dy){
int MinStepPath[8][8];
int nx,ny;
bool flag;
int i,j,cnt,ret=INT32_MAX,MinStep,move;
vector<int> ps;
vector<int> dp;
queue<vector<int>> neighbor;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
MinStepPath[i][j]=INT32_MAX;
}
}
MinStepPath[sx][sy]=0;
if((sx==dx)&&(sy=dy)) {
return 0;
}
ps.push_back(sx);
ps.push_back(sy);
dp.push_back(dx);
dp.push_back(dy);
neighbor.push(ps);
MinStep=0;
while(!neighbor.empty()){
cnt=(int)neighbor.size();
MinStep++;
while(cnt){
ps=neighbor.front();
for(move=0;move<8;move++){
flag=validmove(ps[0],ps[1],move,&nx,&ny);
if(flag){
dp[0]=nx;
dp[1]=ny;
if(MinStepPath[nx][ny]>MinStep){
neighbor.push(dp);
MinStepPath[nx][ny]=MinStep;
if((dx==nx)&&(dy==ny)) {
ret=MinStep;
}
}
}
}
neighbor.pop();
cnt--;
}
}
ps.clear();
dp.clear();
return ret;
}
The path apparently need not be unique, is the question asking for a minimum step path? There are algorithms that do a knight's tour so that every square on the board is visited at least once. Any such algorithm can be employed to reach the destination.
en.wikipedia.org/wiki/Knight's_tour
treat black as no path and white as a path, then the neighbor of a node i,j are:
- Anonymous July 18, 2013i+1,j
i-1,j
i,j+1
i,j-1
given the way a knight is allowed to move around a chess board, apply the BFS to find the shortest path.