Facebook Interview Question for Software Engineers


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

    public int loadRow(int[] row) {
        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');
    }

- aonecoding April 21, 2018 | Flag Reply
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;
}

- Shan April 22, 2018 | Flag Reply
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;

- Shan April 22, 2018 | Flag Reply
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;
}

- Anonymous April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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.

- Nooreddin April 26, 2018 | Flag Reply
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;
}

- aman.bansal4u May 19, 2018 | Flag Reply
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:
            ids.add(i)
            return maxIds, ids, i

    maxIds += 1
    ids.add(maxIds)
    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.add(pl[x])

                    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)

- duongnt79 May 28, 2018 | Flag Reply
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)

- adr June 17, 2018 | Flag Reply
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

- Polly July 14, 2018 | Flag Reply
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;
}

- SHAN April 22, 2018 | Flag Reply
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);
	}

}

- Anupam May 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ofekpearl November 17, 2018 | Flag
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);
	}

}

- Anupam May 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ofekpearl November 17, 2018 | Flag


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