Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
private static int[][] rotateMatrixBy90Degree(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i];
matrix[first][i] = matrix[last - offset][first];
matrix[last - offset][first] = matrix[last][last - offset];
matrix[last - offset][last] = matrix[i][last];
matrix[i][last] = top;
}
}
System.out.println("Matrix After Rotating 90 degree:-");
printMatrix(matrix, n);
return matrix;
}
#include<stdio.h>
int main()
{
int a[10][10], b[10][10];
int i, j, k, l, row, col;
printf("\nEnter the number of rows and columns\n");
scanf("%d%d", &row, &col);
printf("\nEnter the values\n");
for(i = 0; i <= row - 1; i++)
for(j = 0; j <= col - 1; j++)
scanf("%d", &a[i][j]);
for(i = 0; i <= row - 1; i++)
{
for(j = 0; j <= col - 1; j++)
printf("%d\t", a[i][j]);
printf("\n");
}
for(i = 0, k = row - 1; i <= row - 1; i++, k--)
for(j = 0, l = 0; j <= col - 1; j++, l++)
b[l][k] = a[i][j];
printf("\n\n");
for(i = 0; i <= col - 1; i++)
{
for(j = 0; j <= row - 1; j++)
printf("%d\t", b[i][j]);
printf("\n");
}
return 0;
}
Lets modify this question a bit, how can we do the same in by being more efficient in terms of space
public int[][] rotateMatrix(int[][] x){
int[][] m = new int[x[0].length][x.length];
for(int i=0; i<x[0].length; i++){
for(int j=0; j<x.length; j++){
// System.out.format("%4d",m[i][j]=x[j][x[0].length-1-i]); //rotate by 90 degree anticlockwise.
System.out.format("%4d",m[i][j]=x[x.length-1-j][i]); //rotate by 90 degree clockwise.
}
System.out.println();
}
return m;
}
void cyclic_rotate(int *a, int *b, int *c, int *d)
{
int temp;
temp = *a;
*a = *b;
*b = *c;
*c = *d;
*d = temp;
}
void rotate(int a[][SIZE])
{
int i, j;
for(i=0; i<(SIZE/2); i++)
{
for(j=0; j<(SIZE+1)/2; j++)
{
cyclic_rotate(&a[i][j], &a[SIZE-1-j][i], &a[SIZE-1-i][SIZE-1-j], &a[j][SIZE-1-i]);
}
}
}
The very easy algorithm for rotation of the matrix by 90 degrees we will be following the algorithm given below:
1. We will first find the transpose of the matrix.
2. We will then reverse the columns or swap them and we will finally get the rotated matrix.
Implementation:
void transpose(int mat[R][C], int R, int C){
for(int i = 0; i < R; i++){
for(int j = i; j < C; j++){
swap(mat[i][j], mat[j][i];
}
}
}
void swapp(int mat[R][C], int R, int C){
for(int i = 0; i < C; i++){
for(int j = 0, k = R - 1; j < k; i++, k--){
swap(mat[j][i], mt[k][i]);
}
}
Following is for rotating in 90 degree clockwise:
1. Transpose the matrix
2. Reverse each row
Psedocode:
- ama March 22, 2012