Amazon Interview Question Applications Developers
Country: United States
Interview Type: In-Person
this is rotate clockwise solution.
Shift solution see below.
c#.
private static void Rotate( int[,] arr ) {
int n = arr.GetLength( 0 );
if ( n != arr.GetLength( 1 ) ) {
throw new Exception( "This is not a square matrix" );
}
for ( int first = 0; first < n/2; first++ ) {
var last = n - 1 - first;
for ( int i = first; i < last; i++ ) {
var offset = n - 1 - i;
var tmp = arr[ first, i ];
arr[ first, i ] = arr[ offset, first ];
arr[ offset, first ] = arr[ last, offset ];
arr[ last, offset ] = arr[ i, last ];
arr[ i, last ] = tmp;
}
}
}
true shift implementation.
c#.
private static void ShiftRight( int[,] arr ) {
int n = arr.GetLength( 0 );
if ( n != arr.GetLength( 1 ) ) {
throw new Exception( "This is not a square matrix" );
}
for ( int first = 0; first < n/2; first++ ) {
var last = n - 1 - first;
int[] tmp1 = new int[4]
{
arr[ first, first ], arr[ first, last ], arr[ last , last ], arr[ last , first ]
};
for ( int i = first; i < last; i++ ) {
var offset1 = i + 1;
var offset2 = last - 1 - i + first;
var tmp2 = arr[ first, offset1 ];
arr[ first, offset1 ] = tmp1[ 0 ];
tmp1[ 0 ] = tmp2;
tmp2 = arr[ offset1, last ];
arr[ offset1, last ] = tmp1[ 1 ];
tmp1[ 1 ] = tmp2;
tmp2 = arr[ last, offset2 ];
arr[ last, offset2 ] = tmp1[ 2 ];
tmp1[ 2 ] = tmp2;
tmp2 = arr[ offset2, first ];
arr[ offset2, first ] = tmp1[ 3 ];
tmp1[ 3 ] = tmp2;
}
}
}
void moveInCircularMotion(int (*a)[col])
{
int i = 0, j = 0, temp = a[i][j];
while( i < row - 1)
{
a[i][j] = a[i+1][j];
i++;
}
while( j < col - 1)
{
a[i][j] = a[i][j+1];
j++;
}
while( i > 0)
{
a[i][j] = a[i-1][j];
i--;
}
while( j > 0)
{
if(j == 1)
{
a[i][j] = temp;
break;
}
a[i][j] = a[i][j-1];
j--;
}
}
O(n^2) for a nxn matrix
import java.util.Arrays;
public class ShiftMatrix {
public static void main(String[] args) {
int[][] matrix = new int[][] {
new int[] {1, 2, 3, 4, 5},
new int[] {6, 7, 8, 9, 10},
new int[] {11, 12, 13, 14, 15},
new int[] {16, 17, 18, 19, 20},
new int[] {21, 22, 23, 24, 25} };
ShiftMatrix.shift(matrix);
for (int[] i : matrix)
System.out.println(Arrays.toString(i));
}
public static void shift(int[][] matrix) {
int curCol = matrix[0].length - 1;
int curRow = 0;
while (curRow != matrix.length) {
while (curCol != 0) {
swap(matrix, curRow, curCol, curCol - 1);
curCol--;
}
curCol = matrix[0].length - 1;
curRow++;
}
}
public static void swap(int[][] matrix, int row, int fromCol, int toCol) {
int temp = matrix[row][fromCol];
matrix[row][fromCol] = matrix[row][toCol];
matrix[row][toCol] = temp;
}
}
Prints:
[5, 1, 2, 3, 4]
[10, 6, 7, 8, 9]
[15, 11, 12, 13, 14]
[20, 16, 17, 18, 19]
[25, 21, 22, 23, 24]
another c# implementation.
circular algo: the solution replaces elements one by one in really a circular manner.
private static void ShiftRightNew( int[,] arr ) {
int first = 0, row = 0, col = 0, rowt2 = 0, colt2 = 0, pass = 0;
var last = arr.GetLength( 0 ) - 1;
var tmp1 = arr[ first, first ];
var tmp2 = arr[ first, first + 1 ];
while ( last - first > 0 ) {
Get( ref row, ref col, ref rowt2, ref colt2, ref pass, first, last );
arr[ row, col ] = tmp1;
tmp1 = tmp2;
tmp2 = arr[ rowt2, colt2 ];
if ( rowt2 == first && colt2 == first + 1 ) {
first++;
last--;
tmp1 = arr[ first, first ];
tmp2 = arr[ first, first + 1 ];
row = first; col = first; rowt2 = first; colt2 = first;
}
}
}
private static void Get( ref int row, ref int col, ref int rowt2, ref int colt2, ref int pass, int first, int last ) {
if ( pass == 0 ) {
if ( rowt2 == first && ( colt2 == last ) ) {
rowt2 = first + 1;
col = last;
pass++;
return;
}
col++;
if ( last - first == 1 ) {
colt2++; rowt2++; pass++;
} else { colt2 = col + 1; }
return;
}
if ( pass == 1 ) {
if ( rowt2 == last && colt2 == last ) {
colt2 = last - 1;
row = last;
pass++;
return;
}
row++;
rowt2 = row + 1;
return;
}
if ( pass == 2 ) {
if ( rowt2 == last && colt2 == first ) {
rowt2 = last - 1;
col = first;
pass++;
return;
}
col--;
colt2 = col - 1;
return;
}
if ( pass == 3 ) {
if ( rowt2 == first && colt2 == first ) {
colt2 = first + 1;
row = first;
pass = 0;
return;
}
row--;
rowt2 = row - 1;
}
}
below performing cycling trough code and carrying the value to next movement. exteral for loop call can be reduced.
int a[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
int matrixSize=4;
public void cyclicRotate(){
for(int i=0;i<matrixSize;i++){
System.out.println();
for(int j=0;j<matrixSize;j++)
System.out.print(" "+a[j][i]);
}
for(int i =0 ; i<matrixSize/2;i++)
Rotate(i,i,-1,true,true);
for(int i=0;i<matrixSize;i++){
System.out.println();
for(int j=0;j<matrixSize;j++)
System.out.print(" "+a[j][i]);
}
}
private void Rotate(int x,int y,int value,boolean Moveforward,boolean horizontalMove){
if(value==-1)
value=a[x][y];
if(horizontalMove)
{
if(Moveforward){
for(int i=x;i<(matrixSize-x-1);i++){
value=swap(value, i+1, y);
}
Rotate(matrixSize-x-1,y,value,true,false);
}
else{
for(int i=x;i>(matrixSize-x-1);i--){
value=swap(value, i-1, y);
}
Rotate(matrixSize-x-1,y,value,false,false);
}
}
else{ // for vertical move Moveforward means move Down here{
if(Moveforward){
for(int i=y;i<matrixSize-y-1;i++){
value=swap(value, x, i+1);
}
Rotate(x,matrixSize-y-1,value,false,true);
}
else{
for(int i=y;i>(matrixSize-y-1);i--){
value=swap(value, x,i-1 );
}
//Rotate(x,matrixSize-y-1,value,false,true);
}
}
}
private int swap(int fromValue, int toX , int toY){
int temp = a[toX][toY];
a[toX][toY]=fromValue;
return temp;
}
Not a good solution.. but it is working
package dataStructures;
public class ShiftingMatrix {
public static void main(String[] args) {
// TODO Auto-generated method stub
int ar[][]={{1, 2, 3, 2},
{4, 5, 6, 4},
{7, 8, 9, 0},
{9, 3, 5, 1}};
int temp=0, temp2=0;
//for(int i=0;i<ar.length;i++){
int i=0;
temp=ar[i][0];
int j;
for( j=1;j<ar[0].length;j++){
temp2=ar[i][j];
ar[i][j]=temp;
temp=temp2;
}
//int j=1;
j--;
for(i=1;i<ar.length;i++){
temp2=ar[i][j];
ar[i][j]=temp;
temp=temp2;
}
// }
i--;
for( j=ar[0].length-2;j>=0;j--){
temp2=ar[i][j];
ar[i][j]=temp;
temp=temp2;
}
j++;
for(i=ar.length-2;i>=0;i--){
temp2=ar[i][j];
ar[i][j]=temp;
temp=temp2;
}
//temp=ar[i][0];
for(i=0;i<ar.length;i++){
for(j=0;j<ar[0].length;j++){
System.out.print(ar[i][j]);
}
System.out.println();
}
}
}
It seems like you are rotating the whole thing 90 degrees clockwise. The problem requires you to shift 1 element to the right element in 0,0 and consequently shift others accordingly.
- techinterviewsintesys December 15, 2015like here
1 2 3
4 5 6
7 8 9
you would get this
4 1 2
7 5 3
8 9 6