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;
}

- Anonymous April 18, 2015 | Flag Reply
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.

- SK April 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- HBY April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK April 18, 2015 | Flag
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)

- Demo April 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- HBY April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}


}

- Kolpino April 20, 2015 | Flag Reply
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;
}

- Ivan April 21, 2015 | Flag Reply
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;
  }
}

- hankm2004 June 25, 2015 | Flag Reply
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));
    }
}

- Khelsa July 02, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More