Google Interview Question
Country: United States
Interview Type: In-Person
minor bug in the count method. It only works for squares. I should check for j < arr[i].length, not arr.length
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.
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.
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.
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?
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.
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?
^^ 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)
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.. 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.
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?
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
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.
it is 3.unless and until stated we shouldn't consider the extremities of columns or rows to check for adjacency.
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].
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
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;
}
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);
}
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);
}
}
- Anonymous October 18, 2012