Interview Question
- 0of 0 votes
AnswersSo recently to someone I know a question was ask how do you rotate a 2 dimensional array? He was asked to white board it. He could get diagram the problem but had trouble coding it.
- glen@jetsoftdev.com December 15, 2017 in United States
This is not an easy answer because equal dimensional array are easy but require you know the trip that you divide the x and y dimension and then do four swapping rotation around the corners. Not equal X,Y are much harder. When I heard this question, I could get the equal dimensions done in an hour or two in a compiler. It took me two days to get the total program working. Here is the code:
{
#include <stdio.h>
int main()
{
#define xsize 4
#define ysize 8
int matrix[ysize*xsize] ;
typedef enum rotation
{
CW0,
CW90,
CW180,
CW270,
CCW0,
CCW90,
CCW180,
CCW270,
DONE0
} RotationTypes;
RotationTypes DesiredRotation = CW270;
#define min(a,b) ( (a) < (b) ? a : b)
int x,y,r,swap0, swap1,rotx,roty, rotidx;
//walk through every possibily
for (DesiredRotation = CW0; DesiredRotation <= DONE0 ; DesiredRotation++)
{
for (y=0;y<ysize;y++)
{
for (x=0;x<xsize;x++)
{
matrix[(y*xsize)+x] = y + x*10;
//print the base rotation for references
if ( DesiredRotation == CW0
|| DesiredRotation == CCW0
|| DesiredRotation == DONE0)
printf("%d ", matrix[(y*xsize)+x]);
}
if ( DesiredRotation == CW0
|| DesiredRotation == CCW0
|| DesiredRotation == DONE0)
printf("\n");
}
if ( DesiredRotation == CW0
|| DesiredRotation == CCW0
|| DesiredRotation == DONE0)
printf("\n");
//flips are generally more effeicient than rotation
//bu doing flips you only have to do one 90 degree
// type of rotation. flips work on uneven dimeions
if (DesiredRotation != CCW90 && DesiredRotation != CW270)
{
//horiztonal flip
for (y=0;y<ysize;y++)
{
for (x=0; x<xsize/2;x++)
{
swap0 = matrix[(y*xsize)+x];
matrix[(y*xsize)+x] = matrix[(y*xsize)+((xsize-1)-x)] ;
matrix[(y*xsize)+((xsize-1)-x)] = swap0;
}
}
//vertical flip
for (y=0;y<ysize/2;y++)
{
for (x=0; x<xsize;x++)
{
swap0 = matrix[(y*xsize)+x];
matrix[(y*xsize)+x] = matrix[(((ysize-1)-y)*xsize)+x] ;
matrix[(((ysize-1)-y)*xsize)+x] = swap0;
}
}
}
if (DesiredRotation != CW0
&& DesiredRotation != CW180
&& DesiredRotation != CCW0
&& DesiredRotation != CCW180
&& DesiredRotation != DONE0)
{
//do one CCW90 rotation which is the same as CW270
//if would be more effiecient to hard code every
//different combination but no way to make it elegant
int sqsize=min(ysize,xsize);
//first do the inplace square part because it is very efficient
for (y=0;y<sqsize/2;y++)
{
for (x=0;x<(sqsize+1)/2;x++)
{
rotx = x;
roty = y;
//store the top, left
int swap0 = matrix[(y*xsize)+x];
//rotate into top left from top right
matrix[(y*xsize)+x] = matrix[(x*xsize)+((sqsize-1)-y)];
//rotate into top right from bottom right
matrix[(x*xsize)+((sqsize-1)-y)] = matrix[(((sqsize-1)-y)*xsize)+((sqsize-1)-x)];
//rotate into bottom right from bottom left
matrix[(((sqsize-1)-y)*xsize)+((sqsize-1)-x)] = matrix[(((sqsize-1)-x)*xsize)+y];
//into into bottom left from original top left
matrix[(((sqsize-1)-x)*xsize)+y] = swap0;
}
}
//now the challenge is what to do with unequal array left overs
//we chose to hardcode inserting rotation and swapping until done
//we have to do two different sets of code if height is
//greater than width
if (ysize>xsize)
{
int rotinc=0;
int baseptr = sqsize*sqsize;
int rowsize = xsize;
for (x=xsize-1;x>=0;x--)
{
for (y=sqsize;y<ysize;y++)
{
//find where the extra non square starts after
//the sqaure part of the arrary
int rotptr = baseptr+((y-sqsize)*rowsize)+x;
//store it for later insertion
swap0 = matrix[rotptr];
//find where in the new dimensions
//the rotation from the end of the square should
//go
int swapptr = (((xsize-1)-x)*ysize)+y;
//swap upswards to make room for the
//insertion
while (rotptr>swapptr)
{
matrix[rotptr] = matrix[rotptr-1];
rotptr--;
}
//insert the rotation at the proper place
//which is now free
matrix[swapptr] = swap0;
}
//we have done one row so increase where the
//base pointer will be for the next time
baseptr+=ysize-sqsize;
//because we did one rotation the remaining rows
//are one rotation smaller
rowsize--;
}
}
//width is bigger than height
if (xsize>ysize)
{
int rotinc=0;
int rowsize = xsize;
for (x=sqsize;x<xsize;x++)
{
//insert happen at the begging of the array for
//this sizing
int swapptr = 0;
for (y=0;y<ysize;y++)
{
//find the rotation at the end of each row
int rotptr = rotinc+(y*rowsize)+sqsize;
//store it for latter use
swap0 = matrix[rotptr];
//swap upwards to made room for the insertion
while (rotptr>swapptr)
{
matrix[rotptr] = matrix[rotptr-1];
rotptr--;
}
//issert the rotation at the begining of the
//array
matrix[swapptr] = swap0;
//increasement the point
swapptr++;
}
//we have done one row so need to increase
//our start posiiton
rotinc+=ysize;
//we have done one row. the remain is one row smaller
rowsize--;
}
}
//print out the rotated and maybe flipped new array
for (x=0;x<xsize;x++)
{
for (y=0;y<ysize;y++)
{
printf("%d ", matrix[(x*ysize)+y]);
}
printf("\n");
}
} else {
//printout the vertical flipped only array
if (DesiredRotation != CW0
&& DesiredRotation != CCW0
&& DesiredRotation != DONE0)
{
for (y=0;y<ysize;y++)
{
for (x=0;x<xsize;x++)
{
printf("%d ", matrix[(y*xsize)+x]);
}
printf("\n");
}
}
}
printf("\n");
}
return 0;
}
}| Report Duplicate | Flag | PURGE
.Net/C#
Python does it in very simple way, array can be of any dimension eg 4 X 5 or even if the other dimension is varying like there is a list of 4 lists with different length. That will also do.
Rotation can be done in two ways, rightwards or leftwards. So, two statements I have given.
- Sachin Thakare December 16, 2017