## Facebook Interview Question for Software Engineer Interns

• 0

Interview Type: Phone Interview

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

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

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

}

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

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.