## Amazon Interview Question

Software Engineer / DevelopersI think it means you need to print a[0,0],a[0,1] one by one.

The hard is to print a[0,4] and a[1,0] next.

You can not to create matrix before, which cost space, and then print by row and column.

```
static void print()
{
int[,] a = new int[5,5];
printmatrix(a);
Position[] offsets = new Position[4];
offsets[0] = new Position(0, 1);
offsets[1] = new Position(1, 0);
offsets[2] = new Position(0, -1);
offsets[3] = new Position(-1, 0);
int nOffsets = 0;
Position currentPosition = new Position(0, 0);
a[0,0] = 1;
for (int i = 1; i < 25; ++i)
{
Position nextPosition = currentPosition + offsets[nOffsets % 4];
if (nextPosition.x >= 5 || nextPosition.y >= 5 || nextPosition.x < 0 || nextPosition.y < 0 || a[nextPosition.x, nextPosition.y] > 0)
{
nOffsets++;
nextPosition = currentPosition + offsets[nOffsets % 4];
}
currentPosition = nextPosition;
a[currentPosition.x, currentPosition.y] = i + 1;
}
printmatrix(a);
}
```

u can't take an a[n][m] matrxi as a input u given opnly number n=5 now u have to print numbers from 1 to 15 but in given manner thats it..the meaning of not usinging space..stack space is not the problem..but programmer can't take m*n matrix as input..?

@martin

yes u r correct u cant use mxn array..but recursion is fine...

actually the soln is using recursion only

some hints are

first print thr first row 25..... 21

then find an expression bw 10 and 9

you would see (n-2)^2+i = 10 ,11 12....

also

20,19,18 = n^2-n-i

.

.

.

when you reach the last row print 13.... 17

I don't see why ANY space is needed at all if they don't treat stack as a space of course...Just print it recursively row by row.

Stack space is space ... duh. If you don't consider the stack when answering big-O questions about space, you might as well not show up for the interview.

why don't ppl take care to clearly post the question? what is intended to print here? It seems below output is expected without extra space.

25 24 23 22 21 10 09 08 07 20 11 02 01 06 19 12 03 04 05 18 13 14 15 16 17

I found this on link

unknownerror.net/2011-04/spiral-array-algorithm-medium-length-general-mathematical-analysis-5938

```
public int GetMatrixValue (int N, Point p)
{
int value = 0;
int circleNumber, circleNumberX, circleNumberY;
int zeroStart;
int min, max;
/ / Get circle number
circleNumberX = (int) (Math. Abs ((N – 1) / 2.0 – pX) + (N% 2 + 1) * 0.5);
circleNumberY = (int) (Math. Abs ((N – 1) / 2.0 – pY) + (N% 2 + 1) * 0.5);
circleNumber = Math. Max (circleNumberX, circleNumberY);
/ / Get zero start number
zeroStart = N * N – (2 * circleNumber – N% 2) * (2 * circleNumber – N% 2);
/ / Get min X and min Y
min = (N – 1) / 2 – circleNumber + 1;
max = min + circleNumber * 2 – N% 2-1;
/ / Get line number
if (pX <max & & pY == min) {value = zeroStart + pX – min +1;}
if (pX == max & & pY <max) {value = zeroStart + circleNumber * 2 – N% 2 + pY – min;}
if (pX <= max & & pY == max) {value = zeroStart + 2 * (circleNumber * 2 – N% 2) – 1 + max – pX;}
if (pX == min & & pY> min) {value = zeroStart + 3 * (circleNumber * 2 – N% 2) – 2 + max – pY;}
return value;
}
```

Following code prints it

{

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

l = min(i,j,n-i,n-j);// finds the layer in which (i,j)th element lies,

// min() finds minimum of four inputs

if(i>=j)

printf(" %d",((n-2*l)*(n-2*l)-(i-l)-(j-l)));

else

printf(" %d",((n-2*l-2)*(n-2*l-2)+(i-l)+(j-l)));

}

printf("\n");

}

}

```
//SPIRAL TRAVERSAL OF MATRIX
void matrix_spiral( int matrix[][], int n, int m ) {
int x=0,y=0,i,j;
int a=0,b=0,c=m,d=n;
//cout<<matrix[0][0];
cout<<endl;
while (a < c && b < d) {
while (y<c) {
cout<<matrix[x][y]<<" ";
y++;
}
x++;
y--;
while (x<d) {
cout<<matrix[x][y]<<" ";
x++;
}
x--;
y--;
while (y >=a) {
cout<<matrix[x][y]<<" ";
y--;
}
y++;
x--;
while (x > b) {
cout<<matrix[x][y]<<" ";
x--;
}
y++;
x++;
a++;
b++;
c--;
d--;
}
}
```

This is a code that I wrote to solve the problem. It takes O(1) space.

- deep May 19, 2011