## Google Interview Question for Data Engineers

Country: United States

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

Algorithm : Iterate over the rows in O(num_row^2) and go through only the col indexes which differs by row indexes. If all are zero, increment the result.

``````def numberofSquares(matrix):

res, idx= 0,0

for row1_idx, row1 in enumerate(matrix):
for row_2idx,row2 in enumerate(matrix[first_row_idx+1:]):
for col1_idx in range(0,len(matrix)):
col2_idx = col_idx + (row2_idx-row1_idx)
if (col2_idx < len(matrix) and
not row1[col1_idx] and not row1[col2_idx]
not row2[col1_idx] and not row2[col2_idx]):
res += 1

return res``````

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

@DyingLizard, it looks like your solution assume
010
110
000
is a 3x3 square. Did I misunderstand your code?

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

``````bool check(bool mat[], int size, int srow, int scol, int h)
{
for (int i = srow; i < srow + h; i++)
for (int j = scol; j < scol + h; j++)
if (mat[i][j] == 1)
return 0;
return 1;
}

int countZeroSq(bool mat[], int size, int srow, int scol, int h)
{
if (srow == size - 1 || scol == size - 1|| srow + h > size || scol + h > size)
return 0;
int count = 0;
if (check(mat, size, srow, scol, h))
{
if (h > 1)
count++;
count += countZeroSq(mat, size, srow, scol, h + 1);
}
return count;
}

int countZeroSq(bool mat[], int size)
{
int count = 0;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if(mat[i][j] == 0)
count += countZeroSq(mat, size, i, j, 1);
}
}
return count;``````

}

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.

### 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.