Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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.
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;
}
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)
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)
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;
}
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);
}
}
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);
}
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);
}
}
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);
}
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.
A tester
- aonecoding April 21, 2018