Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: In-Person
// in JAVA
public class SpiralArray{
public static int printSpiral(int r,int c,int A[][],int z){
int i,k=0,l=0;
/* k= starting row index
r= ending row index
l= starting column index
c= ending column index
*/
//,ra=0;
while(k<r && l<c)
{
for(i=l;i<c;i++)
{if(z==0) return A[k][i];z--;}
//ra=A[k][i];//System.out.print(A[k][i]);
k++;
for(i=k;i<r;i++)
{if(z==0) return A[i][c-1];z--;}
//ra=A[i][c-1];//System.out.print(A[i][c-1]);
c--;
if(k<r){
for(i=c-1;i>=l;i--)
{if(z==0) return A[r-1][i];z--;}
//ra=A[r-1][i];//System.out.print(A[r-1][i]);
r--;
}
if(l<c){
for(i=r-1;i>=k;i--)
{if(z==0) return A[i][l]; z--;}
//ra=A[i][l];//System.out.print(A[i][l]);
l++;
}
}
//System.out.print(ra);
return 0;
}
public static void main(String args[]){
int R=5,C=5,z=13; // zth element to find
int[][] A= new int[][]{ {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}
};
int ra= printSpiral(R,C,A,z-1);
System.out.print(ra);
}
}
javascript implementation O(N)
let matrix = [];
for(var i = 0 ; i < 10 ; i++){
let arr = [];
matrix.push(arr);
for(let j = 0; j < 10; j++){
arr.push(i*10 + j);
}
}
console.log(matrix);
function findKth(k, matrix){
if(k <= 0 || k >matrix.length * matrix.length){
return null;
}
let startEdge = matrix.length;
let index = 0;
while(k > ((startEdge * 4) - 4)){
k -= ((startEdge * 4) - 4);
index++;
startEdge -= 2;
}
return findOnBorder(matrix, k, index, startEdge);
}
function findOnBorder(matrix, k, startPoint, edgeLength){
console.log('border')
k--;
if(k < edgeLength - 1){
// top part
return matrix[ startPoint][startPoint + k ];
}
k -= edgeLength - 1;
if(k < edgeLength - 1){
// right part
return matrix[startPoint + k ][startPoint + edgeLength - 1 ];
}
k -= edgeLength - 1;
if(k < edgeLength - 1){
// bottom
return matrix[ startPoint + edgeLength - 1 ][startPoint + edgeLength - 1 - k ];
}
// left side
k -= edgeLength - 1;
return matrix[ startPoint + edgeLength - 1 - k ][startPoint ];
}
console.log(findKth(37, matrix));
// print 11
console.log(findKth(100, matrix));
// print 54
console.log(findKth(50, matrix));
// print 78
console.log(findKth(64, matrix));
// print 21
console.log(findKth(65, matrix));
// print 22
public int FindKthSpiralValue(int[][] N, int kth)
{
if(kth >= N.Length*N.Length || kth < 0)
throw ArgumentOutOfRangeException("kth");
int startx = 0;
int starty = 0;
int endx = N.Length-1;
int endy = N.Length-1;
while(true)
{
for(int i = startx; i < endx; i++)
{
if(kth == 0) return N[i][starty]l;
kth--;
}
for(int j = starty; j < endy; j++)
{
if(kth == 0) return N[endx][j];
kth--;
}
for(int k = endx; k > startx; k--)
{
if(kth == 0) return N[k][endy];
kth--;
}
for(int l = endy; l > starty; l--)
{
if(kth == 0) return N[startx][l];
kth--;
}
startx++;
starty++;
endx--;
endy--;
}
}
This is other way to do it, without visiting every cell in the matrix, starting at 0,0 in clockwise direction and using a NxN matrix
- Motakjuq September 27, 2016