Facebook Interview Question
Software Engineer InternsInterview Type: Phone Interview
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)
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
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;
}
}
#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;
}
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;
}
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)
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)
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]).
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
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);
}
}
}
}
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);
}
}
}
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;
}
}
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];
}
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);
}
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);
}
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));
}
}
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)
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))
i didnt test this but i believe this is the answer.
- reezo February 17, 2018efficiency would be O(n)