## Amazon Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

``````public class Matrix {

public static int get(int n, int i, int j)
{
int d=0;
switch(i)
{
case 0:
d=j;
break;

default:
if(i==n-1)
{
d=2*n-2+(n-1-j);

break;
}
switch(j)
{
case 0:
d=3*n-3+n-i-1;
break;
default:
if(j==n-1)
d=n+i-1;
break;

}
}

return n*n-d;

}

public static void main(String args[])
{
int n=6;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int k=0,l=0,N=0;
int d=0;
if(i==0 || j==0 || i == n-1 || j==n-1)
{
k=i;
l=j;
N=n;
}

else
{

if(j < Math.ceil(n/2.0) && i < Math.ceil(n/2.0))
{
if(i<j)
d=i;
else d=j;
}
else if(i<Math.ceil(n/2.0) && i <= n-1-j)
d=i;
else if(i<Math.ceil(n/2.0) && i > n-1-j)
d=n-1-j;
else if(j<Math.ceil(n/2.0) && j<n-1-i )
d=j;
else if(j<Math.ceil(n/2.0) && j > n-1-j)
d=n-1-i;
else if(n-1-i > n-1-j)
d=n-1-j;
else
d=n-1-i;

k=i-d;
l=j-d;
N=n-2*d;

}
System.out.print(get(N,k,l)+" ");
}
System.out.println();
}

}
}``````

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

O(1) space ???? what is that supposed to mean?

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

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

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

It's "supposed to mean" what it always means -- that amount of space needed is constant (not a function of the size of the matrix).

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

have 4 for loops for each direction and decrement the extreme bounds indices

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

``````static void print()
{
int[,] a = new int[5,5];
printmatrix(a);

Position[] offsets = new Position;
offsets = new Position(0, 1);
offsets = new Position(1, 0);
offsets = new Position(0, -1);
offsets = 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);

}``````

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

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

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

@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

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

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.

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

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.

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

I meant a "call stack". What is the stack size for recursive call of the function if there are NO local variables or parameters when we are talking about space estimations?

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

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

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

@lol well its clearly written what the output format should be...

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

debugging will take most of time. Are they gonna give us a laptop or what?

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

This seems a STUPID question. What the heck solving such bizarre scenario that is pretty unlikely to be needed in an industry.

Why such guy is in interviewer position? I wonder :-O

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

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;

}``````

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

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");
}
}

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

<correction in above code >

l = min(i,j,n-1-i,n-1-j);

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

One more correction..
if(i<=j) in place of if(i>=j)

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

Unless I can derive it myself, there is no way I am going to remember that.

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

``````//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;
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--;
}
}``````

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.