Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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.
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.
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)
package google.task;
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;
}
}
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;
}
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;
}
}
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));
}
}
- Anonymous April 18, 2015