Amazon Interview Question Software Engineer in Tests
Rotation here doesn't meant rotation in N-dimensional space. It means rotating the matrix, I don't think there's a simple matrix which can achieve this.
Career Cup book describes this problem. Here's my implementation for a sample 5x5 matrix:
#include <stdio.h>
#define N 5
int main() {
int m[N][N] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
int i, j, temp;
// Initial Matrix
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf("%2d ", m[i][j]);
}
printf("\n");
}
printf("-----------------------\n");
// Rotate Matrix
for(i=1; i<=N/2; i++) {
for(j=i; j<N+1-i; j++) {
temp = m[i-1][j-1];
m[i-1][j-1] = m[N-j][i-1];
m[N-j][i-1] = m[N-i][N-j];
m[N-i][N-j] = m[j-1][N-i];
m[j-1][N-i] = temp;
}
}
// Rotated Matrix
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf("%2d ", m[i][j]);
}
printf("\n");
}
getchar();
return 0;
}
one approach is using co-ordinate system. Based on degree of rotation, rotate the co-ordinates and the shift the origin.
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;
}
- Vir Pratap Uttam May 04, 2015private 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; }