## Google Interview Question for Software Engineer / Developers

• 0
of 0 votes

Country: United States
Interview Type: Phone Interview

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

Here is my post on rotating a given 2D matrix by a given angle (+90, -90, +180, -180):

rajendrauppal.blogspot.in/2011/12/rotating-2d-array-of-integers-matrix-by.html

Summary:
Input: n by n matrix M, where n >= 2

Rotate by +90 (clock-wise):
Step 1: Transpose M
Step 2: Reverse each row

Rotation by -90 degree (anticlockwise once):
Step 1: Transpose
Step 2: Reverse each column

Rotation by +180 degree (clockwise twice):
Two methods follows

First:
Rotate input matrix +90 degree twice, if routine for which is available to you

Second: (You'll be amazed!)
Step 1: Reverse each row
Step 2: Reverse each column

Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows

First:
Rotate input matrix -90 degree twice, if routine for which is available to you

Second: (You'll be amazed again!)
Step 1: Reverse each column
Step 2: Reverse each row

Third: (Aha!)
Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.

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

Various degree rotations : really nice.

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

``````for(i=0;i<n/2;i++)
{
for(j=i;j<n-i-1;j++)
{
t1=a[i+j][n-i];
t2=a[n-i][n-j];
a[i+j][n-i]=a[i][j];
a[n-i][n-j]=t1;
a[i][j]=a[4-j][i];
a[4-j][i]=t2;
printf("\n\n");
display();
getch();
}``````

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 6 vote

1:First Take the transpose of the matrix.
2:Reverse Each Row of the matrix.

Code:

``````#include<stdio.h>

Rotate(int A[4][4],int n)
{
int temp;
int i;
int j;
//Transpose of Matrix.
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
temp=A[i][j];
A[i][j]=A[j][i];
A[j][i]=temp;
}
}
//Reverse Each Row.
for(i=0;i<n;i++)
{
for(j=0;j<n/2;j++)
{
temp=A[i][j];
A[i][j]=A[i][n-j-1];
A[i][n-j-1]=temp;
}
}
}
int main()
{
int A[4][4]= {{1,2,3,4},
{6,7,8,9},
{11,12,13,14},
{16,17,18,19}};
int n=4;
int i;
int j;
Rotate(A,n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",A[i][j]);
}
printf("\n");
}``````

}

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

very simple code :)

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

should be optimized. too many loops increases the time complexity.. its O(n^2) taken for transpose itself.

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

int[,] m = new int[,] { { 1, 2, 3, 10 }, { 4, 5, 6, 11 }, { 7, 8, 9, 12 }, {13,14,15,16} };
int ml = 4;
int tmp = 0;
for (int i = 0; i < ml/2; i++)
{
for (int j = i; j < ml-1 - i; j++)
{
tmp = m[i, j];
m[i, j] = m[ml -1 - j, i]; //move up
m[ml - 1 - j, i] = m[ml - 1 - i, ml - 1 - j]; //move left
m[ml - 1 - i, ml - 1 - j] = m[j, ml - 1 - i]; //move donw
m[j, ml - 1 - i] = tmp; //move right
}
}

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

What if your ml is odd?

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

question from career cup book

public static void rotate(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]; // save top
// left -> top
matrix[first][i] = matrix[last - offset][first];

// bottom -> left
matrix[last - offset][first] = matrix[last][last - offset];

// right -> bottom
matrix[last][last - offset] = matrix[i][last];

// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}

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

void rotateMatrix(float** a, int n) {

if (n <= 1) {
return; // nothing to do: we hit 0 (n is even) or 1 (n is odd)
}

/* outer layer */
for (int i=0; i<n; i++) {
int saved = a[0][i]; // save top.(left+i)

a[0][i] = a[n-i-1][0]; // move (bottom-i).left to top.(left+i)

a[n-i-1][0] = a[n-1][n-1-i]; // move bottom.(right-i) to (bottom-i).left

a[n-1][n-1-i] = a[i][n-1]; // move top(+i).right to bottom.(right-i)

a[i][n-1] = saved; // move top.left (saved) to top(+i).right
}

rotateMatrix(a[1][1], n-2); // now do it for the inner layer(s)
}

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

2 Steps:
Find transpose
Reverse each row indiv

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

Two easy steps
1. First find transpose
2. Swap first and last column, second and second last column and so on

Code here

``````static void rotate90(int[][]a){
int n = a.length;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
//Swap a[i][j] and a[j][i]
a[i][j] = a[i][j] ^ a[j][i];
a[j][i] = a[j][i] ^ a[i][j];
a[i][j] = a[i][j] ^ a[j][i];
}
}

//Now swap colums
int i=0;
int j=n-1;
while(i<j){
for(int k=0;k<n;k++){
//Swap a[k][i] and a[k][j]
a[k][i] = a[k][i] ^ a[k][j];
a[k][j] = a[k][j] ^ a[k][i];
a[k][i] = a[k][i] ^ a[k][j];
}
i++;
j--;
}
}
}``````

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

``````void rotate_matrix(int arr[3][3], int n)
{
int i;
int j;
int *mirror_pos;
int temp;
for (i = 0; i < n; ++i) {
for (j = i + 1; j < n; ++j) {
mirror_pos = &arr[j][i];
temp = *mirror_pos;
*mirror_pos = arr[i][j];
arr[i][j] = temp;
}
}
}``````

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

consider the column and row separately.(say,one n by m matrix, all index starts from 0. )
Any element with row # i , will be placed in the i-th column in the result matrix.
Any element with column #i, will be placed in the i-th row
So the problem is solved:
new_i, new_j = j,i
tips: the result matrix is m by n

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

``````static void Main(string[] args)
{
int[,] Matr;
int Sz = 5;
Matr = new int[Sz, Sz];
// initialize matrix
for (int i = 0; i < Sz; i++)
for (int j = 0; j < Sz; j++)
Matr[i, j] = i * Sz + j + 1;
// rotate
for (int i = 0; i < (Sz - Sz % 2) / 2; i++)
{
for (int j = i; j < Sz - i - 1; j++)
{
SWAP(ref Matr[i, j], ref Matr[j, Sz - i - 1]);
SWAP(ref Matr[Sz - j - 1, i], ref Matr[i, j]);
SWAP(ref Matr[Sz - i - 1, Sz - j - 1], ref Matr[Sz - j - 1, i]);
}
}
}

public static void SWAP(ref int a, ref int b)
{
a = a + b;
b = a - b;
a = a - b;
}``````

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

This will work for [n][n] matrix. Code in Javascript.

``````var rotateMat = function(matrix){
var mat = matrix;
var numRows = mat.length; var numCols = mat[0].length;

for(var i = 0 ; i < numRows ; i++ )
for(var j = i ; j < numCols ; j++)
{
var tmp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = tmp;
console.log(tmp);
}
console.log(mat);

var start = 0; end = numCols - 1;
while(start<end){
for(var i = 0 ; i < numRows; i++){
var tmp = mat[i][start];
mat[i][start] = mat[i][end];
mat[i][end] = tmp;
}
start++; end--;
}
console.log(mat);
}``````

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

Oh as an explanation.. First loop transposes the matrix. The second loop swaps columns till the middle. This results in matrix rotated.

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

This one was tested on work. C#

int size = 2; //that means size 3x3 because counting starts from 0
int[,] ar = new int[3,3] { {1, 2,3}, {4,5,6},{7,8,9} };

//layers - how many layers can be "peeled" from the matrix.
//2x2 - 1 layer. 3x3 - 1 layer (with one unrotated element in the middle), 4x4 - 2 layers
int layers = (int)Math.Floor((double)(size+1) /2);

//starting rotate layer by layer starting from the outside layer.
for (int lyr = 0; lyr < layers; lyr++)
{
for (int col = lyr; col < size - lyr; col++)
{
int temp = ar[size-lyr-col,lyr];
ar[size - lyr - col, lyr] = ar[size - lyr, size - lyr - col];
ar[size - lyr, size - lyr - col] = ar[lyr + col, size - lyr];
ar[lyr + col, size - lyr] = ar[lyr, lyr + col];
ar[lyr, lyr + col]= temp;
}
}

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

This one was tested. It works. C#

int size = 2; //that means size 3x3 because counting starts from 0
int[,] ar = new int[3,3] { {1, 2,3}, {4,5,6},{7,8,9} };

//layers - how many layers can be "peeled" from the matrix.
//2x2 - 1 layer. 3x3 - 1 layer (with one unrotated element in the middle), 4x4 - 2 layers
int layers = (int)Math.Floor((double)(size+1) /2);

//starting rotate layer by layer starting from the outside layer.
for (int lyr = 0; lyr < layers; lyr++)
{
for (int col = lyr; col < size - lyr; col++)
{
int temp = ar[size-lyr-col,lyr];
ar[size - lyr - col, lyr] = ar[size - lyr, size - lyr - col];
ar[size - lyr, size - lyr - col] = ar[lyr + col, size - lyr];
ar[lyr + col, size - lyr] = ar[lyr, lyr + col];
ar[lyr, lyr + col]= temp;
}
}

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

``````#include<iostream>
using namespace std;
#define MAX_SIZE 50
int n[MAX_SIZE][MAX_SIZE];
int size,temp;
int main()
{

cout<<"Enter the size of aquare matrix : ";
cin>>size;

cout<<"\nEnter the array : ";
for(int i=0; i<size; i++)
{
for(int j =0; j<size; j++)
cin>>n[i][j];
}

cout<<"\nEntered array id : ";

for(int i=0; i<size; i++)
{
cout<<endl;
for(int j =0; j<size; j++)
cout<<n[i][j]<<" ";
}

//transforming the matrix
for(int i=0; i<size-1; i++)
{
for(int j =i+1; j<size; j++)
{
temp =n[i][j];
n[i][j] = n[j][i];
n[j][i] =temp;
}
}

//upside down the matrix

for(int i=0; i<size/2; i++)
{
for(int j =0; j<size; j++)
{
temp =n[i][j];
n[i][j] = n[size-1-i][j];
n[size-1-i][j] = temp;
}
}

cout<<"\nRotated array is : ";

for(int i=0; i<size; i++)
{
cout<<endl;
for(int j =0; j<size; j++)
cout<<n[i][j]<<" ";
}
return 0;
}``````

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

This one works too.
It simulates the rotation. Though it's O(n^2).

1 2 3 4 5
0 5 6 7 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
------------
0,0 --> 0,4
0,4 --> 4,4
4,4 --> 4,0
4,0 --> 0,0
***
0,1 --> 1,4
1,4 --> 4,3
4,3 --> 3,0
3,0 --> 0,1
***
0,2 --> 2,4
2,4 --> 4,2
4,2 --> 2,0
2,0 --> 0,2
***
0,3 --> 3,4
3,4 --> 4,1
4,1 --> 1,0
1,0 --> 0,3
***
1,1 --> 1,3
1,3 --> 3,3
3,3 --> 3,1
3,1 --> 1,1
***
1,2 --> 2,3
2,3 --> 3,2
3,2 --> 2,1
2,1 --> 1,2
***
0 0 0 0 1
0 0 0 5 2
0 0 0 6 3
0 0 0 7 4
0 0 0 0 5

``````package Rotate;

public class RotateClean {

public static void main(String args[]) {
int[][] a = { { 1, 2, 3, 4, 5 }, { 0, 5, 6, 7, 0 }, { 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
rotate(a);
}

static void rotate(int[][] a) {
int temp0, temp1;
int n = a.length;
int m = n / 2;

print(a);

System.out.println("------------");

for (int j = 0; j < m; j++) {
for (int i = j; i < n - j - 1; i++) {

temp0 = a[i][n - 1 - j];
a[i][n - 1 - j] = a[j][i];

temp1 = a[n - 1 - j][n - 1 - j - (i - j)];
a[n - 1 - j][n - 1 - j - (i - j)] = temp0;

temp0 = a[n - 1 - j - (i - j)][j];
a[n - 1 - j - (i - j)][j] = temp1;

a[j][i] = temp0;

}
}
print(a);
}

static void print(int[][] a) {

for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {

System.out.print(a[i][j] + " ");
}
System.out.println("");

}
}
}``````

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

``````for(int i = 0 ; i < n/2 ; i++){
for(int j = i ; j < n-i ; j++){
//4 corners = i,j - j,n-1-i - n-1-i,n-1-j - n-1-j,i
swap(&mat[i][j] , &mat[j][n-1-i]);
swap(&mat[i][j] , &mat[n-1-i][n-1-j]);
swap(&mat[i][j] , &mat[n-1-j][i]);
}
}``````

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

hmm.... quite intelligently framed..

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

This seems wrong. For example, let mat[0][0] = a. When i=0, j=0, a is first moved to mat[0][n-1]. When i=0, j=n-1, mat[0][n-1] is moved again, to mat[n-1][n-1]. i.e. mat[n-1][n-1] end up with value a.

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

yes, actually j is less than n-i-1 and not n-i. but really well thought....

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

``````for(int i = 0 ; i < n/2 ; i++){
for(int j = i ; j < n-i ; j++){
//4 corners = i,j - j,n-1-i - n-1-i,n-1-j - n-1-j,i
swap(&mat[i][j] , &mat[j][n-1-i]);
swap(&mat[i][j] , &mat[n-1-i][n-1-j]);
swap(&mat[i][j] , &mat[n-1-j][i]);
}
}``````

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

``````#include <iostream>
#include <cstdlib>
using namespace std;
const int SZ = 5;
void Init(char mtrx[][SZ])
{
for (int y = 0; y < SZ; ++y)
for (int x = 0; x < SZ; ++x)
mtrx[x][y] = '0' + (rand() % 10);
}
void Print(char mtrx[][SZ])
{
for (int y = 0; y < SZ; ++y)
{
for (int x = 0; x < SZ; ++x)
cout << mtrx[x][y];
cout << endl;
}
cout << endl;
}
void Swap4(char mtrx[][SZ], int x, int y)
{
const int sz = SZ - 1;
char& c1 = mtrx[x][y];
char& c2 = mtrx[sz - y][x];
char& c3 = mtrx[sz - x][sz - y];
char& c4 = mtrx[y][sz - x];
char tmp = c4;
c4 = c3;
c3 = c2;
c2 = c1;
c1 = tmp;
}
void Rotate(char mtrx[][SZ])
{
for (int y = 0; y < (SZ + 1) / 2; ++y)
for (int x = 0; x < (SZ) / 2; ++x)
Swap4(mtrx, x, y);
}
int main()
{
char (*mtrx)[SZ] = new char[SZ][SZ];
Init(mtrx);
Print(mtrx);
Rotate(mtrx);
Print(mtrx);
delete[] mtrx;
}``````

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

``````public void rotateMatrix(int[][] a, int n){
for(int level=0;level<n/2;level++){
for(int j=level;j<n-level-1;j++){
int temp=a[level][j];
a[level][j] = a[n-1-j][level];
a[n-1-j][level] = a[n-1-level][n-1-j];
a[n-1-level][n-1-j]=a[j][n-1-level];
a[j][n-1-level]=temp;
}
}
}``````

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

``````def rotate_matrix( input ):
n = len( input )
for r in range( 0, n/2 ):
for o in range( r, n-r-1 ):
temp = input[ r ][ o ]
input[ r ][ o ]=input[ n-o-1 ][ r ]
input[ n-o-1 ][ r ]=input[ n-r-1 ][ n-o-1 ]
input[ n-r-1 ][ n-o-1 ]=input[ o ][ n-r-1 ]
input[ o ][ n-r-1 ]=temp
return input``````

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More