## Facebook Interview Question for SDE-2s

Country: India

Comment hidden because of low score. Click to expand.
5
of 7 vote

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

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

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

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?

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

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.

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

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

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

I see it as a simple BFS traversal problem keeping the predecessor and removing the edges to dangerous island.... Let me know in case I am wrong.

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

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 ?

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

You may check my answer to Gedo Mazo to see why that's incorrect.

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

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.

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

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

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

ya

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

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

``````#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 &current_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 &current_pos) {
A[current_pos.x][current_pos.y] = 0;
}

bool get_next_move(pos &current_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 &current_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 &current_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';
}
}``````

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

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
}

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

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.

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

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.

Comment hidden because of low score. Click to expand.
-2

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.

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

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.

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

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

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

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

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

How can you guarantee the minimum number of step with flooding fill

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.