Amazon Interview Question
Quality Assurance EngineersTeam: Kindle
Country: India
Interview Type: In-Person
i=j=low_r=low_c=0;
high_r=rows-1;
high_c=columns-1;
num=rows*columns;
k=0;
while(k<num){
for(j=low_c;j<=high_c && k<num ;j++){
printf("%d ",a[i][j]);
k++;
}
j--;
low_r++;
for(i=low_r;i<=high_r && k<num;i++){
printf("%d ",a[i][j]);
k++;
}
i--;
high_c--;
for(j=high_c;j>=low_c && k<num;j--){
printf("%d ",a[i][j]);
k++;
}
j++;
high_r--;
for(i=high_r;i>=low_r && k<num;i--){
printf("%d ",a[i][j]);
k++;
}
i++;
low_c++;
}
C++ templated version.
#include <iostream>
template <int N>
void print_spiral(int arr[N][N]) {
if (!arr)
return;
int rows = N;
int cols = N;
for (int r = 0, c = 0; r < rows; r++) {
for (int c2 = c; c2 < cols; c2++) {
std::cout << arr[r][c2] << " ";
}
for (int r2 = r + 1; r2 < rows; r2++) {
std::cout << arr[r2][cols - 1] << " ";
}
for (int c2 = cols - 2; c2 >= c; c2--) {
std::cout << arr[rows - 1][c2] << " ";
}
for (int r2 = rows - 2; r2 > r; r2--) {
std::cout << arr[r2][c] << " ";
}
c++;
rows--;
cols--;
}
std::cout << std::endl;
}
int main() {
int arr3[][3] {{1,2,3}, {8,9,4}, {7,6,5}};
print_spiral(arr3);
int arr5[][5] {{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}};
print_spiral(arr5);
return 0;
}
Use recursion to solve this problem. Divide it to subproblem and each subproblem prints the boundary. Below is the code for the same:
{
{
package com.practise.amazon;
public class PrintArrayInSpiral {
/**
* @param args
*/
public static void main(String[] args) {
int[][] arr = new int [][] {{1, 2, 3, 4}, {12, 13, 14, 5}, {11, 16, 15, 6}, {10, 9, 8, 7}};
printArrayInSpiral (arr);
}
private static void printArrayInSpiral(int[][] arr) {
printArrayInSpiral(arr, 0);
}
private static void printArrayInSpiral(int[][] arr, int step) {
if ( step > (arr[step].length - step - 1)) {
return;
}
for (int i = step; i < arr[step].length - step - 1; i++) {
System.out.print(arr[step][i]+" ");
}
for (int i = step; i < (arr.length - step); i++) {
System.out.print(arr[i][(arr[step].length - step - 1)]+" ");
}
for (int i = arr.length - step -2; i >= step; i--) {
System.out.print(arr[(arr.length - step -1)][i]+" ");
}
for (int i = arr.length - step -2; i > step; i--) {
System.out.print(arr[i][step]+" ");
}
printArrayInSpiral(arr, step + 1);
}
}
}
}
public static void spiralPrint(int [][] arr){
int [] d = {arr[0].length, //<
arr.length, //i <
0, //>=
1}; //>=
int i = 0;
int j = 0;
int dir = 0;
while(true){
if(d[0] == d[2])
break;
switch(dir){
case 0:
while( j < d[dir]){
System.out.print(arr[i][j]);
j++;
}
d[dir] -= 1;
j--; // j = length - 1
i++;
break;
case 1:
while( i < d[dir]){
System.out.print(arr[i][j]);
i++;
}
d[dir] -= 1;
i--;
j--;
break;
case 2:
while( j >= d[dir]){
System.out.print(arr[i][j]);
j--;
}
d[dir] += 1;
j++;
i--;
break;
case 3:
while( i >= d[dir]){
System.out.print(arr[i][j]);
i--;
}
d[dir] += 1;
i++;
j++;
break;
}
dir = (dir + 1 )%4;
}
}
The idea is to see the pattern.
We can notice that such spiral starts from (0,0) and traverse the edges of the (nxn) matrix with (0,0) as the top left corner and completes first round at just below the (0,0). Similarly, 2nd round continues from (1,1) and traverse edges of the (n-1)x(n-1) submatrix with (1,1) as the top left corner and completes the round just below (1,1).
That means for each round i, we traverse the a (n-i)x(n-i) submatrix with (i,i) as the top left corner as follows:
1. traverse the top row left to right from (i,i) to (i, n-i-1)
2. traverse the rightmost column down from (i+1, n-i-1) to (n-i-1, n-i-1) [note: we didn't start from (i, n-i-1) as we have already traversed (i, n-i-1); similarly we didn't finish at (n-i-1, n-i-1) as we will start the next step from there]
3. traverse the bottom row right to left from (n-i-1, n-i-1) to (n-i-1, i).
4. Traverse leftmost column up from (n-i-2, i) to (i+1, i).
Now, question is how many rounds to go? It depends on n. We can notice that each round i we are traversing a submatrix with (0,0) and (n-i-1, n-i-1) as the right diagonal corners. We are traversing two elements of the diagonal of the original matrix per round. So, no of rounds is n/2. If n is odd then the the middle element of the right diagonal should be left after n/2 rounds as described above.
- zahidbuet106 December 06, 2013