Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: Written Test
Code:
public void printSpiralOrder(int a[][]) {
int m = a.length,n = a[0].length;
int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
int i = rowStart, j = colStart;
for (j = colStart; j <= colEnd; j++)
System.out.print(a[i][j] + " ");
for (i = rowStart + 1, j--; i <= rowEnd; i++)
System.out.print(a[i][j] + " ");
for (j = colEnd - 1, i--; j >= colStart; j--)
System.out.print(a[i][j] + " ");
for (i = rowEnd - 1, j++; i > rowStart; i--)
System.out.print(a[i][j] + " ");
rowStart++;rowEnd--;colStart++;colEnd--;
}
}
#define N 4
int a[N][N] = { {1,2,3,4},
{12,13,14,5},
{11,16,15,6},
{10,9,8,7},
};
void print_num()
{
int i=0,j=0,count=0;
while( count < N*N )
{
// direction -> RIGHT
while( j <= N-1-i )
{
printf("%d ", a[i][j]);
j++; count++;
}
j--; i++;
// direction -> DOWN
while( i <= j )
{
printf("%d ", a[i][j]);
i++; count++;
}
i--; j--;
// direction -> LEFT
while( j >= N-1-i )
{
printf("%d ", a[i][j]);
j--; count++;
}
j++; i--;
// direction -> UP
while( i > j )
{
printf("%d ", a[i][j]);
i--; count++;
}
i++; j++;
} // end while
} // end print_num
A variation of the one above, in C# and works on any NxM rectangular matrix.
public static void TraverseSpiral(int[,] m)
{
int ROWS = m.GetLength(0);
int COLS = m.GetLength(1);
int row = 0;
int col = 0;
int count = ROWS * COLS;
int offset = 0;
while (count != 0)
{
// Top
while (col < COLS - offset)
{
Print(m, row, col);
++col; --count;
}
--col; ++row;
// Right
while (row <= ROWS - offset - 1)
{
Print(m, row, col);
++row; --count;
}
--row; --col;
// Bottom
while (col >= offset)
{
Print(m, row, col);
--col; --count;
}
++col; --row;
// Left
while (row > offset)
{
Print(m, row, col);
--row; --count;
}
++row; ++col;
++offset;
}
}
static void Print(int[,] m, int row, int col)
{
Console.WriteLine("[{0}, {1}] = {2}", row, col, m[row, col]);
}
#include<stdio.h>
int main()
{
int n,m,i,j,k,a[10][10];
printf("enter the value of n:\n");
scanf("%d",&n);m=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
for(i=0;i<=n/2;i++)
{
if(i==n/2&&n%2)
{
printf("%d\t",a[n/2][n/2]);
break;
}
for(k=i,j=i;j<m-1;j++)printf("%d\t",a[k][j]);printf("\n");
for(k=m-1,j=i;j<m-1;j++)printf("%d\t",a[j][k]);printf("\n");
for(k=m-1,j=m-1;j>i;j--)printf("%d\t",a[k][j]);printf("\n");
for(k=m-1,j=i;k> i;k--)printf("%d\t",a[k][j]);m--;printf("\n");
}
return 0;
}
public class matrixtoserial {
public static void main(String[] args) {
/*String str="lalabc";
String rev=new StringBuffer(str).reverse().toString();
System.out.println("reverse string is this "+rev);
*/
int a[][]=new int[3][4];
int cols=a[0].length;
a[0][0]=0;
a[0][1]=1;
a[1][0]=2;
a[1][1]=3;
a[2][0]=4;
a[2][1]=5;
System.out.println(a.length);
for(int i=0;i<a.length;i++){
for(int j=0;j<cols;j++){
System.out.print(","+a[i][j]);
}
}
}
}
check this code.....I think this is simple........
public String clockwise(int[] numbers) {
int len = numbers.length;
int n = (int)Math.sqrt(len);
int[] orderedNumbers = new int[len];
for (int i=0; i<len; i++) {
int index = getIndex(i, n);
orderedNumbers[index] = numbers[i];
}
return generateString(orderedNumbers);
}
private String generateString(int[] orderedNumbers) {
StringBuilder sb = new StringBuilder();
for (int number : orderedNumbers) {
sb.append(number).append(" ");
}
return sb.toString().trim();
}
private int getIndex(int i, int n) {
int newRow = i%n;
int currentRow = i/n;
int newColumn = Math.abs(currentRow - n + 1);
return newRow*n + newColumn;
}
int main()
{
int row = 3, col = 3;
int b = 0;
int c = -1;
int a[3][3] = { {1,2,3},{8,9,4},{7,6,5}};
for (int i = 0; i< row * col; i++)
{
if ( (c < col - 1 && b == 0) )
{
cout<<a[b][++c];
}
else if ( c == col -1 && b < row -1 )
{
cout<<a[++b][c];
}
else if ( b == row -1 && c > 0)
{
cout<<a[b][--c];
}
else if ( c == 0 && b == row -1 )
{
cout<<a[--b][c++];
}
else
{
cout<<a[b][c];
}
}
return 0;
}
int main()
{
int row = 3, col = 3;
int b = 0;
int c = -1;
int a[3][3] = { {1,2,3},{8,9,4},{7,6,5}};
for (int i = 0; i< row * col; i++)
{
if ( (c < col - 1 && b == 0) )
{
cout<<a[b][++c];
}
else if ( c == col -1 && b < row -1 )
{
cout<<a[++b][c];
}
else if ( b == row -1 && c > 0)
{
cout<<a[b][--c];
}
else if ( c == 0 && b == row -1 )
{
cout<<a[--b][c++];
}
else
{
cout<<a[b][c];
}
}
return 0;
}
#include<iostream>
#include<map>
#define N 4
using namespace std;
int main()
{
int a[N][N] = { {1,2,3,4},
{12,13,14,5},
{11,16,15,6},
{10,9,8,7},
};
map<int,int> mtrx;
map<int,int>::iterator mitr;
cout<<"array content"<< endl;
for (int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<a[i][j]<<" ";
mtrx[a[i][j]]=a[i][j];
}
cout<<'\n';
}
cout<<"after sorting\n";
for(mitr=mtrx.begin();mitr!=mtrx.end();mitr++)
{
cout<<mitr->first<<'\n';
}
return 0;
}
#include<stdio.h>
#include<conio.h>
void main()
{
int array[3][3]={{1,2,9},{8,3,4},{7,6,5}};
int i=0;
int j=0;
int temp;
clrscr();
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
while(array[i][j]-1!=((i*3)+j))
{
temp=array[i][j];
array[i][j]=array[(temp/3)][(temp%3-1)];
array[(temp/3)][(temp%3)-1]=temp;
}
printf("%d\n",array[i][j]);
}
}
getch();
}
public class PrintMatrixAsCoil {
int matrixDimension = 7;
int[][] matrix = new int[matrixDimension][matrixDimension];
StringBuffer coilNumbers = new StringBuffer("");
public void initializeMatrix() {
int c = 1;
for( int i=0; i<matrixDimension; i++) {
for(int j=0; j<matrixDimension; j++) {
matrix[i][j] = c++;
}
}
}
public void printAsACoil() {
/* 0. stepsCount = matrixdimension-1;
* 1. move stepsCount steps right
* 2. move stepsCount steps down
* 3. move stepsCount steps left
* 4. move stepsCount steps up
* 5. if stepsCount = 2 stop; else go to 6
* 6. stepsCount = stepsCount -2;
* 7. go to step 1
*/
int stepsCount = matrixDimension - 1 ;
Position nextPosition = new Position(0,0);
Position currentPosition;
while(stepsCount > -1) {
// move right
currentPosition = moveRight(stepsCount, nextPosition);
nextPosition = new Position(currentPosition.x, currentPosition.y+1);
// move down
currentPosition = moveDown(stepsCount, nextPosition);
nextPosition = new Position(currentPosition.x+1, currentPosition.y);
// move left
currentPosition = moveLeft(stepsCount, nextPosition);
nextPosition = new Position(currentPosition.x, currentPosition.y-1);
// move up
currentPosition = moveUp(stepsCount, nextPosition);
nextPosition = new Position(currentPosition.x, currentPosition.y+1);
stepsCount = stepsCount -2;
}
// add middle number to coil if dimension if odd
if (matrixDimension%2 !=0)
coilNumbers.append(matrix[matrixDimension/2][matrixDimension/2]).append(" ");
System.out.println(coilNumbers.toString());
}
private Position moveRight(int stepsCount, Position p) {
for (int t=0; t<stepsCount; t++) {
coilNumbers.append(matrix[p.x][p.y + t]).append(" ");
}
return new Position(p.x, p.y+stepsCount-1);
}
private Position moveLeft(int stepsCount, Position p) {
for (int t=0; t<stepsCount; t++) {
coilNumbers.append(matrix[p.x][p.y - t]).append(" ");
}
return new Position(p.x, p.y-stepsCount+1);
}
private Position moveDown(int stepsCount, Position p) {
for (int t=0; t<stepsCount; t++) {
coilNumbers.append(matrix[p.x + t][p.y]).append(" ");
}
return new Position(p.x+stepsCount-1, p.y);
}
private Position moveUp(int stepsCount, Position p) {
for (int t=0; t<stepsCount; t++) {
coilNumbers.append(matrix[p.x - t][p.y]).append(" ");
}
return new Position(p.x-stepsCount+1, p.y);
}
public class Position {
int x;
int y;
Position() {}
Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public void printMatrixForTest() {
initializeMatrix();
for( int i=0; i<matrixDimension; i++) {
for(int j=0; j<matrixDimension; j++) {
System.out.print(matrix[i][j] + " ") ;
}
System.out.println();
}
}
public static void main(String[] args) {
PrintMatrixAsCoil m = new PrintMatrixAsCoil();
m.initializeMatrix();
m.printMatrixForTest();
System.out.println();
m.printAsACoil();
}
}
#include<stdio.h>
# define n 5
int main()
{
int i;
//int a[n][n] = { {1,2,3},{8,9,4},{7,6,5}};
/* int a[n][n]={ {1 ,2 ,3 ,4 },
{12,13,14,5},
{11,16,15,6},
{10,9 ,8 ,7}
}; //output--1,2,3,4,...16
*/
int a[n][n]={{1 ,2 ,3 ,4 ,5},
{16,17,18,19,6},
{15,24,25,20,7},
{14,23,22,21,8},
{13,12,11,10,9}
} ; //output--1,2,3,4,...25
/*
int a[n][n]={ {1 ,2 ,3 ,4 ,5 ,6 ,7},
{24,25,26,27,28,29,8},
{23,40,41,42,43,30,9},
{22,39,48,49,44,31,10},
{21,38,47,46,45,32,11},
{20,37,36,35,34,33,12},
{19,18,17,16,15,14,13}
}; //output--1,2,3,4,...49
*/
int cl1=0,n1=n-1;//,c1=n-1,c2=c1-1;
int count=n*n,chk=0;
while(chk<count)
{
for(i=cl1;i<=n1 && chk<=count;i++)
{printf("%d ",a[cl1][i]); chk++;}
for(i=cl1+1;i<=n1 && chk<=count;i++)
{printf("%d ",a[i][n1]); chk++;}
for(i=n1-1;i>=cl1 && chk<=count;i--)
{printf("%d ",a[n1][i]); chk++;}
for(i=n1-1;i>cl1 && chk<=count;i--)
{printf("%d ",a[i][cl1]); chk++;}
cl1++; n1--;
}
return 0;
}
Using recursion:
Please correct me if I'm wrong.
- teli.vaibhav April 20, 2013