## Interview Question

Country: India

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

Looks like a perfect candidate for BFS:

``````#include <queue>
#include <vector>

#include "gtest/gtest.h"

struct Position {
int x;
int y;

};
Position operator+(const Position &p1, const Position &p2) {
return Position{ p1.x+p2.x, p1.y+p2.y };
}
bool operator==(const Position &p1, const Position &p2) {
return p1.x==p2.x && p1.y==p2.y ;
}

template<int N>
int knightReachability(Position src, Position dst) {
if(src == dst)
return 0;

// Keep track of which cell has been visited
bool visited[N][N]{};

// Keep on the stack the next Positions to visit and the count for each
std::queue<std::pair<Position, int>> nextToCheck;

nextToCheck.push({src, 0});

std::vector<Position> knightMoves = {
{ 1, 2 }, { 2, 1 },
{ 2, -1 }, { 1, -2 },
{ -1, -2 }, { -2, -1 },
{ -2, 1}, { -1, 2 }
};

auto isValidPos = [] (const Position &pos) -> bool {
return pos.x>0 && pos.y>0 && pos.x<N && pos.y<N;
};

while(!nextToCheck.empty()) {
Position currentPos;
int currentCount;
std::tie(currentPos, currentCount) = nextToCheck.front();
nextToCheck.pop();
visited[currentPos.y][currentPos.x] = true;
for(const auto &move : knightMoves) {
Position newPos = move + currentPos;
if(newPos == dst)
return currentCount+1;
if(!visited[newPos.y][newPos.x] && isValidPos(newPos)) {
nextToCheck.push({newPos,  currentCount+1});
}
}
}
// Should not be reached
assert(0 && "The impossible happened !");
return 0;
};

TEST(Chess, knightReachability) {
EXPECT_EQ(0, knightReachability<8>({0,0}, {0,0}));
EXPECT_EQ(1, knightReachability<8>({0,0}, {2,1}));
EXPECT_EQ(2, knightReachability<8>({0,0}, {4,2}));
EXPECT_EQ(6, knightReachability<8>({0,0}, {7,7}));
EXPECT_EQ(6, knightReachability<8>({7,7}, {0,0}));
EXPECT_EQ(2, knightReachability<8>({3,4}, {4,3}));
}``````

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

``````#include<iostream>
#include<queue>
#include<vector>
#include<climits>

#define MIN 0
#define MAX 7

using namespace std;

class Position
{
public:
int x;
int y;

Position()
{}

Position(int f, int s)
{
x = f;
y = s;
}

Position operator+(const Position &incr)
{
Position new_pos;
new_pos.x = this->x+incr.x;
new_pos.y = this->y+incr.y;
return new_pos;
}

bool operator==(const Position &dest)
{
if(this->x == dest.x && this->y == dest.y)
return true;
return false;
}

bool is_valid()
{
if(this->x < MIN || this->y < MIN || this->x > MAX || this->y > MAX)
return false;
return true;
}
};
struct classcomp
{
bool operator()(const Position &p1, const Position &p2)
{
if(p1.x == p2.x && p1.y == p2.y)
return 0;
return p1.x<p2.x;
}
};

int find_closest_path(Position knight, Position king)
{
if(!knight.is_valid() || !king.is_valid())
return INT_MAX;
if(knight == king)
return 0;
vector<pair<int, int> >moves(8);
moves[0].first = 2;
moves[0].second = -1;
moves[1].first = 2;
moves[1].second = 1;
moves[2].first = 1;
moves[2].second = -2;
moves[3].first = 1;
moves[3].second = 2;
moves[4].first = -1;
moves[4].second = 2;
moves[5].first = -1;
moves[5].second = -2;
moves[6].first = -2;
moves[6].second = 1;
moves[7].first = -2;
moves[7].second = -1;

queue<Position>Q;
bool visited[MAX+1][MAX+1] = {false};
Q.push(knight);
int curr_level = 1;
int next_level = 0;
int no_of_steps = 1;
while(!Q.empty())
{
Position top = Q.front();
for(int i=0; i<moves.size(); i++)
{
Position next = Position(moves[i].first, moves[i].second);
Position curr = top + next;
if(!curr.is_valid())
continue;
if(curr == king)
return no_of_steps;
if(visited[curr.x][curr.y] == false)
visited[curr.x][curr.y] = true;
else
continue;
Q.push(curr);
next_level++;
}
Q.pop();
curr_level--;
if(curr_level == 0)
{
no_of_steps++;
curr_level = next_level;
next_level = 0;
}
}
return -1;
}

int main()
{
Position knight(0, 0);
Position king(7,7);

int no_of_moves = find_closest_path(knight, king);
cout<<"no of moves required are - "<<no_of_moves<<endl;
return 0;
}``````

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

Good one :)

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

Why are you all mad to write code before explaining logic. Code is junk. Any college 1st or 2nd yr guy can do. Give out logic first.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

pseudocode:

``````bt(current, target, num_moves, min_so_far)
{
if(current==target)
{
if(num_moves<min_so_far)
min_so_far = num_moves
return min_so_far
}

if(num_moves>min_so_far)
return min_so_far

candidates = get_candidates(current)

foreach(candidate in candidates)
{
min_so_far = bt(candidate, target, num_moves+1, min_so_far)
}
return min_so_far
}``````

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

What would be the initial value for min_so_far ?
Moreover there will be multiple redundant computations...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````class KnightKing {
boolean[][] visited = new boolean[8][8];
int min = -1;

public int catchTheKing (int knX, int knY, int kgX, int kgY) {
min = -1;
catchTheKing (knX, knY, kgX, kgY, 0);
return min;
}

private void catchTheKing (int knX, int knY, int kgX, int kgY, int len) {
if (visited[knX][knY]) return;
if (knX == kgX && knY == kgY) {
if (min == -1 || min > len) min = len;
return;
}
visited[knX][knY] = true;
if (knX > 0 && knY > 1) catchTheKing(knX-1, knY-2, kgX, kgY, len+1);
// repeat the above for other moves as well
visited[knX][knY] = false;
}``````

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

I don't understand how it can work ? There is only one move considered (-1,-2)... There is no check for out of bound either. Try to run with: 0,0,7,7 for instance.

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

"There is only one move considered (-1,-2)... "

Look carefully, there is a comment saying:
// repeat the above for other moves as well

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.

### 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.