Facebook Interview Question for Software Engineer Interns


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)

- learn2code February 18, 2018 | Flag Reply
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

- sir_max December 29, 2018 | Flag
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;
	}
	
}

- mvb13 February 16, 2018 | Flag Reply
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)

- reezo February 17, 2018 | Flag Reply
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;
}

- leonzakaim February 19, 2018 | Flag Reply
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;
    }

- denis.zayats February 19, 2018 | Flag Reply
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)

- Anonymous February 20, 2018 | Flag Reply
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)

- nonamesavailable February 20, 2018 | Flag Reply
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.

- Somal February 22, 2018 | Flag Reply
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.

- Somal February 22, 2018 | Flag Reply
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]).

- RumataEstor February 25, 2018 | Flag Reply
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 !

- Anonymous February 25, 2018 | Flag Reply
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

- seth@sethweidman.com March 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- Jitrapon Tiachunpun March 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hello

- Jitrapon Tiachunpun March 17, 2018 | Flag Reply
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);
        }
    }
}

}

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

- Michal F. April 01, 2018 | Flag Reply
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;
  }
}

- Abereham June 04, 2018 | Flag Reply
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];
    }

- Anatoliy July 02, 2018 | Flag Reply
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);
}

- Krupali Dedhia September 04, 2018 | Flag Reply
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);
}

- Krupali Dedhia September 04, 2018 | Flag Reply
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));
    }    
}

- Anonymous December 10, 2018 | Flag Reply


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