## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````private static final int[][] neighbours = {
{-1, 0, 0, 1},
{0, -1, 1, 0},
};

public static boolean[][] bothCoastsPositions(int[][] a) {
int n = a.length;
int m = (n == 0) ? 0 : a[0].length;
boolean[][] b = new boolean[n][m];
if (n == 0 || m == 0) {
return b;
}
boolean[][] east = wave(a, n, m, 0, 0);
boolean[][] west = wave(a, n, m, n - 1, m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[i][j] = east[i][j] && west[i][j];
}
}
return b;
}

static boolean[][] wave(int[][] a, int n, int m, int i0, int j0) {
int[][] queue = new int[2][n * m];
boolean[][] b = new boolean[n][m];
int qsize = 0;
for (int j = 0; j < m; j++) {
b[i0][j] = true;
queue[0][qsize] = i0;
queue[1][qsize] = j;
qsize++;
}
for (int i = 0; i < n; i++) {
if (!b[i][j0]) {
b[i][j0] = true;
queue[0][qsize] = i;
queue[1][qsize] = j0;
qsize++;
}
}
for (int k = 0; k < qsize; k++) {
int i = queue[0][k];
int j = queue[1][k];
for (int d = 0; d < 4; d++) {
int ni = i + neighbours[0][d];
int nj = j + neighbours[1][d];
if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
if (!b[ni][nj] && a[i][j] <= a[ni][nj]) {
b[ni][nj] = true;
queue[0][qsize] = ni;
queue[1][qsize] = nj;
qsize++;
}
}
}
}
return b;
}``````

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

You can start by BFSing from the top left corner, with the exception that you will only keep BFSing if the value is increasing. Keep a secondary 2D array with lists of parent pointers for each element of the array. When every element has been visited, we now will have a graph of parents in our secondary 2D array. For all elements bordering the east coast, traverse through all of the parent pointers. If one of the pointers reaches the west coast, increment a global count of possible paths.

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

My solution was create a virtual node 0 for east coast, n + 1 for west coast, reverse all flow, do BFS from 0, get a Set A, do BFS from n + 1, get set B. Merge set A and B. You solution won't work if left corner is biggest value of the array.

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

True. We may need to BFS from the smallest value on the west coast then- this would solve that issue

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

What about doing back-tracking from all the west-coast nodes in the graph? There will be an reversed edge only if it follows the rules. Then I would also keep another 2D array to track parents and stop traversing while the parent I'd like to add is already there. Complexity is n^1.5 (n^0.5 for starting from every westcoast node, n^1 for BFS/DFS)

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

Improvise a little, add a node for east coast and west coast, you solution is better.

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

public class CostToCost {
static int NX = 3;
static int NY = 3;
static Cell cells[][] = new Cell[NX][NY];

public static void main(String[] args) {
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
cells[i][j] = new CostToCost.Cell();
cells[i][j].value=-i;
}
}
cells[1][1].value = -10;
cells[0][0].hasPathDown = true;
visitDown(NX - 1, NY - 1);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
System.out.println(" i=" + i + " j=" + j + " hasPathDwn="
+ cells[i][j].hasPathDown + " isVisitedDown="
+ cells[i][j].isVisitedDown + " value="
+ cells[i][j].value);
}
}
System.out.println("=================");

cells[NX-1][NY-1].hasPathUp = true;
visitUp(0, 0);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
System.out.println(" i=" + i + " j=" + j + " hasPathUp="
+ cells[i][j].hasPathUp + " isVisitedUp="
+ cells[i][j].isVisitedUp + " value="
+ cells[i][j].value);
}
}

System.out.println("=================");

cells[NX-1][NY-1].hasPathUp = true;
visitUp(0, 0);
for (int i = 0; i < NX; i++) {
for (int j = 0; j < NY; j++) {
if (cells[i][j].hasPathUp && cells[i][j].hasPathDown)
System.out.println("Has path down and up i=" + i + " j=" + j );
}
}

}

static class Cell {
boolean isVisitedDown = false;
boolean hasPathDown = false;
int value;
boolean isVisitedUp = false;
boolean hasPathUp = false;
}

static void visitDown(int i, int j) {
if (i < 0 || i > (NX - 1) || j < 0 || j > (NY - 1))
return;
if (cells[i][j].isVisitedDown == true)
return;

int newI = i - 1;
if (newI >= 0) {
visitDown(newI, j);
if (cells[newI][j].value <= cells[i][j].value
&& cells[newI][j].hasPathDown) {
cells[i][j].hasPathDown = true;
}
}
int newJ = j - 1;
if (newJ >= 0) {
visitDown(i, newJ);
if (cells[i][newJ].value <= cells[i][j].value
&& cells[i][newJ].hasPathDown) {
cells[i][j].hasPathDown = true;
}
}

cells[i][j].isVisitedDown = true;
}

static void visitUp(int i, int j) {
if (i < 0 || i > (NX - 1) || j < 0 || j > (NY - 1))
return;
if (cells[i][j].isVisitedUp == true)
return;

int newI = i + 1;
if (newI < NX) {
visitUp(newI, j);
if (cells[newI][j].value <= cells[i][j].value
&& cells[newI][j].hasPathUp) {
cells[i][j].hasPathUp = true;
}
}
int newJ = j + 1;
if (newJ < NY) {
visitUp(i, newJ);
if (cells[i][newJ].value <= cells[i][j].value
&& cells[i][newJ].hasPathUp) {
cells[i][j].hasPathUp = true;
}
}

cells[i][j].isVisitedUp = true;
}

}

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

``````struct Point {
Point(int _x, int _y) : x(_x), y(_y) {}

int x;
int y;
};

vector<Point> GetPoints(const vector<vector<int>>& f)
{
//1 - west cost
//2 - east cost

size_t rows = f.size(), cols = f[0].size();
vector<vector<int>> m(rows, vector<int>(cols));

for (size_t i = 0; i < rows; ++i) {
m[i][0] |= 1; //left edge is a west
m[i][cols - 1] |= 2; //right edge is a east
}
for (size_t i = 0; i < cols; ++i) {
m[0][i] |=1; //top edge is a west
m[rows - 1][i] |= 2; //bottom edge is a east
}

for (size_t r = 1; r < rows; ++r) {
for (size_t c = 1; c < cols; ++c) {
//mark all points where I can reach west coast from
if ( (m[r][c - 1] & 1) && f[r][c - 1] <= f[r][c]) {
m[r][c] |= 1;
} else if ( (m[r - 1][c] & 1) && f[r - 1][c] <= f[r][c]) {
m[r][c] |= 1;
}

//mark all positions where I can reach east coast from
size_t curr = rows - r - 1, curc = cols - c - 1;
if ( (m[curr][curc + 1] & 2) && f[curr][curc + 1] <= f[curr][curc]) {
m[curr][curc] |= 2;
} else if ( (m[curr + 1][curc] & 2) && f[curr + 1][curc] <= f[curr][curc]) {
m[curr][curc] |= 2;
}
}
}

vector<Point> res;
for (size_t r = 0; r < rows; ++r) {
for (size_t c = 0; c < cols; ++c) {
if (m[r][c] == 3) {
res.push_back(Point(r, c));
}
}
}
return res;
}``````

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

``````struct Point {
int x;
int y;
Point(int posx, int posy):x(posx), y(posy){}
};

int x_move[4] = {1, -1, 0, 0 };
int y_move[4] = {0, 0, 1, -1};

list<Point>* get_edges(Point p, int*map[], int h, int w)
{
list<Point>* edges = new std::list<Point>();
int cur = map[p.y][p.x];

for (int m = 0; m <4; m++)
{
int next_x = p.x+x_move[m];
int next_y = p.y+y_move[m];
if (next_x <=0 || next_x >= w-1 || next_y <=0 || next_y>=h-1)
continue;
if (cur <= map[next_y][next_x])
edges->push_back(Point(next_x, next_y));
}
return edges;
}

void DFS(Point s, int*map[], int* marked[],int h, int w, int direction)
{
list<Point>* edges = get_edges(s, map, h, w);
list<Point>::iterator iter;
for (iter = edges->begin(); iter != edges->end(); iter++)
{
if ((marked[(*iter).y][(*iter).x] & direction)==0)
{
marked[(*iter).y][(*iter).x] |= direction;
DFS((*iter), map, marked, h, w, direction);
}
}
delete edges;
}

void find_path(int **map, int h, int w)
{
int EAST = 1;
int WEST = 2;
int **marked;
marked = new int* [h];
for (int i = 0; i < w; i++)
marked[i] = new int[w];

for (int x = 0; x < w; x++)
{
marked[0][x] |= EAST;
DFS(Point(x, 0), map, marked, h, w, EAST);
}

for (int y = 1; y < h-1; y++)
{
marked[y][0] |= EAST;
DFS(Point(0, y), map, marked, h, w, EAST);
}

for (int wx = 0; wx < w; wx++)
{
marked[h-1][wx] |= WEST;
DFS(Point(wx, h-1), map,  marked, h, w, WEST);
}
for (int wy = 1; wy < h; wy++)
{
marked[wy][w-1] |= WEST;
DFS(Point(w-1, wy), map,  marked, h, w, WEST);
}
for (int row = 0; row < w; row++)
{
for(int col = 0; col < h; col++)
{
//  if (marked[col][row] == 3)
cout<< marked[col][row];
}
cout <<endl;
}
}``````

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

``````public class EastWestFlowCalculator {

public static boolean[][] calculateFlows(int[][] values) {
int size = values.length;
boolean[][] east = new boolean[size][size];
boolean[][] west = new boolean[size][size];

for (int r=0; r<size; r++) {
for (int c = 0; c < size; c++) {
east[r][c] = false;
west[r][c] = false;
}
}

computeEastMatrix(east, size, values);
print(east);    //debug
computeWestMatrix(east, west, size, values);
print(west);    //debug

//reuse east as the result matrix; check those cells with true and mark them false if corresponding cell is false in west
for (int r=0; r<size; r++)
for (int c=0; c<size; c++)
if ((east[r][c] == true) && (west[r][c] == false))
east[r][c] = false;
return east;
}

private static void computeEastMatrix(boolean[][] east, int size, int[][] values) {
for (int r=0; r<size; r++) {
east[0][r] = true;
east[r][0] = true;
}

for (int r=1; r<size; r++) {
for (int c=1; c<size; c++) {
if ((east[r-1][c] == true) && (values[r][c] >= values[r-1][c]))     //check if u can flow through upper row
east[r][c] = true;
else if ((east[r][c-1] == true) && (values[r][c] >= values[r][c-1]))    //check if u can flow through left column
east[r][c] = true;
else
east[r][c] = false;
}
}
}

private static void computeWestMatrix(boolean[][] east, boolean[][] west, int size, int[][] values) {
for (int i=0; i<size; i++) {
west[i][size-1] = true;
west[size-1][i] = true;
}

for (int r=size-2; r>=0; r--) {
for (int c=size-2; c>=0; c--) {
if (east[r][c] == true) {       //question asks those you can flow to both -> no need to compute those where you cant flow east
if ((west[r+1][c] == true) && (values[r][c] >= values[r+1][c]))
west[r][c] = true;
else if ((west[r][c+1] == true) && (values[r][c] >= values[r][c+1]))
west[r][c] = true;
else
west[r][c] = false;
}
}
}
}

private static void print(boolean[][] matrix) {
for (boolean[] row:matrix) {
for (boolean b:row)
System.out.print(b ? "+":"-");
System.out.println("");
}
System.out.println();
}

public static void main(String[] args) {
int[][] values = {
{1, 2, 1, 4},
{6, 1, 4, 2},
{3, 4, 3, 1},
{2, 3, 4, 5}
};

print(calculateFlows(values));
}
}``````

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.