Amazon Interview Question
Software Engineer / DevelopersThis is a problem about rotation array.
You can make rotation table.
This problem is also known as juggling but somewhat different.
In C++ solution is this:
#include <iostream>
using namespace std;
void rotate(int* arr)
{
int rot_table[] ={1,2,5,0,4,8,3,6,7};
int i=0;
int tmp = arr[0];
while(rot_table[i] != 0)
{
swap(arr[rot_table[i]], tmp);
i = rot_table[i];
}
arr[0] = tmp;
}
void print_mat(const int* arr)
{
for(int j=0;j<3;++j)
{
for(int i=0;i<3; ++i)
cout << arr[j*3+i] << " ";
cout << endl;
}
}
int main(int argc, char* argv[])
{
int m[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
print_mat(m);
rotate(m, sizeof(m)/sizeof(int));
print_mat(m);
return 0;
}
Its a variant of the famous print the array spirally.
int l = 0, r = width, b = length, t = 0;
while (l < r && b > t)
{
int i = l, j = t;
int tmp = 0;
tmp = a[j][i];
for (i = l; i < r-1; i++)
{
int tmp1 = a[j][i+1];
a[j][i+1] = tmp;
tmp = tmp1;
}
l++;
for (j = t; j < b-1; j++)
{
int tmp1 = a[j+1][i];
a[j+1][i] = tmp;
tmp = tmp1;
}
t++;
for (i = r-1; i >= l; i--)
{
int tmp1 = a[j][i-1];
a[j][i-1] = tmp;
tmp = tmp1;
}
r--;
for (j = b-1; j >= t; j--)
{
int tmp1 = a[j-1][i];
a[j-1][i] = tmp;
tmp = tmp1;
}
b--;
}
Thanks,
Rohith Menon
static int[,] Transform(int[,] arr)
{
int prev = int.MinValue;
int numCol = arr.GetLength(1);
int numRow = arr.GetLength(0);
for (int i = 0; i < numCol; i++)
{
if (i == 0)
{
prev = arr[0, i];
}
else
{
var temp = arr[0, i];
arr[0, i] = prev;
prev = temp;
}
}
int lastCol = numCol - 1;
for (int i = 1; i < numRow; i++)
{
var temp = arr[i, lastCol];
arr[i, lastCol] = prev;
prev = temp;
}
int lastRow = numRow - 1;
for (int i = lastCol -1; i >= 0; i--)
{
var temp = arr[lastRow, i];
arr[lastRow, i] = prev;
prev = temp;
}
for (int i = lastRow -1; i >= 1; i--)
{
var temp = arr[i, 0];
arr[i, 0] = prev;
prev = temp;
}
arr[0, 0] = prev;
return arr;
}
void RotateOneUnit()
{
for(i = size-1,j = 0; i > 0 ; i--,j++)
{
for(k = j ; k < i; k++)
{
if(k-1 < 0)
{
prev = arr[j][k];
arr[j][k] = arr[j+1][k];
}
else
{
temp = arr[j][k];
arr[j][k] = prev;
prev = temp;
}
}
for(k = j ; k < i; k++)
{
temp = arr[k][i];
arr[k][i] = prev;
prev = temp;
}
for(k = i ; k > j; k--)
{
temp = arr[i][k];
arr[i][k] = prev;
prev = temp;
}
for(k = i ; k > j; k--)
{
temp = arr[k][j];
arr[k][j] = prev;
prev = temp;
}
}
}
Consider the 2D as A[m][n]
- jvantagodi July 05, 2008Copy the first row in a single dimension array temp[n]
Copy next rows into current rows
Copy the temp in the last row.
for(j=0;j<n;j++)
temp[j]=A[0][j]
for(i=0;i<m-1; i++)
{
for(j=0;j<n;j++)
{
A[i][j] = A[i+1][j];
}
}
for(j=0;j<n;j++)
{
a[m-1][j] = temp[j];
}