CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person
More Questions from This Interview



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

Iterate through items of matrix: row * column
If point is not part of any visited area then start searching for new area

Create margin collection having single starting point. Mark starting point as visited in matrix.
Iterate through margin points.
Populate new margin with points accessible from current margin points, in order to avoid duplicates, mark new margin points as visited in matrix immediately.
Search for new margins till no accessible points exist.


JavaScript Implementation.

//Given a matrix consisting of 0's and 1's, find the largest connected component consisting of 1's.

var mat = [];
mat[0] = [1, 1, 0, 0, 0, 0, 0, 0, 0];
mat[1] = [1, 1, 0, 1, 1, 1, 1, 0, 1];
mat[2] = [0, 0, 0, 0, 0, 1, 0, 0, 1];
mat[3] = [1, 1, 1, 0, 0, 1, 1, 0, 1];
mat[4] = [1, 1, 0, 0, 1, 1, 1, 0, 1];
mat[5] = [1, 1, 1, 0, 0, 0, 0, 0, 1];

function findMaxArea(mat) {
	var visited = [];

	var directions = [
		{ horizontal: -1, vertical: 0 },
		{ horizontal: 0, vertical: -1 },
		{ horizontal: 1, vertical: 0 },
		{ horizontal: 0, vertical: 1 }
	];

	for (var row = 0; row < mat.length; row += 1) {
		visited[row] = [];
	}

	var bestArea = null;
	var bestSize = null;
	for (var row = 0; row < mat.length; row += 1) {
		for (var column = 0; column < mat[row].length; column += 1) {
			if (mat[row][column] == 1 && visited[row][column] != true) {
				var area = getArea(mat, visited, directions, { row: row, column: column });

				if (bestSize == null || area.length > bestSize) {
					bestArea = area;
					bestSize = area.length;
				}
			}
		}
	}

	return bestArea;
}

function getArea(mat, visited, directions, point) {
	var result = [];

	var margin = [point];
	visited[point.row][point.column] = true;

	while (margin.length > 0) {
		var newMargin = [];

		for (var mIndex = 0; mIndex < margin.length; mIndex += 1) {
			point = margin[mIndex];
			for (var dIndex = 0; dIndex < directions.length; dIndex += 1) {
				var direction = directions[dIndex];

				var row = point.row + direction.horizontal;
				var column = point.column + direction.vertical;

				if (row >= 0 && row < mat.length && column >= 0 && column < mat[0].length) {
					if (visited[row][column] != true) {
						if (mat[row][column] == 1) {
							newMargin.push({ row: row, column: column });
							visited[row][column] = true;
						}
					}
				}
			}
		}
		result = result.concat(margin);

		margin = newMargin;
	}
	return result;
}

var result = findMaxArea(mat);

- Andrey Yeliseyev March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LargestConnectedInMatrix {

    public static void main(String... args) {
        int[][]  k = new int[][] {
                {0, 0, 1},
                {0, 1, 1},
                {0, 0, 1}};
        new LargestConnectedInMatrix().getLargestConnectedMatrix(k);
    }

    public int getLargestConnectedMatrix(int[][] arr) {
        boolean [][] visited = new boolean [arr.length][arr[0].length];

        for (int l = 0; l < arr.length; ++l)
            for (int m = 0; m < arr.length; ++m)
                visited[l][m] = false;

        Set<List<Pair<Integer, Integer>>> s = new HashSet<>();

        for (int x = 0; x < arr.length; ++x) {
            for (int y = 0; y < arr.length; ++y) {
                if (visited[x][y]) continue;
                List<Pair<Integer, Integer>> current = new ArrayList<>();
                List<Pair<Integer, Integer>> next = new ArrayList<>();
                int code = arr[x][y];
                next.add(new Pair<Integer, Integer>(x, y));
                while (!next.isEmpty()) {
                    Pair<Integer, Integer> p = next.remove(0);
                    current.add(p);
                    int i = p.getFirst();
                    int j = p.getSecond();
                    visited[i][j] = true;

                    if (i-1 >= 0 && arr[i-1][j] == code && !visited[i-1][j])
                        next.add(new Pair<Integer, Integer>(i-1, j));
                    if (i+1 < arr.length && arr[i+1][j] == code && !visited[i+1][j])
                        next.add(new Pair<Integer, Integer>(i+1, j));
                    if (j-1 >= 0 && arr[i][j-1] == code && !visited[i][j-1])
                        next.add(new Pair<Integer, Integer>(i, j-1));
                    if (j+1 < arr.length && arr[i][j+1] == code && !visited[i][j+1])
                        next.add(new Pair<Integer, Integer>(i, j+1));

                }

                s.add(current);
            }
        }

        for (List<Pair<Integer, Integer>> l : s) {
            System.out.println(l);
        }
        return -1;
    }
}

- ElegantCode March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Union Find algorithm would be much better than brute force.

- summyungguy March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

way too much code guys way too much code
do a simple if(a[i][j]==1) a[i][j] = max(a[i-1][j],a[i][j-1) + 1 if its 4 connected
if its 8 connect then you need Union find both will result in O(n^2) and will be better than brute force because checking viisted nodes repeatedly is complex

- kkr.ashish March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it will work for Square 1's but not rectangle. The solution you are giving is already present on GeeksForGeeks

- byteattack May 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

way too much code guys way too much code
do a simple if(a[i][j]==1) a[i][j] = max(a[i-1][j],a[i][j-1) + 1 if its 4 connected
if its 8 connect then you need Union find both will result in O(n^2) and will be better than brute force because checking viisted nodes repeatedly is complex

- kkr.ashish March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution does not work. Here is code.
It does not count mat[3][2] & mat[1][6] items.

And it does not return items of result area as well.

var mat = [];
            mat[0] = [1, 1, 0, 0, 0, 0, 0, 0, 0];
            mat[1] = [1, 1, 0, 1, 1, 1, 1, 0, 1];
            mat[2] = [0, 0, 0, 0, 0, 1, 0, 0, 1];
            mat[3] = [1, 1, 1, 0, 0, 1, 1, 0, 1];
            mat[4] = [1, 1, 0, 0, 1, 1, 1, 0, 1];
            mat[5] = [1, 1, 1, 0, 0, 0, 0, 0, 1];

            function findMaxArea(mat) {
                var result = null;
                var mat2 = [];
                for (var row = 0; row < mat.length; row += 1) {
                    mat2[row] = [];

                    for(var column =0; column < mat[row].length; column+=1) {
                        if (mat[row][column] == 1) {
                            mat2[row][column] = 1 + (row - 1 >= 0 ? mat2[row - 1][column] : 0) + (column - 1 >= 0 ? mat2[row][column - 1] : 0);

                            if (result == null || result < mat2[row][column]) {
                                result = mat2[row][column];
                            }
                        }
                    }
                }
                return result;
            }

            var result = findMaxArea(mat);

- Andrey Yeliseyev March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Coordinate{
public int x;
public int y;
public Coordinate(int x, int y){
this.x = x;
this.y = y;
}
}

public int largestConnectedArea(int[][] a){
if(a == null || a.length == 0){
return 0;
}
List<List<Coordinate>> list = new ArrayList<List<Coordinate>>();
int m = a.length, n = a[0].length;
int[][] visited = new int[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < m; j++){
if(visited[i][j] == 1){
continue;
}

if(a[i][j] == 1){
Coordinate c = new Coordinate(i, j);
visited[i][j] = 1;
List<Coordinate> cur = new ArrayList<>();
cur.add(c);
search(visited, c, a, -1, cur);
list.add(cur);
}
}
}
int max = 0;
for (List<Coordinate> is : list) {
max = Math.max(max, is.size());
}
return max;
}
//0 from upside, 1 from downside, 2 from left, 3 from right
public void search(int[][] visited, Coordinate c, int[][] a, int direction, List<Coordinate> list){
int row = a.length, col = a[0].length;
int x = c.x, y = c.y;
if(direction != 0 && x - 1 >= 0 && visited[x - 1][y] == 0 && a[x-1][y] == 1){
visited[x - 1][y] = 1;
Coordinate c0 = new Coordinate(x - 1, y);
list.add(c0);
search(visited, c0, a, 1, list);
}

if(direction != 1 && x + 1 < row && visited[x + 1][y] == 0 && a[x+1][y] == 1){
visited[x + 1][y] = 1;
Coordinate c1 = new Coordinate(x + 1, y);
list.add(c1);
search(visited, c1, a, 0, list);
}

if(direction != 2 && y - 1 >= 0 && visited[x][y-1] == 0 && a[x][y-1] == 1){
visited[x][y-1] = 1;
Coordinate c2 = new Coordinate(x, y-1);
list.add(c2);
search(visited, c2, a, 3, list);
}

if(direction != 3 && y + 1 < col && visited[x][y+1] == 0 && a[x][y+1] == 1){
visited[x][y+1] = 1;
Coordinate c3 = new Coordinate(x, y+1);
list.add(c3);
search(visited, c3, a, 2, list);
}
}



public static void main(String[] args){
LargestConnectedArea lca = new LargestConnectedArea();
int[][] a = {
{1,0,1,1,1,0,0,0},
{0,1,0,1,1,0,1,0},
{0,1,1,0,0,1,0,0},
{1,1,1,0,0,1,0,0}

};
System.out.println(lca.largestConnectedArea(a));
}

- Anonymous March 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let say you have following:

[1, 1, 0, 0, 0, 0, 0, 0, 0];
[1, 1, 0, 1, 1, 1, 1, 0, 1];
[0, 0, 0, 0, 0, 1, 0, 0, 1];
[1, 1, 1, 0, 0, 1, 1, 0, 1];
[1, 1, 0, 0, 1, 1, 1, 0, 1];
[1, 1, 1, 0, 0, 0, 0, 0, 1];

int max_area = 0;

now start traversing each row from top to bottom. For each row, first replace 1 with the continuous 1's streak length for all 1's in the stream. Now, traverse the row again replacing each non-zero element a[i,j]=a[i,j]+a[i-1,j]. This process can be seen as:

[2, 2, 0, 0, 0, 0, 0, 0, 0];
[2, 2, 0, 4, 4, 4, 4, 0, 1]; first traversal of row-2
[0, 0, 0, 0, 0, 1, 0, 0, 1];
[1, 1, 1, 0, 0, 1, 1, 0, 1];
[1, 1, 0, 0, 1, 1, 1, 0, 1];
[1, 1, 1, 0, 0, 0, 0, 0, 1];

[2, 2, 0, 0, 0, 0, 0, 0, 0];
[4, 4, 0, 4, 4, 4, 4, 0, 1]; second traversal of row-2
[0, 0, 0, 0, 0, 1, 0, 0, 1];
[1, 1, 1, 0, 0, 1, 1, 0, 1];
[1, 1, 0, 0, 1, 1, 1, 0, 1];
[1, 1, 1, 0, 0, 0, 0, 0, 1];

[2, 2, 0, 0, 0, 0, 0, 0, 0];
[4, 4, 0, 4, 4, 4, 4, 0, 1]; 
[0, 0, 0, 0, 0, 1, 0, 0, 1]; first traversal of row-3
[1, 1, 1, 0, 0, 1, 1, 0, 1];
[1, 1, 0, 0, 1, 1, 1, 0, 1];
[1, 1, 1, 0, 0, 0, 0, 0, 1];

[2, 2, 0, 0, 0, 0, 0, 0, 0];
[4, 4, 0, 4, 4, 4, 4, 0, 1]; 
[0, 0, 0, 0, 0, 5, 0, 0, 2]; second traversal of row-3
[1, 1, 1, 0, 0, 1, 1, 0, 1];
[1, 1, 0, 0, 1, 1, 1, 0, 1];
[1, 1, 1, 0, 0, 0, 0, 0, 1];

Keep updating the max_area with max number seen so far. This will be the max area at the end of the process

- AbhishekA August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

arrx = """
110000000
110111101
110000111
011100100
011000111
"""

def visit(arr, x, y, count=0):
   
    if arr[y][x] == '0':
        return count

    arr[y][x] = '0'
    count += 1
    for i in (-1, 1):
        if len(arr) > y + i and y+i >= 0:
            count = visit(arr, x, y+i, count)

    for i in (-1, 1):
        if len(arr[y]) > x + i and x+i >= 0:
            count = visit(arr, x+i, y, count)
    return count
 
def island(arrx):
    max_area = 0
    arr = filter(lambda x: x, arrx.splitlines())

    arr = [[j for j in i] for i in arr]
    for y in range(len(arr)):
        for x in range(len(arr[y])):
            area = visit(arr, x, y)
            if area > max_area:
                max_area = area
    return max_area

print island(arrx)

- champ August 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.


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