Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
May be some one has better idea, just thinking out loud,
This can be done using dynamic programming, set totalMinSteps to In32.maxValue
a) a knight has 8 directions to go from any position,
b) we try out 8 ways till we hit destination point,
c) once we get there we can totalMinSteps = k, at any point if we hit more than steps, we can simply to In32.MaxValue from the initial location to terminate the search
Space complexity is O( 8 * 8), where each location will have total number of steps to reach destination, Most locations will have Int32.MaxValue indicating that some path already found a minimum possible way to get to destination
package com.home.careercup;
/**
* High performance chess apps use bit operations for determining knight attacks.
* Below is sample code snipped from some chess programming material. It demonstrates
* a flood fill algo for determining knight attacks ( and the distance between source
* and destination ). This is similar to bfs (but very fast with bit operations)
* It is possible to find the shortest paths for knights from source to dest by using
* lookup tables.
* There are 64 values of source. For each source the shortest path to each of the
* other target values (64) cam be precomputed offline and fed into code.
*/
public class KnightDistance {
public static void main(String[] args) {
// 0, left bottom corner of chess board
// 35, D5
KnightDistance kd = new KnightDistance();
int d= kd.distance(0, 35);
System.out.println(d); // prints 3
}
// flood fill all attack position for all knights on board
// some bit magic
long attacks(long bb) {
long l1 = (bb >> 1) & 0x7f7f7f7f7f7f7f7fL;
long l2 = (bb >> 2) & 0x3f3f3f3f3f3f3f3fL;
long r1 = (bb << 1) & 0xfefefefefefefefeL;
long r2 = (bb << 2) & 0xfcfcfcfcfcfcfcfcL;
long h1 = l1 | r1;
long h2 = l2 | r2;
return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}
int distance(long b1 /* source */, long b2 /* target */) {
int d = 0;
while ((b1 & b2) == 0) {
b1 = attacks(b1);
d++; // hop count increment
}
return d;
}
// utility method to translate from human readable board position
// to bit position on chess board
int findHops(int a, int b) {
return distance(1L << a, 1L << b);
}
}
BFS (bidirectional BFS for efficiency) should work.
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Cell {
public:
Cell(int r, int c)
{
r_ = r;
c_ = c;
}
bool operator==(Cell const &other) const
{
return r_ == other.r_ &&
c_ == other.c_;
}
bool Valid() const
{
return r_ >= 0 &&
c_ >= 0 &&
r_ < 8 &&
c_ < 8;
}
int r_, c_;
};
int MinMovesCount(Cell source, Cell target)
{
vector<vector<bool>> m = vector<vector<bool>>(8, vector<bool>(8, false));
vector<pair<int, int>> moves = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
queue<Cell> q1, q2;
queue<Cell> *parents = &q1;
queue<Cell> *children = &q2;
parents->push(source);
int moves_count = 0;
while(!parents->empty()) {
while(!parents->empty()) {
Cell c = parents->front();
parents->pop();
if (c.Valid() &&
!m[c.r_][c.c_])
{
m[c.r_][c.c_] = true;
if (c == target) {
return moves_count;
}
for (auto move : moves) {
children->push(Cell(c.r_ + move.first, c.c_ + move.second));
}
}
}
swap(parents, children);
++moves_count;
}
return -1;
}
int main()
{
for (int r = 0; r < 8; ++r) {
for (int c = 0; c < 8; ++c) {
for (int r2 = 0; r2 < 8; ++r2) {
for (int c2 = 0; c2 < 8; ++c2) {
cout << r << ", " << c << ", " << r2 << ", " << c2 << ", " << MinMovesCount(Cell(r, c), Cell(r2, c2)) << "\n";
}
}
}
}
return 0;
}
- Makarand August 31, 2017