## Facebook Interview Question for Software Engineers

• 6

Country: United States
Interview Type: In-Person

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

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired by G, FB, U, Amazon, LinkedIn and other companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:
Q1 - DFS to count the number of connected components in graph.

Followup -
What if board is too big?
Consider dividing the board and process each part separately.

Divide into blocks or row by row?
Row by Row. It's hard to deal with the border of blocks.
Union find by each row

What's the memory consumption?
Each time load 1 row of input into memory. Create a union find array for two rows (current row and previous row). Memory = 3 * row.

``````public class NumberOfIslands {
int rowLen;
int rowCounter;
int numberOfIslands;

Integer[] islands;

public NumberOfIslands(int rowLen) {
this.rowLen = rowLen;
islands = new Integer[(rowLen + 1) * 2];
}

rowCounter++;
for(int i = 1; i <= rowLen; i++) {
if(row[i - 1] != 0) {
int j = i + rowLen + 1;
Integer top_root = find(i);
Integer left_root = find(j - 1);

//System.out.println("idx " + i );
//System.out.println("top " + top_root + " left " + left_root);
if(top_root == null && left_root == null) { //new island found
numberOfIslands++;
islands[j] = j;
} else if(top_root == null) { //no top neighbor. join left neighbor
islands[j] = left_root;
} else if(left_root == null){ //no left neighbor. join top neighbor
if(top_root <= rowLen) {  //top neighbor had no connection with new row
islands[top_root] = j;
islands[j] = j;
} else {                  //top neighbor's ancestor is in new row
islands[j] = top_root;
}
} else {
if(top_root == left_root) { //no union since left neighbor and top neighbor were in same island
islands[j] = left_root;
} else {                    //union left and top neighbors
islands[top_root] = left_root;
islands[j] = left_root;
numberOfIslands--;
}
}
}
}

compression();

for(int i = 0; i <= rowLen; i++) {
int j = i + rowLen + 1;
if(islands[j] != null) {
islands[i] = islands[j] % (rowLen + 1);
islands[j] = null;
} else {
islands[i] = null;
}
}
return numberOfIslands;
}

private Integer find(int idx) {
if(islands[idx] == null) return null;
while(idx != islands[idx]) {
idx = islands[idx];
}
return idx;
}

private void compression() {
for(int i = rowLen + 1; i < islands.length; i++) {
if(islands[i] != null) {
islands[i] = find(i);
}
}
}``````

A tester

``````public static void main(String[] args) {
NumberOfIslands instance = new NumberOfIslands(10);
System.out.println("number of islands " + instance.loadRow(new int[]{0,0,1,1,0,1,0,1,0,1}) + '\n');
System.out.println("number of islands " + instance.loadRow(new int[]{1,1,1,1,1,1,0,1,1,1}) + '\n');
System.out.println("number of islands " + instance.loadRow(new int[]{0,0,0,0,0,0,0,0,0,1}) + '\n');
System.out.println("number of islands " + instance.loadRow(new int[]{1,0,0,1,0,1,0,0,0,1}) + '\n');
System.out.println("number of islands " + instance.loadRow(new int[]{1,1,1,1,0,1,0,1,0,1}) + '\n');
}``````

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

sample code:

int island = 0;
for(int i=0; i<row, i++) {
for (int j=0; j<col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

You only need to store two rows at a time in memory.
For each point you need access to the up and left cells.
For each point if the point is land, check all up and left.
If none of them is land then make a set with a new number (i.e. If numbers 1, 2 ,3 and 4 are aalready used for sets then number 5 is the next candidate).
If one of them is land then the number of this land becomes the same as that one.
If both of them are land then union the set of both of them and this land belongs to the new set.

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

``````void findIsland(vector<string>& grid, int i, int j, int count)
{
int m = grid.size();
int n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] != 'X')
return;
grid[i][j] = '0'+count;
findIsland(grid, i - 1, j, count);
findIsland(grid, i + 1, j, count);
findIsland(grid, i, j-1, count);
findIsland(grid, i, j+1, count);
}

int idIslands(vector<string>& grid)
{
int m = grid.size();
int n = grid[0].size();
int count = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'X')
findIsland(grid, i, j, ++count);
}
}
return count;
}``````

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

Here is my solution, 20 min and crude but only need the previous line and current line:

``````a = [
'XXX00X',
'00XXXX',
'XX00XX',
'0XXXX0',
]

def findNextIds(maxIds, ids):
for i in range(1, maxIds + 1):
if i not in ids:
return maxIds, ids, i

maxIds += 1
return maxIds, ids, maxIds

pl = None
ids = set()
maxIds = 0
for ln, l in enumerate(a):
print("{}: pl: {}".format(ln, pl))
n = len(l)
p = [0] * n
i = 0
while i < n:
if l[i] == 'X':
if i == 0 or l[i - 1] != 'X':
j = i
while j < n and l[j] == 'X':
j += 1

if pl is None:
maxIds, ids, id = findNextIds(maxIds, ids)
for x in range(i, j):
p[x] = id
else:
pids = set()
for x in range(i, j):
if pl[x] > 0:

pids = sorted(pids)
if len(pids) == 0:
maxIds, ids, id = findNextIds(maxIds, ids)
else:
for id in pids[1:]:
for x in range(len(pl)):
if pl[x] == id:
pl[x] = pids[0]
ids.remove(id)
id = pids[0]

for x in range(i, j):
p[x] = id

i = j
i = i + 1

pl = p
print("{}: p: {}".format(ln, pl))

print(ids)``````

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

If one can fit the entire map in memory, then union-find is an overkill

``````import random
n,m=3,4
grid=[[random.choice("XO") for _ in xrange(m)] for _ in xrange(n)]

def numIslands(grid):
count = 0
for p in xrange(n*m):
r,c = p/m,p%m
if grid[r][c] == 'X':
count += 1
l = [p]
while l:
p = l.pop()
for z in filter(lambda z: 0<=z<n*m
and grid[z/m][z%m] == 'X'
and abs(z/m-p/m)*abs(z%m-p%m)<2,
[p-1,p+1,p-m,p+m]):

grid[z/m][z%m] = 'V'
l += [z]
return count

for v in grid:
print v
print numIslands(grid)``````

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

def find_island(arr):
count=0
for i in range(len(arr)):
for j in range(len(arr[i])):
if arr[i][j]=='X':
if j>0 and arr[i][j-1]!='0':
arr[i][j]=arr[i][j-1]
elif i>0 and arr[i-1][j]!='0':
arr[i][j]=arr[i-1][j]
else:
count+=1
arr[i][j]=count
return count

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

sample code:

``````int getIsland(char ar[][], int row, int col) {
int island = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (isIsland(ar, i, j) && !isIsland(ar, i, j-1) && !isIsland(ar, i-1, j-1) && !isIsland(ar, i-1, j) && !isIsland(ar, i-1, j+1)) {
island++;
}
}
}

return island;
}``````

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

``````public class islands {

public static void main(String[] args) {
// TODO Auto-generated method stub

char[][] x = {
{'X','X','X','O','O'},
{'O','O','O','X','X'},
{'X','X','O','O','X'}
};
System.out.println(findisland(x));

}

private static int findisland(char[][] x) {
int count=0;
int[][] n =new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}

return (count);
}

}``````

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

This solution will not work for this example:

``````public static void main(String[] args) {
// TODO Auto-generated method stub

char[][] x = {
{'X','O','X'},
{'O','X','X'},
{'O','O','O'}
};
System.out.println(findisland(x));

}

private static int findisland(char[][] x) {
int count=0;
int[][] n = new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}

return (count);
}``````

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

``````public class islands {

public static void main(String[] args) {
// TODO Auto-generated method stub

char[][] x = {
{'X','X','X','O','O'},
{'O','O','O','X','X'},
{'X','X','O','O','X'}
};
System.out.println(findisland(x));

}

private static int findisland(char[][] x) {
int count=0;
int[][] n =new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}

return (count);
}

}``````

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

This will not work for this example (prints out 3 instead of 2):

``````public static void main(String[] args) {
// TODO Auto-generated method stub

char[][] x = {
{'X','O','X'},
{'O','X','X'},
{'O','O','O'}
};
System.out.println(findisland(x));

}

private static int findisland(char[][] x) {
int count=0;
int[][] n = new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}

return (count);
}``````

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.