## Facebook Interview Question

SDE-2s**Country:**India

Nice breaking the problem down. But one line confused me, what do you mean "We can use dynamic programming to find the best path"? At the current point of your solution, you already have the optimal path from BFS's on every single pair of islands + permutations of the pairs to find the shortest path. Maybe it was a mis-type or something?

No, I intended that way. If we consider all permutations of the specific islands like

start -> island_1 -> island_2 -> island_3

start -> island_1 -> island_3 -> island_2

start -> island_2 -> island_1 -> island_3

start -> island_2 -> island_3 -> island_2

start -> island_3 -> island_1 -> island_2

start -> island_3 -> island_2 -> island_1

to compute the optimal cost, this will take O(S! * S) because there are S! permutations and we take O(S) time to compute the cost of each permutation (path), using the previously computed distances between islands.

However, we can use the dynamic programming approach i mentioned above to compute the optimal cost in O(S^2 * 2^S) which is much better than the factorial time complexity.

You can code assuming that n can be at most 20 and number of special islands are not more than 10.

I think Gedo Mazo might be right....

He is saying use grid's geometric properties instead of viewing this problem in isolation as an abstract graph.

The example that Miguel posted seems misleading, since on a grid it would look something like

this:

###############

E_ _D_ _A_B_ _C

###############

so the distances are from A { B=1, D=2, C=3, E=4}

Select B.

from B { D=3, C=2, E=5}

Select C.

from C {D=5, E=7}

Select D

From D { E=2}

select E

total : 1+2+5+2 = 10.

Maybe the question poster should add if edges between the given islands need to be calculated or are already provided ?

I think this problem is not asked by FB, but it is asked in Illuminati Hiring Challenge that ended today on HackerRank.com. Only the words have been changed, problem seems to be exactly what was asked there.

oh, it's so bad that people post questions here to cheat :S

at least i didn't post the code, but it was a huge spoiler that way

Hi, i implemented this algo...i dont print NOT POSSIBLE TO DELIVER ALL...but the rest should be there...

please give me some feedback.

```
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <stack>
using namespace std;
const int grid_x_max = 6;
const int grid_y_max = 6;
array<array<int, grid_y_max+1>, grid_y_max+1> A;
class pos
{
public:
int x;
int y;
pos(): x(0), y(0) {}
pos(int x_, int y_): x(x_), y(y_) {}
pos &operator=(const pos &rhs) {
x = rhs.x;
y = rhs.y;
return *this;
}
bool operator==(const pos &rhs) {
return x == rhs.x && y == rhs.y;
}
bool operator!=(const pos &rhs) {
return x != rhs.x && y != rhs.y;
}
};
void init_grid(vector<pos> &dang_islands) {
for(int x = 0; x <= grid_x_max; x++) {
for(int y = 0; y <= grid_y_max; y++) {
bool allowed_pos = true;
for(int i = 0; i < dang_islands.size(); i++) {
if(x == dang_islands[i].x && y == dang_islands[i].y) {
allowed_pos = false;
break;
}
}
if(allowed_pos) {
A[x][y] = 1;
}
else {
A[x][y] = 0;
}
}
}
}
bool is_valid_coord(pos ¤t_pos) {
if((A[current_pos.x][current_pos.y] == 1) && (current_pos.x >= 0 && current_pos.x <= grid_x_max) && (current_pos.y >= 0 && current_pos.y <= grid_y_max)) {
return true;
}
return false;
}
float calc_heuristic(pos &next_pos, vector<pos> &spec_islands) {
set<float> heuristic_dist;
for(int i = 0; i < spec_islands.size(); i++) {
float dist = sqrt(pow(next_pos.x - spec_islands[i].x, 2) + pow(next_pos.y - spec_islands[i].y, 2));
heuristic_dist.insert(dist);
}
return *heuristic_dist.begin();
}
void set_grid_pos_invalid(pos ¤t_pos) {
A[current_pos.x][current_pos.y] = 0;
}
bool get_next_move(pos ¤t_pos, vector<pos> &spec_islands) {
// Right, Down, Left, Up
vector<pos> next_possible_move = {{-1,0}, {0,1}, {1,0}, {0,-1}};
map<float, pos> distance_map;
pos start_pos = current_pos;
for(int i = 0; i < next_possible_move.size(); i++) {
pos next_pos(current_pos.x + next_possible_move[i].x, current_pos.y + next_possible_move[i].y);
if(is_valid_coord(next_pos)) {
float heuristic = calc_heuristic(next_pos, spec_islands);
distance_map.insert(make_pair(heuristic, next_pos));
}
}
if(distance_map.size() > 0) {
current_pos = distance_map.begin()->second;
}
if(start_pos == current_pos) { // no move was possible
return false;
}
return true;
}
bool is_current_pos_at_dest(pos ¤t_pos, vector<pos> &spec_islands) {
for(int i = 0; i < spec_islands.size(); i++) {
if(current_pos.x == spec_islands[i].x && current_pos.y == spec_islands[i].y) {
return true;
}
}
return false;
}
pos move_to_spec_island(pos &start_pos, vector<pos> &spec_islands, vector<pos> &dang_islands) {
stack<pos> movements;
bool move_possible = false;
bool dest_reached = false;
bool do_move = true;
pos current_pos = start_pos;
init_grid(dang_islands);
set_grid_pos_invalid(current_pos);
movements.push(current_pos);
do {
do_move = true;
move_possible = get_next_move(current_pos, spec_islands);
set_grid_pos_invalid(current_pos);
dest_reached = is_current_pos_at_dest(current_pos, spec_islands);
// Backtrack
if(!move_possible && !dest_reached) {
if(!movements.empty()) {
do {
pos prev_pos = movements.top();
movements.pop();
if(prev_pos != current_pos) {
current_pos = prev_pos;
break;
}
current_pos = prev_pos;
}while(!movements.empty());
}
else {
do_move = false;
}
}
else {
movements.push(current_pos);
}
cout << "x: " << current_pos.x << ", y: " << current_pos.y << endl;
}while(do_move && !dest_reached);
return current_pos;
}
void dest_visited(pos ¤t_pos, vector<pos> &spec_islands) {
for(int i = 0; i < spec_islands.size(); i++) {
if(current_pos.x == spec_islands[i].x && current_pos.y == spec_islands[i].y) {
spec_islands.erase(spec_islands.begin() + i);
break;
}
}
}
int main() {
vector<pos> spec_islands = {{4,6}, {5,5}, {3,3}, {1,2}};
vector<pos> dang_islands = {{3,6}, {2,5}, {2,2}, {0,3}, {1,3}, {2,3}};
pos start_pos = {1,6};
pos current_pos = start_pos;
while(!spec_islands.empty()) {
cout << "move to dest: " << endl;
start_pos = current_pos;
current_pos = move_to_spec_island(start_pos, spec_islands, dang_islands);
if(current_pos == start_pos) {
break;
}
dest_visited(current_pos, spec_islands);
cout << '\n';
}
}
```

this could be done by BFS several times.

1) find the first reach able island by BFS from start point.

and let's count the #mov

2) empty that start point, and set the node the we found from previous as start point and repeat 1) again

int valid(vector<vector<int>> &vv, int n, int nx, int ny, queue<Point*> &nq)

{

if (nx >= 0 && nx < n && ny >=0 && ny < n && (vv[nx][ny] == 0 || vv[nx][ny] == 1))

{

Point * p = new Point(nx, ny);

nq.push(p);

int ret = vv[nx][ny];

vv[nx][ny] = -1;

return ret;

}

return -1;

}

int traval(int n, vector<Point> &spec, vector<Point> &dan, Point* start){

// no need to travel

if (spec.size() == 0)

return 0;

// init matrix, set as all pass

vector<vector<int>> vv;

for(int i=0; i<n; i++)

{

vector<int> v(n, 0);

vv.push_back(v);

}

// set spec points

for(int i=0; i<spec.size(); i++)

{

vv[spec[i].x][spec[i].y] = 1;

}

// set dangerous points

for(int i=0; i<dan.size(); i++)

{

vv[dan[i].x][dan[i].y] = 2;

}

int mov = 0;

for(int i=0; i<spec.size(); i++)

{

int nmov = nextNode(n, vv, start);

if (nmov > 0){

mov +=nmov;

}

else{ // no possible path

return -1;

}

}

return mov;

}

int nextNode(int n, vector<vector<int>> &vv, Point* &start)

{

// reset

for(int i=0; i<n; i++)

{

for(int j=0; j<n; j++)

{

if (vv[i][j] < 0)

{

vv[i][j] = 0;

}

}

}

// BFS, start from start point

queue<Point*> q;

vv[start->x][start->y] = -1;

q.push(start);

int mindepth = INT_MAX;

int depth = 0;

while(!q.empty())

{

queue<Point*> nq;

depth ++;

while(!q.empty())

{

// for each current, add children

Point* p = q.front();

q.pop();

if (valid(vv, n, p->x-1, p->y, nq) == 1)

{

start = p;

return depth;

}

if (valid(vv, n, p->x, p->y-1, nq) == 1)

{

start = p;

return depth;

}

if (valid(vv, n, p->x+1, p->y, nq) == 1)

{

start = p;

return depth;

}

if (valid(vv, n, p->x, p->y+1, nq) == 1){

start = p;

return depth;

}

}

q = nq;

}

return 0; // not possible

}

Given a pair of nodes <n1,n2> meaning the shortest path from n1 to n2, we could build DP[x][y][steps] to solve it. Each node could possibly be reached through 4 directions, so DP[x][y][steps] = min(DP[x-1][y][steps-1] + 1, DP[x][y-1][steps-1] + 1, DP[x+1][y][steps-1] + 1,DP[x][y+1][steps-1] + 1) if corresponding islands[x-1/x+1][y-1/y+1] is safe. After this is computed for any pair of islands (which I think will take O(N^3 * N^2)), then search minimal spanning tree on the graph covering all necessary islands.

An MST gives us the minimum cost of connecting all vertices. However, in this problem we want a route that will pass through all specific islands. This is not the same as MST and it's why it's similar to TSP.

Consider this graph as counter-example:

A - B, cost 1

A - D, cost 2

B - C, cost 2

D - E, cost 2

The MST has cost 7, using all edges. However, lets say A is the starting point and B..E the specific islands. The best route would be A -> B -> C -> B -> A -> D -> E with cost 1+2+1+2+2 = 10.

I don't understand your example. Are you considering each cell as a vertice ?

My approach will only consider 3 nodes. And at each node it will calculate the smallest path and add it to the route. So it should be fine...

I think the only thing i would need to change is instead of considering all the nodes I need to consider the last added node while exploring shortest paths.

In general because this is a grid,

I am assuming all geometric properties hold true. esp sum of two sides of triangle is greater than the 3rd side.

Also while finding the shortest path I am not considering other islands as islands at all, I just consider them as any other grid that is not dangerous point.

A - B, cost 1

A - D, cost 2

B - C, cost 2

D - E, cost 2

This example of yours on a grid will look something like this(assuming all the other paths are blocked by dangerous islands)

A-B = 1

A-D = 2

A-C = 3

A-E = 4

So on and so forth.

You can code assuming that n can be at most 20 and number of special islands are not more than 10.

I was using a general graph as example because it's easier to find counter-examples to the greedy approaches.

To see why your greedy approach is wrong, imagine the grid has only one line. 's' denotes the starting position and A,B,C the special places.

`A..s.B.....C`

The best path is s -> A -> B -> C with cost 3 + 5 + 6 = 14. However, the greedy algorithm will go first to B because it is closer to the start, then to A and finally to C yielding a cost of 2 + 5 + 11 = 18

This is similar to the Travelling Salesman problem, which is NP-hard.

- Miguel Oliveira October 12, 2013- If the number S of specific islands is quite small, say <= 20, we can perform S+1 Breadth First Searches to find all pairs of distances between the S islands and the initial position. Then, we can check all permutations of the S islands and calculate the cost of the possible paths "Initial pos -> Island_1 -> .. Island_S" using the distances calculated above. We can use dynamic programming to find the best path. The DP state can be the current specific island and a bitmask with the covered islands so far.

The running time will be O(S^2 * 2^S + S * N^2).

Note that 2^20 is about 1 million which allows this solution to be fast.

- If there are more specific islands, we can try A*. I don't know much about heuristics but we should try to discuss them with the interviewer. Like using the number of the islands covered so far and the current cost.