Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

package com.home.careercup;

public class PrintMatrixSpirallyUsingRecursion {

    /**
     * Write a logic to print the elements of 2D matrix in a spiral way?
     * <p>
     * for eg if int[][] matrix = {{1,2,3,4}{5.6,7,8}{9, 10, 11,12}};
     * The output should be 1 2 3 4 8 12 11 10 9 5 6 7
     * The interviewer asked me to implement a recursive algorithm.
     *
     * @param args
     */
    public static void main(String[] args) {

        //example 1
        int[][] m = new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        //example 2
        int[][] m1 = new int[][]{
                {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},
        };
        PrintMatrixSpirallyUsingRecursion printer = new PrintMatrixSpirallyUsingRecursion();
        printer.printMatrix(m, new int[]{0, m.length - 1},
                new int[]{0, m[0].length - 1}, Direction.LEFT_RIGHT);

        System.out.println();
        printer.printMatrix(m1, new int[]{0, m1.length - 1},
                new int[]{0, m1[0].length - 1}, Direction.LEFT_RIGHT);

        System.out.println();

    }

    enum Direction {
        DEFAULT, LEFT_RIGHT, TOP_DOWN, RIGHT_LEFT, DOWN_TOP;
    }

    /*
    Imagine a big block of soft material (rectangular).
    You will take slices from this material where thickness
    of slice is 1 row or 1 column
    Take Ninja sword and cut off the top part from LEFT to RIGHT ( SLIIIIICE!).
    Next cut slice on the right side from TOP to BOTTOM  ( SLIIIIICE!)
    Next cut slice from BOTTOM from RIGHT TO LEFT  ( SLIIIIICE!)
    Next cut slice from left side from BOTTOM to top  ( SLIIIIICE!)
    Repeat till there is NOTHING left

     */
    void printMatrix(int[][] m, int[] rowRange, int[] colRange, Direction d) {

        if (rowRange[1] - rowRange[0] < 0) return;
        if (colRange[1] - colRange[0] < 0) return;

        Direction next = Direction.DEFAULT;

        switch (d) {
            case LEFT_RIGHT:
                for (int x = rowRange[0], y = colRange[0]; y <= colRange[1]; y++)
                    System.out.printf("%d ", m[x][y]);
                rowRange[0]++;
                next = Direction.TOP_DOWN;
                break;

            case TOP_DOWN:
                for (int x = rowRange[0], y = colRange[1]; x <= rowRange[1]; x++)
                    System.out.printf("%d ", m[x][y]);
                colRange[1]--;
                next = Direction.RIGHT_LEFT;
                break;

            case RIGHT_LEFT:
                for (int x = rowRange[1], y = colRange[1]; y >= colRange[0]; --y)
                    System.out.printf("%d ", m[x][y]);
                rowRange[1]--;
                next = Direction.DOWN_TOP;
                break;

            case DOWN_TOP:
                for (int x = rowRange[1], y = colRange[0]; x >= rowRange[0]; --x)
                    System.out.printf("%d ", m[x][y]);
                colRange[0]++;
                next = Direction.LEFT_RIGHT;
                break;
            case DEFAULT:
                throw new RuntimeException("invalid direction");

        }
        printMatrix(m, rowRange, colRange, next);
    }
}

- Makarand August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<iostream>
using namespace std;
int printrow(int *a, int rowno, int sc, int ec,int n){  //for printing rows
    int z=0;
    if(sc<ec){
        for(int i=sc;i<=ec;i++){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    else{
        for(int i=sc;i>=ec;i--){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    return z;
}
int printcol(int *a,int colno,int sr,int er,int n){  //for printing columns
    int z=0;
    if(sr<er){
        for(int i=sr;i<=er;i++){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    else{
    for(int i=sr;i>=er;i--){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    return z;
}

int main(){
    int n,i,j,k,p,l,m,o,z;
    cin>>n; //number of columns. here it is 4
    int a[n-1][n];
    for(i=0;i<n-1;i++){
        for(j=0;j<n;j++){
            cin>>a[i][j]; // input value for the matrix
        }
    }
    k=n*(n-1);
    p=0;
    l=n-1;
    m=0;
    o=n-2;
    while(1){
        z=printrow((int *)a,m,p,l,n);
        m++;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,l,m,o,n);
        l--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printrow((int *)a,o,l,p,n);
        o--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,p,o,m,n);
        p++;
        k-=z;
        if(k<=0){
            break;
        }
    }
    return 0;
}

- SUBASH CHANDRA MANOHARI August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is just to navigate in a spiral direction using a direction state system.

JSBin: jsbin.com/guhafom/1/edit?js,console

var data = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12]
];


(function(data) {
  var direction = 0;
  var result = [];
  while(data.length) {
    switch(direction) {
      case 0: { //right
        var row = data.shift();
        result = result.concat(row);
        direction = 1; 
        break; 
      }
      case 1:  { //down
        var cells = [];
        data.forEach(function(row) {
          row && cells.push( row.pop() );
        });
        result = result.concat(cells);
        direction = 2;
        break; 
      }
      case 2:  { //left
        var row = data.pop();
        result = result.concat(row.reverse());
        direction = 3;
        break;
      }
      case 3:  { //up
        var cells = [];
        data.forEach(function(row) {
          row && cells.push( row.shift() );
        });
        result = result.concat(cells);
        direction = 0;
        break; 
      }
    }
  }
  console.log(result);
})(data);

//outputs: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Just notice the recursive requirement. One recursive solution is to put direction in param and call the function with the next direction to operate on. The base case is data is not empty else return the sliced data.

- tnutty2k8 August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if it needs to be recursive, the best I can come up is:

const int DIRECTIONS[][2] { {1,0}, {0,1}, {-1,0}, {0,-1} };

void printMatrixCircularRec(const vector<vector<int>>& matrix, int x, int y, int x2, int y2)
{
	if (y > y2 || x > x2) return;
	int dir = 0, cx = x, cy = y;
	while (y <= y2 && x <= x2) {
		cout << matrix[cy][cx] << " "; // a bit cheap
		if (cx + DIRECTIONS[dir][0] < x 
			|| cx + DIRECTIONS[dir][0] > x2 
			|| cy + DIRECTIONS[dir][1] < y 
			|| cy + DIRECTIONS[dir][1] > y2) {
			dir++;
			if (DIRECTIONS[dir % 4][0] > 0) x++;
			if (DIRECTIONS[dir % 4][0] < 0) x2--;
			if (DIRECTIONS[dir % 4][1] > 0) y++;
			if (DIRECTIONS[dir % 4][1] < 0) y2--;
			if (dir == 4) break;
		}
		cx += DIRECTIONS[dir][0];
		cy += DIRECTIONS[dir][1];
	}	
	printMatrixCircularRec(matrix, x, y, x2, y2);
}

void printMatrixCircular(const vector<vector<int>>& matrix) 
{
	if (matrix.size() == 0 || matrix[0][0] == 0) return;
	printMatrixCircularRec(matrix, 0, 0, matrix[0].size() - 1, matrix.size() - 1);
	cout << endl;
}

- Chris August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int printrow(int *a, int rowno, int sc, int ec,int n){ //for printing rows
int z=0;
if(sc<ec){
for(int i=sc;i<=ec;i++){
cout<<*((a+rowno*n) + i)<<" ";
z++;
}
}
else{
for(int i=sc;i>=ec;i--){
cout<<*((a+rowno*n) + i)<<" ";
z++;
}
}
return z;
}
int printcol(int *a,int colno,int sr,int er,int n){ //for printing columns
int z=0;
if(sr<er){
for(int i=sr;i<=er;i++){
cout<<*((a+i*n) + colno)<<" ";
z++;
}
}
else{
for(int i=sr;i>=er;i--){
cout<<*((a+i*n) + colno)<<" ";
z++;
}
}
return z;
}

int main(){
int n,i,j,k,p,l,m,o,z;
cin>>n; //number of columns. here it is 4
int a[n-1][n];
for(i=0;i<n-1;i++){
for(j=0;j<n;j++){
cin>>a[i][j]; // input value for the matrix
}
}
k=n*(n-1);
p=0;
l=n-1;
m=0;
o=n-2;
while(1){
z=printrow((int *)a,m,p,l,n);
m++;
k-=z;
if(k<=0){
break;
}
z=printcol((int *)a,l,m,o,n);
l--;
k-=z;
if(k<=0){
break;
}
z=printrow((int *)a,o,l,p,n);
o--;
k-=z;
if(k<=0){
break;
}
z=printcol((int *)a,p,o,m,n);
p++;
k-=z;
if(k<=0){
break;
}
}
return 0;
}

- SUBASH CHANDRA MANOHARI August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int printrow(int *a, int rowno, int sc, int ec,int n){  //for printing rows
    int z=0;
    if(sc<ec){
        for(int i=sc;i<=ec;i++){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    else{
        for(int i=sc;i>=ec;i--){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    return z;
}
int printcol(int *a,int colno,int sr,int er,int n){  //for printing columns
    int z=0;
    if(sr<er){
        for(int i=sr;i<=er;i++){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    else{
    for(int i=sr;i>=er;i--){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    return z;
}

int main(){
    int n,i,j,k,p,l,m,o,z;
    cin>>n; //number of columns. here it is 4
    int a[n-1][n];
    for(i=0;i<n-1;i++){
        for(j=0;j<n;j++){
            cin>>a[i][j]; // input value for the matrix
        }
    }
    k=n*(n-1);
    p=0;
    l=n-1;
    m=0;
    o=n-2;
    while(1){
        z=printrow((int *)a,m,p,l,n);
        m++;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,l,m,o,n);
        l--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printrow((int *)a,o,l,p,n);
        o--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,p,o,m,n);
        p++;
        k-=z;
        if(k<=0){
            break;
        }
    }
    return 0;
}

- SUBASH CHANDRA MANOHARI August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int printrow(int *a, int rowno, int sc, int ec,int n){  //for printing rows
    int z=0;
    if(sc<ec){
        for(int i=sc;i<=ec;i++){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    else{
        for(int i=sc;i>=ec;i--){
        cout<<*((a+rowno*n) + i)<<" ";
        z++;
    }
    }
    return z;
}
int printcol(int *a,int colno,int sr,int er,int n){  //for printing columns
    int z=0;
    if(sr<er){
        for(int i=sr;i<=er;i++){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    else{
    for(int i=sr;i>=er;i--){
        cout<<*((a+i*n) + colno)<<" ";
        z++;
    }
    }
    return z;
}

int main(){
    int n,i,j,k,p,l,m,o,z;
    cin>>n; //number of columns. here it is 4
    int a[n-1][n];
    for(i=0;i<n-1;i++){
        for(j=0;j<n;j++){
            cin>>a[i][j]; // input value for the matrix
        }
    }
    k=n*(n-1);
    p=0;
    l=n-1;
    m=0;
    o=n-2;
    while(1){
        z=printrow((int *)a,m,p,l,n);
        m++;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,l,m,o,n);
        l--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printrow((int *)a,o,l,p,n);
        o--;
        k-=z;
        if(k<=0){
            break;
        }
        z=printcol((int *)a,p,o,m,n);
        p++;
        k-=z;
        if(k<=0){
            break;
        }
    }
    return 0;
}

- subashmanohari August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's another solutions that uses recursion and direction enum and a visited boolean[][] to keep an eye on visited indices

package com.es.utils;


public class ArraySpiral {


    public static void main(String[] arsg) {

        try {
            int[][] input1 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
            int[][] input2 = {{ 1,  2,  3,  4,  5,  6},
                              { 7,  8,  9, 10, 11, 12},
                              {13, 14, 15, 16, 17, 18}
            };
            new ArraySpiral().printSpiralRecurse(input1);
            System.out.println("");
            new ArraySpiral().printSpiralRecurse(input2);

        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    /**
     * Setup up the inputs for recursive visit().
     * @param input the input int[][]
     */
    public void printSpiralRecurse(int[][] input) {
        boolean[][] visited = new boolean[input.length][input[0].length];
        this.visit(input, 0, 0, Direction.EAST, visited);
    }


    /**
     * Runs a recursive visit spiral algorithm by tracking visited nodes
     * in a boolean[][]
     *
     * @param input input to traverse int[][]
     * @param r current row to visit
     * @param c current col to visit
     * @param d current traversal direction
     * @param visited track visited nodes as boolean[][]
     * @return true|false based on last traversed element.
     */
    public boolean visit(int[][] input, int r, int c, Direction d, boolean[][] visited) {

        if (r  >= input.length || r < 0 ||
                c  >= input[0].length || c < 0) {
            return false;  //outOfBound
        }

        if (visited[r][c]) {
            return false; //alreadyVisisted
        }

        System.out.print(input[r][c] + ", ");
        visited[r][c]= true;

        boolean success = visit(input, r + d.getRowIncr(), c + d.getColIncr(), d, visited);
        //if fails, backtrack and try next direction
        if (!success) {
            d=d.changeDirection();
            success = visit(input, r + d.getRowIncr(), c + d.getColIncr(), d, visited);
            return success;
        }
        return true;
    }

}


/**
 * Create enum for directions so we can use it to
 * move indices for traversal plus save logic to
 * get the next direction
 *
 */
enum Direction {

    EAST(0,1),  SOUTH(1,0), WEST(0,-1), NORTH(-1,0),;

    private int r=0;

    private int c=0;

     Direction(int r,int c) {
        this.r=r;
        this.c=c;
    }

    public int getRowIncr() { return this.r; }
    public int getColIncr() { return this.c; }

    public Direction changeDirection() {
        switch (this.ordinal()) {
            case 0:
                return Direction.SOUTH;
            case 1:
                return Direction.WEST;
            case 2:
                return Direction.NORTH;
            case 3:
                return Direction.EAST;
        }
        return Direction.EAST;
    }

}

- Ehtesham Siddiqui August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.cracking.amazon;

public class Print2DMatrixSpiralWay {
	
	static class Direction {
		public String name;
		public int rowInc;
		public int columnInc;
		public boolean isHorizonatl;
		
		public Direction(String name, int rowInc, int columnInc, boolean isHorizonatl) {
			this.name = name;
			this.rowInc = rowInc;
			this.columnInc = columnInc;
			this.isHorizonatl = isHorizonatl;
		}
		
	}

	public static Direction[] directions = {
			new Direction("RIGHT", 0, 1,true),
			new Direction("DOWN", 1, 0,false),
			new Direction("LEFT", 0, -1,true),
			new Direction("UP", -1, 0,false)
	};
	
	public static int[][] matrix = {
			{1,2,3,4},
			{5,6,7,8},
			{9,10,11,12},
			{13,14,15,16}
	};
	

	public static void main(String[] args) {
		printSpiral(matrix, 0,0,4,0,4);
	}
	
	public static void printSpiral(int matrix[][],int direction,int rowPos,int rowCount,int columnPos,int columnCount) {
		direction = direction < directions.length ? direction:0;
		Direction currDirection = directions[direction];
		
		int rowCountC = rowCount;
		int columnCountC = columnCount;
		int printed = 0;
		
		while( rowCount > 0  && columnCount>0) {
			printed++;
			System.out.print(matrix[rowPos][columnPos] + " , ");
			rowPos += currDirection.rowInc;
			columnPos += currDirection.columnInc;
			
			if(currDirection.isHorizonatl) {
				//running on columns
				columnCount--;
			}else {
				//running on rows
				rowCount--;
			}
		}
		
		int nextDirection = direction+1;
		nextDirection = nextDirection < directions.length ? nextDirection:0;
		
		if(currDirection.isHorizonatl) {
			rowCountC--;
			columnPos -= currDirection.columnInc;
			rowPos += directions[nextDirection].rowInc;
		}else {
			columnCountC--;
			rowPos -= currDirection.rowInc;
			columnPos += directions[nextDirection].columnInc;
		}
		
		if(printed > 0) {
			printSpiral(matrix, nextDirection, rowPos, rowCountC, columnPos, columnCountC);
		}
	}
	
}

- Yonatan Riaznov August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution

while array is not empty
- Print first row and remove it
- rotate array 90 to left

Although not efficient, but can be really short solution in some languages (ex python)

- tnutty2k8 August 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could do something like below in Java:
The idea is after each row/column - change direction and reduce the width of elements to print.

public class PrintSpiralArray
{
    public static void main ( String... args )
    {
        PrintSpiralArray psa = new PrintSpiralArray();
        int[][] a = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        psa.print( Direction.POS_X, 0, a[0].length, a.length, 0, -1, a, 0);
    }
    
    public void print( Direction d, int range, int xwidth, int ywidth, int i, int j, int[][] a, int grabbed )
    {
       if ( grabbed == a[0].length*a.length )
       {
          return;
       }
       else
       {
           
          switch( d )
          {
          case POS_X:
             if ( range == xwidth )
             {
                 ywidth--;
                 range = 0;
                 d = Direction.NEG_Y;
             }
             else
             {
                 j++;
                 range++;
                 grabbed = printAndGrab( a, i, j, grabbed );
                 
             }
             break;
          case NEG_Y:
              if ( range == ywidth )
             {
                 xwidth--;
                 range = 0;
                 d = Direction.NEG_X;
             }
             else
             {
                 i++;
                 range++;
                 grabbed = printAndGrab( a, i, j, grabbed );
                 
             }
             break;
          case NEG_X:
              if ( range == xwidth )
              {
                 ywidth--;
                 range = 0;
                 d = Direction.POS_Y;
              }
              else
              {
                 j--;
                 range++;
                 grabbed = printAndGrab( a, i, j, grabbed );
                
              }
              break;
          case POS_Y:
              if ( range == ywidth )
              {
                 xwidth--;
                 range = 0;
                 d = Direction.POS_X;
              }
              else
              {
                 i--;
                 range++;
                 grabbed = printAndGrab( a, i, j, grabbed );
                 
              }
              break;
          }
          
          print ( d, range, xwidth, ywidth, i, j,  a, grabbed );
       }

    }
    
    private int printAndGrab( int[][] a, int i, int j, int grab )
    {
        System.out.print( a[i][j] + " ");
        return ++grab;
        
    }
    
    enum Direction
    {
      POS_X,
      POS_Y,
      NEG_X,
      NEG_Y
    }
}

- Sunny August 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PrintSpiralIn2DMatrix {

	public void printSpiral(int arr[][]) {
		int i = 0;
		int j = 0;
		int iMax = arr.length;
		int jMax = arr[i].length;
		printMatrix(arr, i , j,iMax ,jMax);
	}

	private void printMatrix(int[][] arr, int i, int j, int iMax, int jMax) {
		boolean noElementLeftAti = (iMax <= i); 
		boolean noElementLeftAtj = (jMax <= j);
		if(noElementLeftAti && noElementLeftAtj){
			return;
		}
		
		//L2R 
		for(int p = i; p<iMax-1 ;p++ ){
			System.out.print(arr[j][p]+" ");
		}
		//T2B
		for(int p = j ; p < jMax-1 ;p++ ){
			System.out.print(arr[p][iMax-1]+" ");
		}
		//R2L
		for(int p = iMax-1 ; p > i ;p-- ){
			System.out.print(arr[iMax-1][p]+" ");
		}
		//B2T
		for(int p = jMax-1 ; p > j ;p-- ){
			System.out.print(arr[p][i]+" ");
		}
		i += 1;
		j += 1;
		iMax -= 1;
		jMax -= 1;
		printMatrix(arr, i , j,iMax ,jMax);		
	}
	
	public static void main(String[] args) {
		int arr[][] = new int[][]{
								{1 ,2 ,3 ,4 }, 
								{5 ,6 ,7 ,8 }, 
								{9 ,10,11,12}, 
								{13,14,15,16}
					};
		PrintSpiralIn2DMatrix psdM = 			
		new PrintSpiralIn2DMatrix();
		psdM.printSpiral(arr);
		System.out.println("");
		int arr1[][] = {{1,2},{3,4}};
		psdM.printSpiral(arr1);	
	}
}

- zuned485 August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length<1) return;
        return helper(matrix, 0, 0, matrix[0].length-1, matrix.length-1);
    }
    public void helper(int[][] matrix, int left, int top, int right, int bottom) {
        
        if(left > right || top > bottom)
            return;
        
        for(int j=left; j<=right; j++)
            System.out.print(matrix[top][j]);  
        top++;

        for(int i=top; i<=bottom; i++)
            System.out.print(matrix[i][right]);
        right--;

        if(bottom>=top)
            for(int j=right; j>=left; j--)
                System.out.print(matrix[bottom][j]);
            
        bottom--;
        if(right>=left)
            for(int i=bottom; i>=top; i--)
                System.out.print(matrix[i][left]);
        left++;

        helper(matrix, l, left, top, right, bottom);
    }

- Clk September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SpiralWayMatrix {

private static final int RIGHT = 0;
private static final int DOWN = 1;
private static final int LEFT = 2;
private static final int UP = 3;
private static boolean[][] visited;

public static void main(String[] args) {
//example 1
int[][] m = new int[][]{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
//example 2
int[][] m1 = new int[][]{
{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}
};

printSpiral(m);

}

static void printSpiral(int[][] m) {

visited = new boolean[m.length][m[0].length];
printRec(m,0,0,RIGHT,1);

}

private static void printRec(int[][] m, int i, int j, int direction,int element) {

if (element==m.length*m[0].length) {
System.out.println(m[i][j]);
return;
}

if (direction==RIGHT) {
if (canGoDirection(m,i,j+1,direction)) {
System.out.println(m[i][j]);
visited[i][j]=true;
printRec(m, i, j+1, direction,element+1);
} else {
printRec(m, i, j, direction+1,element);
}
} else if (direction==DOWN) {
if (canGoDirection(m,i+1,j,direction)) {
System.out.println(m[i][j]);
visited[i][j]=true;
printRec(m, i+1, j, direction,element+1);
} else {
printRec(m, i, j, direction+1,element);
}
} else if (direction==LEFT) {

if (canGoDirection(m,i,j-1,direction)) {
System.out.println(m[i][j]);
visited[i][j]=true;
printRec(m, i, j-1, direction,element+1);
} else {
printRec(m, i, j, direction+1,element);
}
} else if (direction==UP) {

if (canGoDirection(m,i-1,j,direction)) {
System.out.println(m[i][j]);
visited[i][j]=true;
printRec(m, i-1, j, direction,element+1);
} else {
printRec(m, i, j, 0,element);
}
}
}

private static boolean canGoDirection(int[][] m, int i, int j, int direction) {
if (direction==RIGHT) {
if (j>m[i].length-1) {
return false;
} else if (visited[i][j]) {
return false;
} else {
return true;
}
} else if (direction==DOWN) {
if (i>m.length-1) {
return false;
} else if (visited[i][j]) {
return false;
}else {
return true;
}
} else if (direction==LEFT) {
if (j<0) {
return false;
} else if (visited[i][j]) {
return false;
} else {
return true;
}
} else if (direction==UP) {
if (i<0) {
return false;
} else if (visited[i][j]) {
return false;
} else {
return true;
}
}
return false;
}


}

- DobryiEeh December 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SpiralWayMatrix {

	private static final int RIGHT = 0;
	private static final int DOWN = 1;
	private static final int LEFT = 2;
	private static final int UP = 3;
	private static boolean[][] visited;
	
	public static void main(String[] args) {
	      //example 1
        int[][] m = new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        //example 2
        int[][] m1 = new int[][]{
                {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}
        };
        
        printSpiral(m);

	}
	
	static void printSpiral(int[][] m) {
		
		visited = new boolean[m.length][m[0].length];
		printRec(m,0,0,RIGHT,1);
		
	}

	private static void printRec(int[][] m, int i, int j, int direction,int element) {
	
		if (element==m.length*m[0].length) {
			System.out.println(m[i][j]);
			return;
		}
		
		if (direction==RIGHT) {
			if (canGoDirection(m,i,j+1,direction)) {
				System.out.println(m[i][j]);
				visited[i][j]=true;
				printRec(m, i, j+1, direction,element+1);
			} else {
				printRec(m, i, j, direction+1,element);
			}
		} else if (direction==DOWN) {
			if (canGoDirection(m,i+1,j,direction)) {
				System.out.println(m[i][j]);
				visited[i][j]=true;
				printRec(m, i+1, j, direction,element+1);
			} else {
				printRec(m, i, j, direction+1,element);
			}
		} else if (direction==LEFT) {
			
			if (canGoDirection(m,i,j-1,direction)) {
				System.out.println(m[i][j]);
				visited[i][j]=true;
				printRec(m, i, j-1, direction,element+1);
			} else {
				printRec(m, i, j, direction+1,element);
			}
		} else if (direction==UP) {
			
			if (canGoDirection(m,i-1,j,direction)) {
				System.out.println(m[i][j]);
				visited[i][j]=true;
				printRec(m, i-1, j, direction,element+1);
			} else {
				printRec(m, i, j, 0,element);
			}
		}
	}

	private static boolean canGoDirection(int[][] m, int i, int j, int direction) {
		if (direction==RIGHT) {
			if (j>m[i].length-1) {
				return false;
			} else if (visited[i][j]) {
				return false;
			} else {
				return true;
			}
		} else if (direction==DOWN) {
			if (i>m.length-1) {
				return false;
			} else if (visited[i][j]) {
				return false;
			}else {
				return true;
			}
		} else if (direction==LEFT) {
			if (j<0) {
				return false;
			} else if (visited[i][j]) {
				return false;
			} else {
				return true;
			} 
		} else if (direction==UP) {
			if (i<0) {
				return false;
			} else if (visited[i][j]) {
				return false;
			} else {
				return true;
			}
		}
		return false;
	}
	
	
	}

- DobryiEeh December 07, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More