## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

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;

}

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

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  }

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

Would this work even if the matrix is not nxn?

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

No, because you would need to allocate new storage. A x B is only the same dimensions as B x A if A = B. You wouldn't be able to reuse the old storage in the case that you had an M x N matrix with M != N because the output would need to be N x M.

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

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);
}

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

// 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];

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

hey why r u using extra nxn space.....?? its not a good solution..

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

you want inplace algorithm?

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

for(int i=0; i<n/2; i++)
for(int j=0; j<(n+1)/2; j++)
cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]);

void cyclic_roll(int &a, int &b, int &c, int &d)
{
int temp = a;
a = b;
b = c;
c = d;
d = temp;
}

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

for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
target[j][n-i-1] = a[i][j];

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

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;

}

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

This does not seem to be working properly for 5x5 matrix

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

Corrected!
See this

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

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

}

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

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;
}
}
}

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

can be done in o(1) space with O(M) where M are total number of elements in a matrix of size (pxq)

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

Can you explain how?

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

why do we need to reverse rows ..
wont taking transpose enough ??

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

transpose and reverse the rows

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

transpose the matrix and then reverse every row

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

awesomecoder.blogspot.com/2012/08/rotating-n-x-n-matrix-clockwise-by-90.html

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

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--;
}
}

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

The code for rotation of 90 deg is not correct in this case the input is
123
456
789 and output should be
741
852
963 and not
147
258
369

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

Try not to call people morons when you're wrong. Be right when you do that.

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.