Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Quoted from CareerCup 150, Question 1.6
The rotation can be performed in layers, where you perform a cyclic swap on the edges on
each layer In the first for loop, we rotate the first layer (outermost edges) We rotate the
edges by doing a four-way swap first on the corners, then on the element clockwise from the
edges, then on the element three steps away
Once the exterior elements are rotated, we then rotate the interior region's edges
1 public static void rotate(int[][] matrix, int n) {
2 for (int layer = 0; layer < n / 2; ++layer) {
3 int first = layer;
4 int last = n - 1 - layer;
5 for(int i = first; i < last; ++i) {
6 int offset = i - first;
7 int top = matrix[first][i]; // save top
8 // left -> top
9 matrix[first][i] = matrix[last-offset][first];
10
11 // bottom -> left
12 matrix[last-offset][first] = matrix[last][last - offset];
13
14 // right -> bottom
15 matrix[last][last - offset] = matrix[i][last];
16
17 // top -> right
18 matrix[i][last] = top; // right <- saved top
19 }
20 }
21 }
public static void quadRotate(int[][] matrix, int i0, int j0, int i1, int j1, int i2, int j2, int i3, int j3)
{
matrix[i0][j0]+=matrix[i1][j1]+matrix[i2][j2]+matrix[i3][j3];
matrix[i1][j1]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i2][j2]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i3][j3]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i0][j0]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
}
public static void rotate(int[][] matrix, int p0, int n)
{
if(n<=1)
{
return;
}
for(int i=0; i<n-1; i++)
{
quadRotate(matrix, p0, p0+i, p0+i, p0+n-1, p0+n-1, p0+n-1-i, p0+n-1-i, p0 );
}
rotate(matrix, p0+1, n-2);
}
// rotate 90 degrees clock wise
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
target[j][n-i-1] = a[i][j];
// rotate 90 degrees anticlock wise
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
target[m-j-1][i] = a[i][j];
Inplace (Working code!)
ideone.com/u1oS4
#include<stdio.h>
#define n 3
void printm(int (*a)[n])
{
int i,j;
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
}
void rotate(int (*a)[n])
{
int i,j,temp,l;
for(i=0; i<n/2;i++)
{
l=n-2*i;
for(j=0;j<l-1; j++)
{
temp = a[i+j][i];
a[i+j][i] = a[n-1-i][i+j];
a[n-1-i][i+j] = a[n-1-i-j][n-1-i];
a[n-1-i-j][n-1-i] = a[i][n-1-i-j];
a[i][n-1-i-j] = temp;
}
}
}
int main()
{
int a[][3]={{1,2,3},{4,5,6},{7,8,9}};
printm(a);
printf("\n\n\nAfter Rotation\n");
rotate(a);
printm(a);
return 0;
}
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int main()
{ clrscr();
int temp,i, j,k,l,n,b[20][20],a[20][20];
cout<<"\n\nenter n";
cin>>n;
cout<<"\n\n\nenter values";
for(i=0;i<n;i++)
{for( j=0;j<n;j++)
{cout<<"\n\nenter";
cin>>a[i][j];
}}
for(i=0;i<n/2;i++)
{for( j=i;j<n-i-1;j++)
{
//for clockwise rotation
temp=a[j][n-i-1];
a[j][n-i-1]=a[i][j];
a[i][j]=a[n-j-1][i];
a[n-j-1][i]=a[n-i-1][n-j-1];
a[n-i-1][n-j-1]=temp;
/*
for anti clockwise rotation
temp=a[i][j];
a[i][j]=a[j][n-i-1];cout<<"aij="<<i<<j<<a[i][j];
a[j][n-i-1]=a[n-i-1][n-j-1]; cout<<"ajn-i-1="<<j<<n-i-1<<a[j][n-i-1];
a[n-i-1][n-j-1]=a[n-j-1][i]; cout<<"ani1nj1="<<n-i-1<<n-j-1<<a[n-i-1][n-j-1];
a[n-j-1][i]=temp; cout<<"anj1i="<<n-j-1<<i<<a[n-j-1][i]<<endl;
getch();
/* for(k=0;k<n;k++)
{for( l=0;l<n;l++)
{cout<<a[k][l]<<" ";
}
cout<<"\n";
}
getch();
cout<<endl;
*/
}}
/*for(i=0;i<n;i++)
{for( j=0;j<n;j++)
{
b[i][j]=a[i][j];
}}
for(i=0;i<n;i++)
{for( j=0;j<n/2;j++)
{k=b[i][j];
b[i][j]=b[i][n-1-j];
b[i][n-1-j]=k;
}}
*/
for(i=0;i<n;i++)
{for( j=0;j<n;j++)
{cout<<a[i][j]<<" ";
}
cout<<"\n";
}
getch();
return 0;
}
Below is the C# implementation for inplace rotation. First we take transpose of the matrix and then swap elements starting from edges to inner elements. The function also takes care of clockwise and anti-clockwise rotation
private static void MatrixRotateInPlace(int[,] matrix, bool clockWise = true)
{
MatrixTranspose(matrix);
int row = matrix.GetLength(0);
int column = matrix.GetLength(1);
int temp;
for (int i = 0; i < row; i++)
{
int k = column - 1;
for (int j = 0; j < (column / 2); j++)
{
if (clockWise)
{
temp = matrix[i, j];
matrix[i, j] = matrix[i, k];
matrix[i, k] = temp;
}
else
{
temp = matrix[j, i];
matrix[j, i] = matrix[k, i];
matrix[k, i] = temp;
}
k--;
}
}
}
private static void MatrixTranspose(int[,] matrix)
{
for (int i = 0; i < 5; i++)
{
for (int j = i; j < 5; j++)
{
int temp = matrix[i, j];
matrix[i, j] = matrix[j, i];
matrix[j, i] = temp;
}
}
}
can be done in o(1) space with O(M) where M are total number of elements in a matrix of size (pxq)
This is java code for in-place rotation of an matrix of order n*n .
The idea here is take diagonal elements ( Diagonal from first element in First /top row to last element/ Right most element of last row). These elements on diagonal will be at the same place even after rotation , now replace elements equidistance from this diagonal elements .
public void rotateMatrix(int matrix[][])
{
int rowIndex=matrix.length-1; // Starting from last row
int colIndex=matrix[0].length-1;// Starting from last column
int tmp=0;
while(rowIndex>0)
{
colIndex=rowIndex-1;
while(colIndex>=0 )
{
tmp=matrix[rowIndex][colIndex];
matrix[rowIndex][colIndex]=matrix[colIndex][rowIndex];
matrix[colIndex][rowIndex]=tmp;
colIndex--;
}
rowIndex--;
}
}
- 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; }