## Facebook Interview Question for Software Engineer Interns

• 0
of 0 votes

Interview Type: Phone Interview

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

``````func IslandCount

set island count to 0
for each index, (go from left to right, row by row)
if the top adjacent index is 0, and the left adjacent index is 0, increment island count by 1
if the top adjacent index is 1, and the left adjacent index is 1, decrement island count by 1
end for

return island count
end func``````

i didnt test this but i believe this is the answer.
efficiency would be O(n)

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

``````matrix = [[0,1,0,1,0],
[0,1,0,0,1],
[0,1,1,0,1]]
count = 0

def searchrows_island(x, y):
if (x == len(matrix) or
y == len(matrix[0]) or
matrix[x][y] <= 0):
return
matrix[x][y] = -1
searchrows_island(x + 1, y)
searchrows_island(x, y + 1)

for x in range(len(matrix)):
for y in range(len(matrix[0])):
if matrix[x][y] <= 0:
continue
else:
count = count + 1
searchrows_island(x, y)

print(count)``````

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

Good solution, but it doesn't consider islands expanding on the left side.
The number of islands in this matrix is still 3, but the algorithm returns 7:

``````matrix = [[0,1,0,1,0],
[0,1,0,0,1],
[0,1,1,0,1]]``````

Here's a revisited solution:

``````def eraser(map, height, width, x, y):
if 0 <= x < height and 0 <= y < width and map[x][y] == 1:
map[x][y] = -1
eraser(map, height, width, x, y+1)
eraser(map, height, width, x+1, y)
eraser(map, height, width, x, y-1)

def scan_map(map, height, width):
count = 0
for x in range(height):
for y in range(width):
if map[x][y] == 1:
eraser(map, height, width, x, y)
count += 1
return count``````

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

``````package Main;

public class Island {

public static void main(String[] args) {

//		int[][] map = {{0, 1, 0, 1, 1},
//					   {0, 0, 0, 1, 1},
//					   {1, 1, 0, 1, 0}};

//		int[][] map = {{0, 1, 0, 1, 0, 1},
//				   	   {0, 1, 1, 1, 0, 1},
//				   	   {1, 1, 0, 0, 0, 0},
//				   	   {1, 1, 0, 1, 1, 1}};

int[][] map = {{0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 1, 1},
{0, 0, 1, 0, 0, 0}};

new Island().count(map);

}

private void count(int[][] map) {
Context c = new Context();
c.x = 0;
c.y = 0;

int[][] visitedPoints = new int[map.length][map[0].length];
for(int i=0; i<visitedPoints.length; i++) {
for(int j=0; j<visitedPoints[0].length; j++) {
visitedPoints[i][j] = 0;
}
}
c.visitedPoints = visitedPoints;

int counter = countInner(map, c);
System.out.println(counter);

for(int i=0; i<c.visitedPoints.length; i++) {
for(int j=0; j<c.visitedPoints[0].length; j++){
System.out.print(c.visitedPoints[i][j] + "  ");
}
System.out.println();
}
}

private int countInner(int[][] map, Context c) {
int counter = 0;

for(int i=0; i<map.length; i++) {
for(int j=0; j<map[0].length; j++) {

if(map[i][j] == 1 && c.visitedPoints[i][j] == 0) {
counter++;
c.x = i;
c.y = j;
visit(map, c);
}

if(map[i][j] == 0) {
c.visitedPoints[i][j]++;
}
}
}

return counter;
}

private void visit(int[][] map, Context c) {
int x = c.x;
int y = c.y;

c.visitedPoints[x][y]++;
//try to move right
if((y+1)<map[0].length && map[x][y+1] == 1 && c.visitedPoints[x][y+1] == 0) {
c.y = y + 1;
visit(map, c);
}

//try to move left
if((y-1)>-1 && map[x][y-1] == 1 && c.visitedPoints[x][y-1] == 0) {
c.y = y - 1;
visit(map, c);
}

//try to move bottom
if((x+1)<map.length && map[x+1][y] == 1 && c.visitedPoints[x+1][y] == 0) {
c.x = x + 1;
visit(map, c);
}

//try to move top
if((x-1)>-1 && map[x-1][y] == 1 && c.visitedPoints[x-1][y] == 0) {
c.x = x - 1;
visit(map, c);
}
}

public class Context {
int x;
int y;
int[][] visitedPoints;
}

}``````

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

#include "stdafx.h"// A C program to print all anagarms together
#include <stdio.h>
#include <vector>
using namespace std;
vector<vector<char>> worldGlobal{
vector<char>{0,1,0,1,0,1,0},
vector<char>{0,1,0,0,0,1,0},
vector<char>{0,1,1,0,1,0,1}
};

char **arrVisited = nullptr;
int height;
int width;
int counter = 0;
void VisitAll(int h, int w, const vector<vector<char>> &world)
{

if (h >= height)
return;

if (w >= width)
return;

if (w < 0)
return;

if (h < 0)
return;

if (worldGlobal[h][w] == 0)
return;

if (arrVisited[h][w] == 1)
return;

else if (worldGlobal[h][w] == 1 && arrVisited[h][w]==0)
{
arrVisited[h][w] = 1;
}

VisitAll(h+1, w, worldGlobal);
VisitAll(h, w+1, worldGlobal);

}

void Getlands(int h,int w, const vector<vector<char>> &world)
{
if (worldGlobal[h][w] == 1 && arrVisited[h][w] == 0)
{
arrVisited[h][w] = 2; // find the root
counter++;
VisitAll(h, w, worldGlobal);
}
}

void main()
{
height = worldGlobal.size();
width = worldGlobal[0].size();

for (int i = 0; i < height; i++)
{
for (int j = 0; j <width; j++)
{
int y = worldGlobal[i][j];
printf("%d ", y);
}
printf("\n");
}
printf("\n");
if (arrVisited == nullptr)
{
arrVisited = new char*[height];
for (int i = 0; i < height; i++)
arrVisited[i] = new char[width]{ 0 };
}

for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
Getlands(i, j, worldGlobal);
}
}

for (int i = 0; i < height; i++)
{
for (int j = 0; j <width; j++)
{
int y = arrVisited[i][j];
printf("%d ",y);
}
delete [] arrVisited[i];
arrVisited[i] = nullptr;
printf("\r\n");
}
printf("Number islands %d \r\n", counter);
delete [] arrVisited;
}

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

Very short solution. It checks that 0 could be an island also if it's alone:

``````public boolean isAnIsland(int[][] matrix, int[] pointXY) {
assert pointXY.length == 2;

int x = pointXY[0];
int y = pointXY[1];
int value = matrix[x][y];

boolean top = x <= 0 || (matrix[x - 1][y] != value);
boolean bottom = x >= matrix.length - 1 || (matrix[x + 1][y] != value);
boolean left = y <= 0 || (matrix[x][y - 1] != value);
boolean right = y >= matrix[x].length - 1 || (matrix[x][y + 1] != value);

return top && bottom && left && right;
}

public int foundNumberOfIslands(int[][] matrix) {
int count = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (isAnIsland(matrix, new int[]{i, j})) {
count++;
System.out.println("Coordinates: " + i + ", " + j);
}
}
}

return count;
}``````

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

``````import numpy as np

RNG = np.random.RandomState(1234)

def findIslandsCount(mtx):
rows = len(mtx)
columns = len(mtx[0])

# visited = [[False for j in range(len(mtx[0]))] for i in range(len(mtx))]

numIslands = 0
for i in range(rows):
for j in range(columns):
if mtx[i][j] == 1:
dfs(i, j, rows, columns, mtx)
numIslands += 1

return numIslands;

def dfs(i, j, rows, cols, mtx):
rowNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
colNbr = [-1, -1, -1, 0, 0, 1, 1, 1]

mtx[i][j] = 0

for k in range(len(rowNbr)):
if isSafe(i+rowNbr[k], j+colNbr[k], rows, cols, mtx):
dfs(i+rowNbr[k], j+colNbr[k], rows, cols, mtx)

def isSafe(i, j, rows, cols, mtx):
# row number is in range, column number
# is in range and value is 1
# and not yet visited
return (i >= 0 and i < rows and
j >= 0 and j < cols and
mtx[i][j])

if __name__ == "__main__":
graph = RNG.randint(low=0, high=2, size=(6, 7))
print(graph)

result = findIslandsCount(graph)
print(result)``````

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

``````import numpy as np

RNG = np.random.RandomState(1234)

def findIslandsCount(mtx):
rows = len(mtx)
columns = len(mtx[0])

# visited = [[False for j in range(len(mtx[0]))] for i in range(len(mtx))]

numIslands = 0
for i in range(rows):
for j in range(columns):
if mtx[i][j] == 1:
dfs(i, j, rows, columns, mtx)
numIslands += 1

return numIslands;

def dfs(i, j, rows, cols, mtx):
rowNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
colNbr = [-1, -1, -1, 0, 0, 1, 1, 1]

mtx[i][j] = 0

for k in range(len(rowNbr)):
if isSafe(i+rowNbr[k], j+colNbr[k], rows, cols, mtx):
dfs(i+rowNbr[k], j+colNbr[k], rows, cols, mtx)

def isSafe(i, j, rows, cols, mtx):
# row number is in range, column number
# is in range and value is 1
# and not yet visited
return (i >= 0 and i < rows and
j >= 0 and j < cols and
mtx[i][j])

if __name__ == "__main__":
graph = RNG.randint(low=0, high=2, size=(6, 7))
print(graph)

result = findIslandsCount(graph)
print(result)``````

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

For each 1.... do DFS.... maitain visited 2D array too to avoid visiting 1 again.

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

Do DFS/BFS for each each one ..... maintain visited 2D array to make sure we visit each one only once.

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

How about an immutable language? ;-)

``````-module(islands).

-export([start/0]).

start() ->
3 = count(["01010",
"01001",
"01101"]),

2 = count(["10101",
"10111"]),

1 = count(["10101",
"10111",
"11100"]),
ok.

count([Row | _] = Rows) ->
count(fake_start_row(Row), Rows, #{next => 1});
count([]) ->
0.

fake_start_row([_ | Rest]) ->
[0 | fake_start_row(Rest)];
fake_start_row([]) ->
[].

count(TopRow, [Row | Rest], MaybeIslands) ->
{NewRow, NewIslands} = count_row(Row, TopRow, MaybeIslands),
count(NewRow, Rest, NewIslands);
count(_, [], MaybeIslands) ->
maps:fold(fun count_ids/3, 0, maps:remove(next, MaybeIslands)).

count_ids(Key, Key, Count) ->
Count + 1;
count_ids(_, _, Count) ->
Count.

count_row(Row, TopRow, MaybeIslands) ->
count_row(Row, TopRow, MaybeIslands, 0, []).

count_row([], [], MaybeIslands, _, Result) ->
{lists:reverse(Result), MaybeIslands};
count_row([\$0 | Row], [_ | TopRow], MaybeIslands, _, Result) ->
count_row(Row, TopRow, MaybeIslands, 0, [0 | Result]);
count_row([\$1 | Row], [0 | TopRow], MaybeIslands, 0, Result) ->
#{next := Next} = MaybeIslands,
NextIslands = MaybeIslands#{next => Next + 1, Next => Next},
count_row(Row, TopRow, NextIslands, Next, [Next | Result]);
count_row([\$1 | Row], [0 | TopRow], MaybeIslands, Last, Result) ->
count_row(Row, TopRow, MaybeIslands, Last, [Last | Result]);
count_row([\$1 | Row], [Top | TopRow], MaybeIslands, 0, Result) ->
count_row(Row, TopRow, MaybeIslands, Top, [Top | Result]);
count_row([\$1 | Row], [Top | TopRow], MaybeIslands, Left, Result) ->
NewIslands = MaybeIslands#{Top => Left},
count_row(Row, TopRow, NewIslands, Left, [Left | Result]).``````

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

Just a note , I think yhe recursive function should also take care of diagonals . Not only the next and down : e.g
0100
0010
One island not two !

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

The Python solution above contains very clever use of recursion. But it is not quite right, since it only searches in the "right" and "down" directions with its recursive call.

For example, the test case

``````matrix = [[0,1,0,1,0],
[1,1,0,0,1],
[1,0,0,0,1]]``````

Returns 4, and considers [(0,1), (1,1)] and [(1,0), (2,0)] to be separate islands.

The following modifies that solution to accommodate this:

``````matrix1 = [[0,1,0,1,0],
[1,1,0,0,1],
[1,0,0,0,1]]

matrix2 = [[0,1,0,1,0],
[0,1,0,0,1],
[0,1,1,0,1]]

matrix3 = [[0,1,0,1,0],
[0,1,0,0,1],
[1,0,0,0,1]]

def num_islands(matrix):

count = 0

def searchrows_island(x, y):
if (x == len(matrix) or
y == len(matrix[0]) or
matrix[x][y] <= 0):
return
matrix[x][y] = -1
if y > 0:
searchrows_island(x, y - 1)
searchrows_island(x + 1, y)
searchrows_island(x, y + 1)

for x in range(len(matrix)):
for y in range(len(matrix[0])):
if matrix[x][y] <= 0:
continue
else:
count = count + 1
searchrows_island(x, y)

return count

print(num_islands(matrix1)) # 3
print(num_islands(matrix2)) # 3
print(num_islands(matrix3)) # 4``````

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

``test``

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

hello

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

``````class TwoDimArray {
public static void main(String[] args) {
int[][] input = {
{0,1,0,1,0},
{0,1,0,0,1},
{0,1,1,0,1}
};

int[][] input2 = {
{1,0,1,0,1},
{0,1,0,1,0},
{1,0,1,0,1},
{0,1,0,1,0},
{1,0,1,0,1}
};
System.out.println(numOfIslands(input2));
}

public static int numOfIslands(int[][] input){
int marker = 2;
for(int i = 0; i < input.length; i++){
for(int j = 0; j < input[0].length; j++){
if(input[i][j] == 1) markIsland(input, i, j, marker++);
}
}
return marker - 2;
}

public static void markIsland(int[][] input, int row, int col, int marker){
if(input[row][col] == 0) return;
if(input[row][col] == 1) {
input[row][col] = marker;
if(row > 0) markIsland(input, row - 1, col, marker);
if(col > 0) markIsland(input, row, col - 1, marker);
if(row < input.length-1) markIsland(input, row + 1, col, marker);
if(col < input[0].length-1) markIsland(input, row, col + 1, marker);
}
}
}``````

}

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

``````class TwoDimArray {
public static void main(String[] args) {
int[][] input = {
{0,1,0,1,0},
{0,1,0,0,1},
{0,1,1,0,1}
};

int[][] input2 = {
{1,0,1,0,1},
{0,1,0,1,0},
{1,0,1,0,1},
{0,1,0,1,0},
{1,0,1,0,1}
};
System.out.println(numOfIslands(input2));
}

public static int numOfIslands(int[][] input){
int marker = 2;
for(int i = 0; i < input.length; i++){
for(int j = 0; j < input[0].length; j++){
if(input[i][j] == 1) markIsland(input, i, j, marker++);
}
}
return marker - 2;
}

public static void markIsland(int[][] input, int row, int col, int marker){
if(input[row][col] == 0) return;
if(input[row][col] == 1) {
input[row][col] = marker;
if(row > 0) markIsland(input, row - 1, col, marker);
if(col > 0) markIsland(input, row, col - 1, marker);
if(row < input.length-1) markIsland(input, row + 1, col, marker);
if(col < input[0].length-1) markIsland(input, row, col + 1, marker);
}
}
}``````

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

``````class Solution {
public static void main(String[] args) {
int [][] arr1 = {{0,1,0,1,1}, {1,1,0,0,1}, {0,1,1,0,1}};

System.out.println(countIslands(arr1));
}

public static int countIslands(int [][] arr) {

int count = 0;

for (int i = 0 ; i < arr.length; i++){
for (int j = 0; j < arr[0].length ; j++ ) {
if(arr[i][j] == 1) {
if ( i == 0 && j == 0)
count++;

else if (i == 0 && j > 0 && arr[i][j-1] != 1)
count++;
else if ( j == 0 &&  i > 0 && arr[i-1][j] != 1)
count++;

else if(i != 0 && j!= 0)
if (arr[i-1][j] != 1 && arr[i][j-1] != 1){
count++;
}
}
}

}
return count;
}
}``````

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

``````private int getIslandsCount(final int[][] matrix, final int rows, final int cols) {
if (matrix == null){
return 0;
}

int count = 0;
for (int r=0; r<rows; r++){
for (int c=0; c<cols; c++){
if (getCellValue(matrix, r, c-1) < 1 && getCellValue(matrix, r-1,c) < 1){
// if both left and up cells are 0 or -1 (out of bounds) increase counter
// if 1 is  current cell's value
count += getCellValue(matrix, r, c);
}
}
}
return count;
}

private int getCellValue(final int[][] matrix, final int row, final int col){
if (row < 0 || col < 0 || row == matrix.length || col == matrix[0].length){
// In case cell is outside of matrix return -1
return -1;
}

// For correct cell indexes return real value (0 or 1)
return matrix[row][col];
}``````

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

class Solution(int array[3][5]) {

Boolean isIsland[][] = new Boolean[3][5];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 5; j++) {
isIsland[i][j] = false;
}
}

for(int i = 0; i < 3; i++ ){
for(int j = 0; j < 5; j++) {
if(array[i][j] == 1 && (isIsland[i][j] != true)){
isl_count++;
isIsland[i][j] = true;

for(int x = i; x < 3; x++){
if(array[x][j] == 1)
isIsland[x][j] = true;
else
break;

}
for(int y = j; y < 5; y++) {
if(array[i][y] == 1)
isIsland[i][y] = true;
else
break;
}
}
}
}
System.out.println(isl_count);
}

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

``````public int Solution(int array[i][j]) {
Boolean isIsland[][] = new Boolean[3][5];
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 5; j++) {
isIsland[i][j] = false;
}
}

for(int i = 0; i < 3; i++ ){
for(int j = 0; j < 5; j++) {
if(array[i][j] == 1 && (isIsland[i][j] != true)){
isl_count++;
isIsland[i][j] = true;

for(int x = i; x < 3; x++){
if(array[x][j] == 1)
isIsland[x][j] = true;
else
break;

}
for(int y = j; y < 5; y++) {
if(array[i][y] == 1)
isIsland[i][y] = true;
else
break;
}
}
}
}
System.out.println(isl_count);
}``````

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

``````public class Solution {

public int countIslands(int[][] arr) {
int count = 0;
for ( int i = 0; i < arr.length; i++) {
for ( int j = 0; j < arr[0].length - 1; j++) {
if (arr[i][j] == 1 && arr[i][j+1] == 1)
count++;

if (i + 1 != arr.length && (arr[i][j] == 1 && arr[i+1][j] == 1))
count++;
}

}
return count;
}
public static void main(String[] args) {
Solution s= new Solution();
//    	int[] nums = {5,6,7,0,3,4};
int[][] nums = {{0,1,0,1,0}, {0,1,0,0,1}, {0,1,1,0,1}};
System.out.println(s.countIslands(nums));
}
}``````

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

``````a = [[0,1,0,1,0],[0,1,0,0,1],[0,1,1,0,1]]

# make a list of elements and position
l = []
row = 0
for i in a:
col = 0
for j in i:
k = [row,col]
if (j == 1):
l.append(k)
col += 1
row +=1

print(l)

count = 0
z = []
#traverse by row and col
for i in range(len(l)-1):
if (l[i][0] == l[i+1][0] and (l[i][1] + 1) == l[i+1][1]):
count += 1
for j in range(i,len(l)-1):
if (l[i][1] == l[j+1][1] and l[i][1] not in z):
z.append(l[i][1])
count += 1

print(count)``````

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

``````def numOfIslands_helper(arr, i, j, visited):

#print(i,j)

#print(visited)

if i>=len(arr) or j >= len(arr[0]) or i<0 or j<0:
return 0

if (i,j) in visited:
return 0

if arr[i][j] == 0:
visited[(i,j)] = True
return 0
else:

visited[(i,j)] = True

numOfIslands_helper(arr,i+1,j+1, visited)
numOfIslands_helper(arr,i+1,j, visited)
numOfIslands_helper(arr,i+1,j-1, visited)

numOfIslands_helper(arr,i,j+1, visited)
numOfIslands_helper(arr,i-1,j+1, visited)
numOfIslands_helper(arr,i,j+1, visited)

numOfIslands_helper(arr,i-1,j-1, visited)

numOfIslands_helper(arr,i-1,j, visited)

#visited[(i,j)] = True

return 1

def numOfIslands(arr):

r = len(arr)
c = len(arr[0])

#print(r)
#print(c)

# DFS
# keep tracks of nodes visited so far ( indexes visited so far)
# iterate from 00 --> r-1, c-1
# perform DFS at every element
# expand the island in all 8 directions
# (i+1, j+1), (i, j+1), (i+1, j), (i-1, j-1), (i, j-1), (i-1, j), (i+1, j-1), (i-1, j+1)
# pass any node if it's already visited or it's value is zero;
# key for i,j ==> (i,j) as key;

visited = {}

count = 0

for i in range(r):
for j in range(c):
#print(i,j)
count += numOfIslands_helper(arr, i, j, visited)

#print(visited)

return count

arr = [[0 for i in range(5)] for j in range(3)]

arr[0][1] = 1
arr[1][1] = 1
arr[2][1] = 1
arr[0][3] = 1
arr[1][4] = 1
arr[2][4] = 1

print(arr)

print(numOfIslands(arr))``````

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