Google Interview Question


Country: United States
Interview Type: In-Person




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

@Test public void testFoo() {
        int[][] arr = {{1, 0, 0},
                       {1, 0, 1},
                       {0, 0, 0}};
        
        System.out.println("COUNT: " + count(arr));
    }
    
    int count (int[][] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                count += (mark(arr, i, j) > 1) ? 1 : 0;
            }
        }
        return count;
    }
    
    int mark(int[][] arr, int i, int j) {
        int count = 0;
        if (i >= 0 && j >= 0 && i < arr.length && j < arr[i].length && arr[i][j] == 1) {
            count++;
            arr[i][j] = -1;
            count += mark(arr, i + 1, j);
            count += mark(arr, i - 1, j);
            count += mark(arr, i, j + 1);
            count += mark(arr, i, j - 1);
        }
        return count;
    }

- Anonymous October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

minor bug in the count method. It only works for squares. I should check for j < arr[i].length, not arr.length

- Anonymous October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also change count += (mark(arr, i, j) > 1) ? 1 : 0; to check >= 1

- JustCoding October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Similar questions :

careercup.com/question?id=14428676

In this question, it is considered as 8 connected component.

- Psycho October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

Idea:
iterate over each element in the matrix and
Do for each element that is 1
if all of its neighbors are 0, count=count+1,
otherwise, overwrite the value in current index by 0 and move to next index in the matrix.

count is the desired result.
Should work in O(n*m) time.

- Epic_coder October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

do you mean for each element that is 1?
i think we don't need to overwrite the value in the current index by 0. instead of checking all neighbors, we just need to check the left one and the above one.

- gnahzy October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant for each element that is 1. And yes, If we are scanning from left to right, we just need to check the right and bottom neighbor.

- Epic_coder October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have two votes, but I think there is a bug. Correct me if I am wrong.

In the following case:

0 1 1 0
0 1 0 0

In the first step you ll change the matrix to be
0 0 1 0
0 1 0 0.
and the answer would be 2 for your algorithm, which is not correct.

Is that rite?

- Vincent October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right vincent, here is the modified approach:
iterate over each element in the matrix and
Do for each element that is 1
if none of the neighbors is 2, count=count+1 and overwrite the value in current index by 2
if at least one of the neighbors is 2 , overwrite the value in current index by 2 and move to next index

If we are scanning from left to right we just need to check right and bottom neighbor.

count is the desired result.
Should work in O(n*m) time.

- Epic_coder October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

e.g.

101
101
111

You'll be counting two groups since the bottom row doesn't get processed until after you've incrememted the count. Or am I missing something?

- MrJava October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^^ You are right.

For making this to work, we'll have to flip all the 1s in a group when we find the first 1 in a group. A recursive function could be written to keep flipping all the neighbor ones. So,

Do for each element that is 1
--if all of its neighbors are 0, count=count+1,
--otherwise, count=count+1 and call flipbits()

flipbits() would flip all the 1s in a group when we find the first 1 in the group.
flipbits(i,j){
bit(i,j)=0;
if(bit(i+1,j)==1) flipbits(i+1,j);
if(bit(i,j+1)==1) flipbits(i,j+1);
if(bit(i,j-1)==1) flipbits(i,j-1);
if(bit(i-1,j)==1) flipbits(i-1,j);
return;
}

count is the result.

I think it's still O(n*m)

- Epic_coder October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't understand why we need to flip. why just scan in top-down left-right way and check the upper and left one is 1 or not when it is 1 itself, if it is not, count++. And we can prove it.
Suppose we get the group information of last line already, for every "1" element in the current line, we first check the left one, if it is also 1,then they are in the same group, we do not need to create a new group; then we check the upper one the same way. If they are both 0, then we need to create a new group, so count++.

- robert October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

robert.. ur approach will not work for the following case:

1 0 0 1
1 1 1 1

while scanning the first line you will create two groups and count them as 2. While its actually just one group.

- Tomonfire October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

epic_coder- what is the complexity of flipbits()
both time and space

- Tomonfire October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tomonfire,
The space complexity depends on what approach you use, recursive or iterative. It would be same as the space complexity of BFS.
Time complexity would be O(1) amortized.

- Epic_coder October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

diagonal not considered?

in this example:
1 1 0 0
0 0 1 1
0 0 0 0
1 1 1 1

what is the answer? 2 groups? or 3 groups?

- JustCoding October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3

- himanshu6589 October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry´╝îI don't know which 3 is counted here. Could you please explain to me ? Thank you

- weiwuwei October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I replaced the 1s above with their group# so you can see why there are 3 groups.

1 1 0 0
0 0 2 2
0 0 0 0
3 3 3 3

- Sunny December 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is the question?

- Loler October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not considering diagonals

import numpy as np

a = np.array([ [ 0 , 0, 0, 1 ],
               [ 0,  0, 1, 1 ],
               [ 1,  0, 0, 1 ],
               [ 1,  1,  1, 0 ] ])

v = np.array ([ [ 0 , 0, 0, 0 ],
               [ 0,  0, 0, 0 ],
               [ 0,  0, 0, 0 ],
               [ 0,  0,  0, 0 ] ])


def add_neigbours(i,j, l):

    n1 = ( i-1, j )
    n2 = ( i, j+1 )
    n3 = ( i+1, j )
    n4 = ( i, j-1 )

    n = [ n1, n2, n3, n4]
    for n1 in n:
        if ( n1[0] >= 0 and n1[0] <= 3
             and n1[1] >=0 and n1[1] <= 3 ):
            if v[n1] == 0 and a[n1] == a[i,j]:
                v[n1] = 1
                l.append(n1)

def process(l):
    while ( len(l) > 0 ):
        i,j = l.pop()
        add_neigbours(i,j, l)


if __name__ == '__main__':
    count=0
    l = list()
    for i in range(0, 4):
        for j in range(0,4):

            if v[i,j] == 0:
                count = count + 1
                add_neigbours(i,j,l)
                process(l)



    print count

- betacod3r October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

assume we have n adjacent 1. If any of the adjacent 1's are considered as a group, the total number of groups of these n adjacent 1 is (n-1)+...1=n(n-1)/2.

So all we have to do is get the block of 1's from the matrix. A simple method is to iterate over the matrix horizontally and vertically once. If the matrix is m*n, it has O(m*n) complexity.

There should be optimal answers though.

- Judy October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

0 0 1 1
0 0 1 1
1 1 0 0

Would the above matrix have 2 groups or 3 groups

- Anonymous October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think 3.

- shashank October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry.. i think it should be 5.. 3 horizontal groups 2 vertical groups.

- shashank October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is 3.unless and until stated we shouldn't consider the extremities of columns or rows to check for adjacency.

- BeautifulCode October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

2

- Epic_coder October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

0 0 1 1
0 0 1 1
1 1 1 0

How many groups does this have? is it one ?

- bluesky October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1

- DigitalFire October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the number of groups depends on the definition of group.

If we consider all possible combinations, a grid which is all composed by 1, and has size
m*n (it has many ways to find there grids, one way is find a grid, and then replace all its elements as 0, then find another till all elements are 0.)
And m has [m+(m-1)+...+1=m*(m+1)/2], n has [n+(n-1)+...+1=n*(n+1)/2],
so the number of groups is [m*(m+1)/2] * [n*(n+1)/2].

- Gabriel October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi

- sharma October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use flood-fill algorithm

- pckben October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Should use BFS or DFS search strategy, and once an element is visited, we will mark it as visited. If we encountered a visited node, simply skipping it. Should be done no larger than O(m*n).

- Glenn October 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is the "connected component labeling" problem.

Search "Connected Component Labeling" in wikipedia for standard solutions

- yy October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution based on sets, without initialization.
Instead boundary conditions of (-1) are given

Starts with an empty list of sets
Runs on lines, check if upper/left neighbor are 1's
when it's a new "1" (no neighbors) -> append a new set with coordinates
when reaching a 1, check upper/left boundaries.
If has both, join sets if needed
otherwise, append to the set of upper or left "1" neighbor.


full code tested in Python

M = (1,1,1,0,1),\
        (1,1,1,0,1),\
        (1,0,0,1,0),\
        (0,0,0,1,0),\
        (1,1,1,0,0)
        
        
    countMatrixBlocks(M)
    
    
def countMatrixBlocks(M):
    printMatrix(M)
    allMembers = reduce(lambda a,b: a+b, M)
    if any( abs(m) > 1 for m in allMembers):
        print "Not a binary matrix"
        return
    
    mSets = []
    prevLineMembers = [-1]*len(M[0])
    for line, members in enumerate(M): 
        prevMember = -1
        for row, member in enumerate(members):
            upper = (prevLineMembers[row] == 1)
            prev = (prevMember == 1)
            
            if (member == 0):
                pass
                
            elif (not upper) and (not prev):
                mSets.append( sets.Set([(line, row)]) )
                
            elif (upper and prev):
                iPrev = [(line, row-1) in set for set in mSets].index(True)
                iUpper = [(line-1, row) in set for set in mSets].index(True)
                mSets[iPrev].add((line, row))
                if (iUpper != iPrev):
                    mSets[iPrev].union( mSets.pop(iUpper) )
                
            elif upper:
                iUpper = [(line-1, row) in set for set in mSets].index(True)
                mSets[iUpper].add((line, row))
                
            elif prev:
                iPrev = [(line, row-1) in set for set in mSets].index(True)
                mSets[iPrev].add((line,row))
                
            prevMember = member

        prevLineMembers = members

    print "# of blocks = %d" % (len(mSets))


def printMatrix(M):
    for line in M:
        print line

- Shacharm October 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

with output such as:
(1, 1, 1, 0, 1)
(1, 1, 1, 0, 1)
(1, 0, 0, 1, 0)
(0, 0, 0, 1, 0)
(1, 1, 1, 0, 0)
# of blocks = 4

Now add 1 in the (2,4) location...
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 1)
(1, 0, 0, 1, 0)
(0, 0, 0, 1, 0)
(1, 1, 1, 0, 0)
# of blocks = 2

- shacharm October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A typical BFS problem

int adjacent1s (const std::vector< std::vector<int> > & matrix)
{
	std::vector< std::vector<bool> > mark;
	for (int i = 0; i < matrix.size (); ++i)
	{
		std::vector<bool> tmp;
		for (int j = 0; j < matrix.at (0).size (); ++j)
		{
			tmp.push_back (false);
		}
		mark.push_back (tmp);
	}

	int retVal (0);
	std::queue<Cell> q;
	for (int i = 0; i < matrix.size (); ++i)
	{
		for (int j = 0; j < matrix.at (0).size (); ++j)
		{
			if (! mark.at (i).at (j) && 1 == matrix.at (i).at (j))
			{
				q.push (Cell (i, j));
				while (! q.empty ())
				{
					Cell current = q.front ();
					q.pop ();
					mark.at (current.m_x).at (current.m_y) = true;

					if (current.m_x + 1 < matrix.size () && ! mark.at (current.m_x + 1).at (current.m_y) && 1 == matrix.at (current.m_x + 1).at (current.m_y))
					{
						q.push (Cell (current.m_x + 1, current.m_y));
					}
					if (current.m_x > 0 && ! mark.at (current.m_x - 1).at (current.m_y) && 1 == matrix.at (current.m_x - 1).at (current.m_y))
					{
						q.push (Cell (current.m_x - 1, current.m_y));
					}
					if (current.m_y + 1 < matrix.at (0).size () && ! mark.at (current.m_x).at (current.m_y + 1) && 1 == matrix.at (current.m_x).at (current.m_y + 1))
					{
						q.push (Cell (current.m_x, current.m_y + 1));
					}
					if (current.m_y > 0 && ! mark.at (current.m_x).at (current.m_y - 1) && 1 == matrix.at (current.m_x).at (current.m_y - 1))
					{
						q.push (Cell (current.m_x, current.m_y - 1));
					}
				}
				++ retVal;
			}
		}
	}

	return retVal;
}

- meanmee November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Each time I encounter a 1, I use BFS to mark all the 1s in this group as -1. That way we can restore the matrix afterwards if needed and also avoid the need for extra memory.

static int numGroups(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  int count = 0;
  for(int i=0; i<rows; i++) {
    for(int j=0; j<cols; j++) {
      if(matrix[i][j] == 1) {
        count++;
        traverse(matrix, i, j);
      }
    }
  }
  return count;
}

static void traverse(int[][] matrix, int i, int j) {
  if(i<0 || j<0)
    return;
  if(i>=matrix.length || j>=matrix[0].length)
    return;
  if(matrix[i][j] != 1)
    return;
  matrix[i][j] = -1;
  traverse(matrix, i-1, j);
  traverse(matrix, i+1, j);
  traverse(matrix, i, j-1);
  traverse(matrix, i, j+1);
}

- Sunny December 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is detailed discussion about this problem at the blog:

codercareer.blogspot.com/2013/02/no-41-group-of-1s-in-matrix.html

- henghenghaha February 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution{
  public int Island(int[][] matrix){
    if(matrix == null) return 0;
    int row = matrix.length,column = matrix[0].length,res = 0;
    if(row*column == 0) return 0; 
    for(int i = 0 ; i < row ;i++) 
      for(int j = 0 ; j < column ; j++) 
        if(matrix[i][j] == 1)
          {
            res++;
            mark(matrix,i,j);
          }  
    return res;
  }
  public void mark(int[][] matrix, int x , int y){
  
    int row = matrix.length,column = matrix[0].length;
    if(x<0 || x>= row || y<0 ||y>=column) return;
    if(mark[x][y] == 1) mark[x][y] = 0;
    else return;
    mark(matrix,x+1,y+1);
    mark(matrix,x+1,y-1);
    mark(matrix,x-1,y+1);
    mark(matrix,x-1,y-1);
  }
}

- huihancarl September 04, 2013 | 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