Google Interview Question SDE1s
Team: maps
Country: United States
it can be done faster by picking the number of iterations equal to the number of elements in the smaller dimension.
Shouldn't this be O(m+n) rather than O(m*n)???
You are just iterating through the whole matrix once in this approach...
//let a[][] be the matix
public bool IsSymmetric (int[][] a)
for(int i = 0;i < n;i ++)
{
for(int j = 0; j< n-i; j++)
{
if(a[i][j] != a[n-i][n-j]);
{
return false;
}
}
}
return true;
1) it can be rectangular - not always square
2) n not defined
3) the outer for loop should go only till the middle (I know the inner one won't execute but those are still precious cycles).
int ifSameOnRotation(int a[R][C]){
int i,j;
for(i=0;i<=(R-1-i);i++){
for(j=0;j<C;j++)
if(a[i][j]!=a[R-1-i][C-1-j])
return 0;
}
return 1;
}
Concatenate
row 0 with row n-1,
row 1 with row n-2,
row 2 with row n-3,
...
row n/2-1 with row n/2
You get a matrix of 2*m columns and n/2 rows.
Now each row should be a palindrome in order to fulfill the requirement.
Of course you don't really need to create a new matrix.
On each loop iteration deal with one concatenated row.
bool is_the_same_when_rotated(bool a[], size_t rows, size_t cols)
{
bool bRes = true;
for (size_t i = 0; i <= (rows / 2) && bRes; i++)
{
for (size_t j = 0; j < cols; j++)
{
if (i == (rows / 2) && (j >= (cols / 2)))
{
break;
}
size_t currIdx = i * cols + j;
if (a[currIdx] != a[((rows * cols) - 1) - currIdx])
{
bRes = false;
break;
}
}
}
return bRes;
}
def is180RotatedEqual(matrix1, matrix2):
if not matrix1:
return not matrix2
if len(matrix1) != len(matrix1[0]):
return False
for i in xrange(len(matrix1)):
for j in xrange(len(matrix1)):
if matrix1[i][j] != matrix2[len(matrix1) - i - 1][len(matrix1) - j - 1]:
return False
return True
print is180RotatedEqual(
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]],
[[9, 8, 7],
[6, 5, 4],
[3, 2, 1]])
print is180RotatedEqual(
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]],
[[9, 8, 7],
[6, 5, 4],
[9, 2, 1]])
We should first ask from interviewer regarding 180 degree of rotation on the basis of x axis or y axis. In both the condition we have to only check whether the row or column are palindrome or not. We can check it in O(ROW*COL) time complexity by traversing each row or column ( on the basis of x and y axis constraints ) from start and end simultaneously.
for i = 1 to MAX_ROWS
while(MAX_ROWS - i + 1 > i)
for j = 1 to MAX_COLUMNS
while (MAX_COLUMNS -j + 1 > j)
if Matrix(i,j) != Matrix(MAX_ROWS - i + 1,MAX_COLUMNS -j + 1) then
message("Matrix not same when turned 180 deg")
break;
endif
endwhile
endfor
endwhile
endfor
def is180RotationSame(matrix):
lastRowsIndex=len(matrix)-1
lastColumnIndex=len(matrix[0])-1
for i in range (lastRowsIndex+1):
for j in range(lastColumnIndex+1):
if (i<=lastRowsIndex-i or j<=lastColumnIndex-j):
if(matrix[i][j]!=matrix[lastRowsIndex-i][lastColumnIndex-j]):
return False
else:
#print "Breaking at %d row and %d column"%(i+1,j+1)
return True
if __name__=='__main__':
#matrix=[[i for i in range(5)] for j in range(3)]
matrix=[[1,2,3,4],[2,6,5,4],[4,5,6,2],[4,3,2,1]]
print matrix
print is180RotationSame(matrix)
Launch two pointers Fwd and Bkw at the same time. Fwd is going in left-right/top-bottom direction and Bkw going in right-left/bottom-up direction. Compare values on every step and bail out if difference found. Terminate loop when Fwd == Bkw (i.e. they meet in the center).
- Anonymous June 06, 2013