## Google Interview Question for Software Engineer / Developers

• 0

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

Various degree rotations : really nice.

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

``````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

very simple code :)

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

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

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

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

hmm.... quite intelligently framed..

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

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

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``````

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.

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

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