Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

Here is an approach walking along the diagonal. General approach:

1. Start in the bottom left corner.
2. Subtract row index until you find a 0.
3. Add the row index + 1 to you total and move one column right.
4. Repeat from step 2 until you find the top or right edge of the matrix.

This is worst case O(N) since the length of the diagonal is proportional to N.

Code:

private int countNumZeroes(int[][] matrix) {
    int row = matrix.length - 1, col = 0, numZeroes = 0;
    while (col < matrix[0].length) {
      while (matrix[row][col] != 0) {
        if (--row < 0) {
          return numZeroes;
        }
      }
      // Add one since matrix index is 0 based
      numZeroes += row + 1;
      col++;
    }
    return numZeroes;
  }

- Johnie June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 8 vote

I have an O(log n) solution.

Binary search the middle row. Now you know the x and y of the middle 1. We break the matrix into four rectangular sections. Everything on the upper left of the middle 1 must be a 0. Everything on the bottom right of the middle 1 must be a 1. This leaves the bottom left and the upper right. Those two sections are smaller versions of the original problem so we recurse on those sections. Performing the binary search takes (log n), and since we are breaking the problem in half each time, there will be (log n) recursions. The next recursions perform a binary search taking time (log n/2), (log n/4), etc. This results in O( log n + log n/2 + log n/4 + ...) which amortizes to O(log n).

- zd June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if you have something like this

[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]

Would the above work

- babalonso7 July 17, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple python solution based on binary search

def count_zeros(m):                                                                                 
    high = len(m[0]) - 1                                                                            
    count = 0                                                                                       
    for i in range(len(m)):                                                                         
        low = 0                                                                                     
        if m[i][high] == 0:                                                                         
            # All zeros in this row                                                                 
            count += high + 1                                                                       
            continue                                                                                
        if m[i][low] == 1:                                                                          
            # No more zeros around                                                                  
            break                                                                                   
        while low <= high:                                                                          
            # Binary search for the                                                                 
            # first one of the row                                                                  
            mid = (low + high)/2                                                                    
            if m[i][mid] == 1:                                                                      
                high = mid - 1                                                                      
                if m[i][mid - 1] == 0:                                                              
                    break                                                                           
            else:                                                                                   
                low = mid + 1                                                                       
        count += high + 1                                                                           
    return count                                                                                    
                                                                                                    
                                                                                                    
assert count_zeros([[0, 0, 1],                                                                      
                    [0, 1, 1],                                                                      
                    [1, 1, 1]]) == 3                                                                
assert count_zeros([[0, 0],                                                                         
                    [0, 0]]) == 4                                                                   
assert count_zeros([[1, 1, 1, 1],                                                                   
                    [1, 1, 1, 1],                                                                   
                    [1, 1, 1, 1],                                                                   
                    [1, 1, 1, 1]]) == 0                                                             
assert count_zeros([[0, 0, 0, 0],                                                                   
                    [0, 0, 0, 1],                                                                   
                    [1, 1, 1, 1],                                                                   
                    [1, 1, 1, 1]]) == 7                                                             
assert count_zeros([[0]]) == 1                                                                      
assert count_zeros([[1]]) == 0

- Anonymous June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int getNumOfZeroes(int a[][]) {
    int count=0;
    for(int i=0; i < a.length; ++i) {
      int index=binarySearchUpper(a[i]);
      if(index > -1) {
        count += index;
      }
    }
    return count;
  }

  static int binarySearchUpper(int[] a) {
    int low=0;
    int high=a.length;
    int lower=-1;
    for(int i =0; i < a.length; ++i) {
      int m = (low + high) / 2;
      if(a[m] == 0) {
        low = m + 1;
        lower = m;
      } else {
        high = m - 1;
      }
    }
    return lower+1;
  }
 
  public static void main(String... args) {
 int[][] a = { {0,0,1}, {0,1,1}, {0,1,1}};
    System.out.println(getNumOfZeroes(a));
  }

- Vishal June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int getNumOfZeroes(int a[][]) {
int count=0;
for(int i=0; i < a.length; ++i) {
int index=binarySearchUpper(a[i]);
if(index > -1) {
count += index;
}
}
return count;
}

static int binarySearchUpper(int[] a) {
int low=0;
int high=a.length;
int lower=-1;
for(int i =0; i < a.length; ++i) {
int m = (low + high) / 2;
if(a[m] == 0) {
low = m + 1;
lower = m;
} else {
high = m - 1;
}
}
return lower+1;
}

- VishalS June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My initial solution was just to do a binary search in each row, and add the index of the first 1 to a count of zeros - O(n * log n).

My second solution was to preform two binary searches. First a horizontal one, then a vertical one on the column returned by the horizontal one. This yields a section of the matrix that is all zeros, which we can add to the count by multiplying the horizontal and vertical indices. We then decrement the column, increment the row, and recurse. This solution performs better in the case of many zeros (for example, a matrix of all 0s takes log(n) instead of n*log(n)), but I believe this remains O(n * log n) in the worst case.

If we had a matrix with a diagonal separating the 0s and 1s, then we do log(n) + log (n-1) + ... + log(1) = log (n * (n - 1) * ... * 1) = log(n!) = n * log (n) work.

- gm June 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getZeroCount(int (*arr)[MAX_SIZE], int size)
{
	int ret = 0;
	int x=0;
	int y=0;
	//find last 0 of 1st row.
	for(int i=0;i<size;i++)
	{
		if(arr[x][i] > 0 || i == size-1)
		{
			y = i;
			ret = i;
			if(i == size-1) ret++;
			x++;
			break;
		}
	}

	//move backward until find 0 of next row.
	while(x > -1 && y > -1 && x < size && y < size)
	{
		if(arr[x][y] > 0)
		{
			y--;
		}
		else if(arr[x][y] == 0)
		{
			ret += y + 1;
			x++;
		}
	}
	return ret;
}

- jihow June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if you just sum each of the arrays that form the matrix and substract "n"?

import operator

def main():
    matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
    matrixLength = len(matrix)
    result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
    print result

def getZeros(array, length):
    return length - reduce(operator.add, array)

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

What if you just sum each of the arrays that form the matrix and substract "n"?

import operator

def main():
    matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
    matrixLength = len(matrix)
    result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
    print result

def getZeros(array, length):
    return length - reduce(operator.add, array)

- Alberto Romero June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if you just sum each of the arrays that form the matrix and substract "n"?

import operator

def main():
    matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
    matrixLength = len(matrix)
    result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
    print result

def getZeros(array, length):
    return length - reduce(operator.add, array)

- Alberto Romero June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
public class ArraryMatrix {
	static int count;
	/**
	 * @param args
	 */
	public static int Mat(int arr[][],int size){
		
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				if(arr[i][j]==0){
					count+=1;
				}
			}
		}
	return count;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the dimension of the Array:-");
		int len=sc.nextInt();
		int [][]A=new int[len][len];
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){
				System.out.println("Enter the element:["+i+"]"+"["+j+"]");
				A[i][j]=sc.nextInt();
				
			}
		}
		int score=Mat(A,len);
		System.out.println("There are --"+score+"---No of zros are present in the given Matrics");
		
		
	}

}

- nandagirisaipranay June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can start off with the top row, counting from the right end until we hit a 0. Let's say we hit k1 number of 1's before hitting a 0. Total number of 1's in row1 = k1.

Now for the next row, we know that every column is also sorted, so no column from the end can have a 0 if it has a 1 in this row. So, we can safely skip k1 number of 1's and start from there until we hit a 0. Let the new number of 1's hit be k2. Total number of 1's in row1+row2 = sum so far + (previous k + new k) = (k1) + (k1+k2) = 2k1+k2

Continuing, we can go down, and we'll be amassing the number of 1's. Next row, we get total 1's = 3k1+2k2+k3, and so on. The total 1's in the end would be n*k1+(n-1)*k2+...+2*k{n-1}+kn.

Time wise, the total counting is k1+k2+...+kn = actually the whole length of one row = n, since if we completely cover a lot of elements in one row, the elements to cover for the next row become lesser and lesser, and the maximum we can cover is only n elements horizontally. Thus, time is O(n).

This can be optimized by binary search. Applying that on first row to find k1 yields us log(n) steps for row1, log(n-k1) steps for row2 and so on. Total = log(n)+log(n-k1)+log(n-k1-k2)+...+log(n-k1-k2...-kn).

- Ashish June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numZeros(int[][] m)
{
	if(m==null||m.length==0||m[0].length==0)
	{
		return 0;
	}
	
	int r=0;
	int c=m[0].length-1;
	int total=0;
	while(r<m.length)
	{
		if(c<0)
		{
			r++;
			c=m[0].length-1;
		}else
		{
			if(m[r][c]==1)
			{
				c--;
			}else{
				if(c==m[0].length-1||m[r][c+1]==1)
				{
					total+=c+1;
					r++;
				}else{
					c++;
				}
			}
		}
	}
	return total;
}

//Worst case: O(N) where N is the number of rows.

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

public int numZeros(int[][] m)
{
	if(m==null||m.length==0||m[0].length==0)
	{
		return 0;
	}
	
	int r=0;
	int c=m[0].length-1;
	int total=0;
	while(r<m.length)
	{
		if(c<0)
		{
			r++;
			c=m[0].length-1;
		}else
		{
			if(m[r][c]==1)
			{
				c--;
			}else{
				if(c==m[0].length-1||m[r][c+1]==1)
				{
					total+=c+1;
					r++;
				}else{
					c++;
				}
			}
		}
	}
	return total;
}

Worst case: O(N) where N is the number of rows.

- divm01986 June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any tips for the O(log N) solution? I'm having a hard time visualizing how to find information that to me seems linear in the worst case in logarithmic time without relying on some assumption of fast matrix operations or other things.

- Johnie June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Divide the matrix into 4 quadrants.
2. Check the element at origin.
3. If it is 1, then we can eliminate the right bottom quadrant, as it will have only 1s.
4. If it is 0, then we can eliminate the left top quadrant, as it will have only 0s.
5. Now we are left with 3 quadrants each of size 1/4 of original matrix.
6. Repeat the process for these.
7. The base case can be a 2 x 2 matrix, or a single row of column.

This is f(n) = 1 + 3 * f(n/4), by Master's theorem, this is O(n ^ log(3 to base 4). Which is better than O(n).

- devxeq June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getZeroCountDivide(int x1, int y1, int x2, int y2, int (*arr)[MAX_SIZE])
{
	if(arr[x1][y1] == 0 && arr[x2][y2] == 0) return (x2-x1+1) * (y2-y1+1);
	if(arr[x1][y1] == 1 && arr[x2][y2] == 1) return 0;

    int result = 0;
	
	int row = x2-x1;
	int column = y2-y1;

	if(row == 0)
	{
		//just a few. count!
		for(int i=y1;i<=y2;i++)
		{
			if(arr[x1][i] == 0) result ++;
		}
		return result;
	}
	if(column == 0)
	{
		//just a few. count!
		for(int i=x1;i<=x2;i++)
		{
			if(arr[i][y2] == 0) result ++;
		}
		return result;
	}

	return getZeroCountDivide(x1, y1, x1 + (row / 2), y1 + (column / 2), arr) 
		+ getZeroCountDivide(x1 + (row / 2) + 1, y1 + (column / 2) + 1, x2, y2, arr)
		+ getZeroCountDivide(x1, y1 + (column / 2) + 1, x1 + (row / 2), y2, arr)
		+ getZeroCountDivide(x1 + (row / 2) + 1, y1, x2, y1 + (column / 2), arr);

}

O(logN?) ?

- jihow June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

devxeq, comments aren't working so I'll ask here:

Since N is the length of each side, would your reduction not be

f(n) = 1 + 3 * f(n/2) ?

- Johnie June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

binary search from top-left to bottom-right to find 1, it will be located at X, where 0<=X<N. At this point you have X+X zeros, plus you need to recursively check right-top and top-bottom sections from X for extra zeros using similar technique. For right-top do binary search along top row to find 1, it will be located at Y, where X<=Y<N. So far with log n you will know how many 1s there in the right-top section: X*(N-Y). Then, recursively check rectangle bounded by X,0 and Y,X where left-bottom and right-top corners have zeros. Not sure though if the extra recursion increases log n complexity though.

- pavelp June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Johnie,

You're right, the n in my solution should be number of elements in the matrix and not the number of rows/columns.
And number of elements is in the order of N^2. So we're back to square one.

- devxeq June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is what I think, you can do it with recursion as below with O(logN):
1. First check position (0,0) == 1, if true, then quit with Number of Zeros = 0; else step 2.
2.

FindZeros(N,N){
if position (N,N) == 0, then quit with 
    Number of Zeros = N*N; 
else,
     if(N-1,N)==0  then 
	{
        NumberOfZeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1) ;
	}
    else if(N,N-1) == 0 then
	{
        NumberOfZeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N) ;
	}
else{
	FindZeros(N-1,N-1);
	}
}

- Liju George June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.

FindNumberOfZeros(N)
{
if(N,N)==0, then 
return  Number of Zeros = N*N;
else if (N-1,N) == 0 then,
 return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
  return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else 
  return FindNumberOfZeros(N-1);
}

- Liju George June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.

FindNumberOfZeros(N)
{
if(N,N)==0, then 
return  Number of Zeros = N*N;
else if (N-1,N) == 0 then,
 return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
  return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else 
  return FindNumberOfZeros(N-1);
}

- Liju George June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- Liju George June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.

FindNumberOfZeros(N)
{
if(N,N)==0, then 
return  Number of Zeros = N*N;
else if (N-1,N) == 0 then,
 return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
  return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else 
  return FindNumberOfZeros(N-1);
}

- liju.george47 June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    enum values{
        zero =0,
        one = 1,
    };
    vector<vector<values>> matrix = {{zero,zero,zero,one,one},{zero,zero,one,one,one},{zero,zero,one,one,one},{one,one,one,one,one}};
     for (short int i = 0;i<matrix.size();i++){
        cout<<"["<<i<<"]=> ";
        for (short int j = 0;j<matrix[i].size();j++){
            cout<<"["<<matrix[i][j]<<"]";
        }
        cout<<endl;
    }
    int posFirstOne = matrix[0].size();
    int cont = 0;
    for (short int i = 0;i<matrix.size();i++){
        for (short int j = 0;j<posFirstOne;j++){
            if (matrix[i][j]==one){
                posFirstOne = j;
                break;
            }else{
                cont+=1;
            }
        }
    }
    cout<<"Zeros:"<<cont<<endl;
    return 0;
}

- Solution in C++ June 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here are 2 methods in Python:

matrix = [[0, 0, 0, 1 ], [0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 1, 1]]

#method 1
print sum([len(eachArr)-sum(eachArr) for eachArr in matrix])

#method 2

from operator import add
length = len(matrix)
if matrix[length-1][length-1]==0:
    print length**2
elif matrix[0][0]==1:
    print 0
else:
    total=0
    for i in range(length-1,-1,-1):
        if matrix[i][0]==0:
            #total+=(length - sum(matrix[i]))
            total+=(length - reduce(add, matrix[i]))
        else:
            pass
        
    print total

- murali June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

implementation in Python

matrix = [[0, 0, 0, 1 ], [0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 1, 1]]
#method 1
print sum([len(eachArr)-sum(eachArr) for eachArr in matrix])

#method 2

from operator import add
length = len(matrix)
if matrix[length-1][length-1]==0:
    print length**2
elif matrix[0][0]==1:
    print 0
else:
    total=0
    for i in range(length-1,-1,-1):
        if matrix[i][0]==0:
            #total+=(length - sum(matrix[i]))
            total+=(length - reduce(add, matrix[i]))
        else:
            pass
        
    print total

- murali June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Go diagonally from bottom right until it hits '0' (i,j). This eliminates the (I,j) block and adds this dimension to count. Then, increment i for as long as it is '0', add this to count. Then, increment j for as long as it is '0', add this to count.

long MatrixPatternCount(vector<vector<long>>& data)
{
	long i = data.size() - 1, j = data[0].size() -1;
	long count = 0;
	for (; i >= 0 && j >= 0; i--, j--)
		if (!data[i][j]) {
			count = (i + 1) * (j + 1);
			break;
		}
	long ii = i, jj = j;
	if (ii < data.size() - 1)
		for (; j >= 0; j--)
			for (i = ii + 1; !data[i][j]; i++)
				count++;
	i = ii;
	if (jj < data[ii].size() - 1)
		for (; i >= 0; i--)
			for (j = jj + 1; !data[i][j]; j++)
				count++;
	return count;
}

- funcoolgeek June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@zd Your total complexity is O(nlogn), not O(logn). The complexity of the binary search doesn't change when the search space gets smaller since O(log(n/2)) = O(log(1/2 * n)) = O(log(1/2) + log(n)) = O(constant + log(n)) + O(log(n)). Also, you end up doing the binary search O(n) times, so your total complexity is O(nlogn)

- Anonymous June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void calculateElemNum(int **mat, int n, int m, int el)
{   
    printf("Number of '%ds' in matrix:\t", el);
    
    int cnt = 0;
    
    int start = n - 1;
    
    for (int i = 0; i < m; i++) {
        
        for (int j = start; j >= 0; j--) {
            if (mat[i][j] == el) {
                cnt += j + 1;
                start = j;
                if (j == 0)
                    goto END;
                else
                    break;
            }
        }
    }
END:
    printf("%d\n", cnt);
}

- Luigi June 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I can solve this in O(logn*logn).
1. binary search on the diagonal finding the last cell containing 0. -->O(logn)
2. then we can divide the matrix into 4- one contain only 0, one contain only 1 and in the other 2 we need to count the zeroes. we can run the first step on the 2 matrix and sum all together. each time narrow the matrix size in at least 2.

- seffy July 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The optimal solution is O(n).
This cannot be done in O(log n), and it's not difficult to prove this.
One proof is to note that the contour separating the 0 and 1 regions could have up to n segments. To determine the size of each area we need to know the location of the segments, which cannot be done in O(log n) since there are O(n) segments.

- gen-y-s July 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

log(N):
1) Binary search along the diagonal to find "change" point : log(N)
2) Binary search along the row found in (1) to find "change" point in that row: log(N)
3) Binary search along the column found in (1) to find "change" point in that column: log(N)

- potential.himanshu4u July 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int count(int[][] m) {
		int res = 0;
		int w = m[0].length, h = m.length;
		int i = h - 1, j = 0, count = 0;
		while(i >= 0 && j < w) {
			if(m[i][j] == 0 && j == w - 1) {
				res += w;
				i--;
				continue;
			}
			if(m[i][j] == 1) {
				res += j;
				i--;
			}else {
				j++;
			}
		}
		return res;
	}

- cqz93 July 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
void main()
{
	int i, j, row, col = 0;
	int arr[50][50];
	clrscr();
	printf("Enter no of rows:");
	scanf("%d",&row);
	printf("Enter no of columns:");
	scanf("%d",&col);
	for(i = 0; i < row; i++)
	{
		for(j = 0; j < col; j++)
		{
			printf("Enter value for row %d and column %d",i,j);
			scanf("%d", &arr[i][j]);
		}
	}
	for(i = 0; i < row; i++)
	{
		printf("\n");
		for(j = 0; j < col; j++)
		{
			printf("%d ",arr[i][j]);
		}
	}
	getch();
}

- Anonymous July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best runtime complexity we can achieve is n*lg(n), the following code is written in java, using a binary search to find the biggest 0 index in a row.

public int findZeroCount(int[][] matrix) {
        if (matrix == null || matrix.length < 1) {
            return 0;
        }

        int sumZeros = 0;
        int indexOfLastZero = matrix[0].length;

        for (int i = 0; i < matrix.length; i++) {
            indexOfLastZero = findIndexOfLastZero(matrix[i], 0, indexOfLastZero);
            if (indexOfLastZero >= 0) {
                sumZeros += (indexOfLastZero + 1);
            }
        }

        return sumZeros;
    }


    private int findIndexOfLastZero(int[] array, int left, int right) {
        int mid = 0;
        while (right - left > 1) {
            mid = (left + right) / 2;
            if (array[mid] == 0) {
                left = mid;
            } else {
                right = mid;
            }
        }


        if (array[right] == 0) {
            return right;
        } else if (array[left] == 0) {
            return left;
        } else {
            return -1;
        }

    }


    @Test
    public void testCountZeros() {
        int[][] data = new int[][]{
                {0, 0, 1},
                {0, 1, 1},
                {1, 1, 1}
        };

        int zeroCount = findZeroCount(data);
        assertTrue(zeroCount == 3);

}

- eric.liu.developer July 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class matrix {
public static void main(String args[]){
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt(); int count =0;
	int [][] array = new int[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
		{
			array[i][j] = sc.nextInt();  
			if (array[i][j] == 1)
				break;
			else count = count + 1;
		}
		sc.nextLine();
	}
	System.out.print(count);
			
}
}

- Anonymous July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class matrix {
public static void main(String args[]){
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt(); int count =0;
	int [][] array = new int[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
		{
			array[i][j] = sc.nextInt();  
			if (array[i][j] == 1)
				break;
			else count = count + 1;
		}
		sc.nextLine();
	}
	System.out.print(count);
			
}
}

- Shruthi Prakash July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C- Implementation

int main()
{
   int matrix[4][4]={ {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 1, 1, 1},
                      {0, 1, 1, 1},
                };
   int row = 3 ; 
   int col = 0;
   int zero = 0;
   
   while( col < 4 )
   {
        if( matrix[col][row] == 0 )
        {
            zero += ( row + 1 );
            col++;
        }
        else
        {
            row--;
        }
   }

    printf("Zero:%d\n", zero);

}

- som July 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int countZero(vector<vector<int>> table){
    //Find the most right 0 of the first row
    int col = 0; 
    int res = 0;
    while (col < table.size() && table[1][col] == 0) col++;
    if (col == 0) return 0; res += col; col--;
    for (int i = 1; i < table.size(); i++){
   	while(col > -1 && table[i][col] == 1) col--;
           res += col + 1;
           if (col == -1) return res;
   }
}

- vucuong020195 July 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int count0s(int[][] mat){
			int i=0; 
			int j=mat.length-1;
			int count = 0;
			while(i < mat.length && j > -1){
				if(mat[i][j] == 0){
					count = count + j + 1;
					i++;
				}else{				
					j--;
				}
			}
			return count;
		}

- Manju July 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my first version, and the complexity is O(n * log(n)):

// array contains n elements
int CountZeroCountInArray(const int *array, int n) {
    // Range is [begin, end)
    int begin = 0;
    int end = n;

    while (begin < end) {
        int middle = (begin + end) / 2;
        if (array[middle] != 0) {
            end = middle;
        } else {
            begin = middle + 1;
        }
    }

    // Should begin == end, and is the index of first non-zero element
    return begin;
}

// matrix contains n * n elements
int CountZeroCountInMatrix(const int *matrix, int n) {
    int zeroCount = 0;

    int lineEnd = n;
    for (const int *line = matrix; line < matrix + n * n; line += n) {
        lineEnd = CountZeroCountInArray(line, lineEnd);
        zeroCount += lineEnd;
    }

    return zeroCount;
}

This is my second version. It doesn't use a binary search, but the complexity is O(n). Interesting!

// matrix contains n * n elements
int CountZeroCountInMatrix(const int *matrix, int n) {
    int zeroCount = 0;

    int lineEnd = n;
    for (const int *line = matrix; line < matrix + n * n; line += n) {
        while (line[lineEnd - 1] != 0) {
            lineEnd--;
            if (lineEnd == 0) {
                return zeroCount;
            }
        }
        zeroCount += lineEnd;
    }

    return zeroCount;
}

Here is my test code:

int main() {
    const int matrix1[] = {
        0, 0, 1,
        0, 1, 1,
        1, 1, 1
    };

    // 3
    std::cout << CountZeroCountInMatrix(matrix1, 3) << std::endl;


    const int matrix2[] = {
        0, 0,
        0, 0
    };

    // 4
    std::cout << CountZeroCountInMatrix(matrix2, 2) << std::endl;


    const int matrix3[] = {
        0, 0, 0,
        0, 1, 1,
        0, 1, 1
    };

    // 5
    std::cout << CountZeroCountInMatrix(matrix3, 3) << std::endl;

    return 0;
}

- SW July 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your solution is correct with tiny correction.
" Everything on the upper left of the middle 1 : not exactly." not exactly.

O(N,N) = 3* O(N/2,N/2);
O(N^2) = 3 *O(N/4) + 1;

O(2logN/log(4/3)) --> O(logN).

int count(const vec2dint &A, int x, int y, int x1, int y1)
{
  if (x > x1 || y > y1) return 0;
  if (A[x][y] == 1) return 0;
  if (A[x1][y1] == 0) return (x1-x+1) * (y1-y+1);

  int xm = (x + x1)/2;
  int ym = (y + y1)/2;

  
  int t =  count (A, x,y,xm,ym) + count (A, xm+1,ym+1, x1, y1) + count(A, x, ym+1, xm, y1) + count(A, xm+1, y, x1, ym);

  int nc = 0;
  for (int i = x; i <= x1; ++i)
    for (int j = y; j <= y1; ++j)
      if (A[i][j] == 0) nc ++;
  if (nc != t)
    {
      std::cout << "error " << nc << " " << t << "\n";
      exit(1);
    }
  
}

- lsquang July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Solution that depends on bit manipulation could be as follows:
i)Invert bits in every single row -> O(n) with the assumption that the bit mask operation takes constant time with fast processor.
ii)Return the least significant one in every row -> Should be another O(n)
iii) Number of zeros in every row = N - output of step # ii -> O(n)
iv) Add numbers
iv)

- Ahmed.Ebaid October 17, 2016 | 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