JP Morgan Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
This simple non-recursive Java method works for 2d arrays of different rows & columns # too (need not be a 4x4, 5x5, but can be 4x5, 5x6, etc too)-
public class ArrayInSpiralOrder {
public static void main(String[] args) {
int array[][] = {
{ 0, 1, 2, 3, 4},
{15, 16, 17, 18, 5},
{14, 23, 24, 19, 6},
{13, 22, 21, 20, 7},
{12, 11, 10, 9, 8}};
printMatrixNonRecursive(array, 5, 5);
}
public static void printMatrixNonRecursive(int array[][], int rows, int cols){
int nCurrentLevel = 0;
int min = (rows < cols) ? rows:cols;
while(nCurrentLevel <= min/2){
for(int j = nCurrentLevel; j < cols - nCurrentLevel - 1; j++){
System.out.print(array[nCurrentLevel][j] + " ");
}
for(int i = nCurrentLevel; i < rows - nCurrentLevel - 1; i++) {
System.out.print(array[i][cols - nCurrentLevel - 1] + " ");
}
for(int j = cols - nCurrentLevel - 1; j > nCurrentLevel; j--){
System.out.print(array[rows - nCurrentLevel - 1][j] + " ");
}
for(int i = rows - nCurrentLevel - 1; i > nCurrentLevel; i-- ){
System.out.print(array[i][nCurrentLevel] + " ");
}
nCurrentLevel++;
}
}
}
This can be recursively printed with this method -
public class ArrayInSpiralOrder {
public static void main(String[] args) {
int array[][] = {
{ 0, 1, 2, 3, 4},
{15, 16, 17, 18, 5},
{14, 23, 24, 19, 6},
{13, 22, 21, 20, 7},
{12, 11, 10, 9, 8}};
printMatrixRecursive(array, 0, 0, 4, 4);
}
public static void printMatrixRecursive(int array[][], int startRow, int startCol, int endRow, int endCol)
{
if(startRow > endRow || startCol > endCol)
return;
for(int i=startRow, j=startCol; j<endCol; j++)
System.out.println(array[i][j] + " ");
for(int i=startRow, j=endCol; i<=endRow; i++)
System.out.println(array[i][j] + " ");
for(int i=endRow, j=endCol - 1; j>startCol; j--)
System.out.println(array[i][j] + " ");
for(int i=endRow, j=startCol; i>startRow; i--)
System.out.println(array[i][j] + " ");
printMatrixRecursive(array, startRow+1, startCol+1, endRow-1, endCol-1);
}
}
The same principle but write to char array
//---------------------------------------------------------------------------------
// Write a function with the following signature that, given a matrix of integers,
// builds a string with the entries of that matrix appended in clockwise order.
//---------------------------------------------------------------------------------
#include <iostream>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
void AppendChar(char *OutBuffer, int value, int & charIdx)
{
char buffer[33];
_itoa(value, buffer, 10);
strcpy(OutBuffer + charIdx, buffer);
charIdx += strlen(buffer);
strcpy(OutBuffer + charIdx++, ",");
}
void GetRingValues(int * Matrix, int IndexRing, int NumRows, int NumColumns,
char *OutBuffer, int &charIdx)
{
const int StartIndex = IndexRing * NumColumns + IndexRing;
int ArrayMaxIndex = NumRows * NumColumns;
int CurrentIndex, Limit;
CurrentIndex = StartIndex;
// iterate L2R
Limit = StartIndex + (NumColumns - IndexRing * 2);
for (int Index = CurrentIndex; Index < Limit; ++Index)
{
AppendChar(OutBuffer, Matrix[Index], charIdx);
CurrentIndex = Index;
}
// iterate Top2Bottom
bool bHorizontalShift = false;
Limit = ArrayMaxIndex - (IndexRing * NumColumns);
for (int Index = CurrentIndex + NumColumns; Index < Limit;
Index += NumColumns, bHorizontalShift = true)
{
AppendChar(OutBuffer, Matrix[Index], charIdx);
CurrentIndex = Index;
}
// iterate R2L
bool bLeftToRightShift = false;
Limit = CurrentIndex - (NumColumns - IndexRing * 2);
for (int Index = CurrentIndex - 1; bHorizontalShift && Index > Limit;
--Index, bLeftToRightShift = true)
{
AppendChar(OutBuffer, Matrix[Index], charIdx);
CurrentIndex = Index;
}
// iterate B2T
for (int Index = CurrentIndex - NumColumns;
bLeftToRightShift && Index > StartIndex; Index -= NumColumns)
{
AppendChar(OutBuffer, Matrix[Index], charIdx);
}
}
void BuildStringFromMatrix(int *Matrix,int NumRows,int NumColumns,char *OutBuffer)
{
if (Matrix != NULL && OutBuffer != NULL && NumRows > 0 && NumColumns > 0)
{
int ChrIdx = 0;
int NumCircles = ceil(((NumRows < NumColumns) ? NumRows : NumColumns)/2.f);
for (int Index = 0; Index < NumCircles; ++Index)
{
GetRingValues(Matrix, Index, NumRows, NumColumns,
OutBuffer, ChrIdx);
}
}
}
void main()
{
int Matrix[] = {2, 3, 4, 13, 17,
8, 5, 7, 14, 18,
9, 12, 1, 15, 19,
0, 6, 10, 16, 20,
23, 24, 25, 26, 27,
};
// allocate enough space
char *CharArray = new char[1024];
BuildStringFromMatrix(Matrix, 5, 5, CharArray);
std::cout << CharArray << std::endl;
delete [] CharArray;
getch();
}
const int MATRIX_ROW = 4;
void show_matrix()
{
int data[MATRIX_ROW][MATRIX_ROW] = {{1,2,3,4}, {12,13,14,5}, {11,16,15,6}, {10,9,8,7} };
int a = 0, b = MATRIX_ROW-1, c = MATRIX_ROW-1, d = 0;
int choose = 1;
int column = 0, row = 0;
while(a<=c || b>=d)
{
switch(choose)
{
case 1:
{
row = a;
for(column=d; column<=b; ++column)
{
cout << data[row][column] << " ";
}
choose = 2;
a++;
}
break;
case 2:
{
column = b;
for(row=a; row<=c; ++row)
{
cout << data[row][column] << " ";
}
choose = 3;
b--;
}
break;
case 3:
{
row = c;
for(column=b; column>=d; --column)
{
cout << data[row][column] << " ";
}
choose = 4;
c--;
}
break;
case 4:
{
column = d;
for(row=c; row>=a; --row)
{
cout << data[row][column] << " ";
}
choose = 1;
d++;
}
break;
}
}
}
A answer in C,the variable choose is not needed. Just for other direction which to show the variables in matrix.
#include <stdio.h>
void main(){
int A[4][4] = { {1,2,3,4},
{12,13,14,5},
{11,16,15,6},
{10,9,8,7} };
int count=0;
int i=0, j=-1;
int n=4, k=n-1, p=0;
int state=1;
while (count < n*n) {
switch (state) {
case 1:
printf("%d, ", A[i][++j]);
count++;
if (j == k)
state = 2;
break;
case 2:
printf("%d, ", A[++i][j]);
count++;
if (i == k) {
state = 3;
k -= 1;
} break;
case 3:
printf("%d, ", A[i][--j]);
count++;
if (j == p) {
state = 4;
p += 1;
} break;
case 4:
printf("%d, ", A[--i][j]);
count++;
if ( i==p )
state = 1;
break;
}
}
printf("\n");
}
import java.util.*;
public class MatricSnake
{
private static Map<String, String> directionMap = new HashMap<String, String>(4);
static int m, n;
public static void main(String[] args)
{
// TODO Auto-generated method stub
directionMap.put("R", "D");
directionMap.put("D", "L");
directionMap.put("L", "U");
directionMap.put("U", "R");
m = 10;
n = 10;
int count=0;
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
matrix[i][j] = count++;
}
}
MatricSnake ms = new MatricSnake();
ms.populateMatrixSnake(matrix);
}
public void populateMatrixSnake(int[][] matrix)
{
List<Integer> iList = new ArrayList<Integer>(m);
List<Integer> jList = new ArrayList<Integer>(n);
int i = 0;
int j = 0;
int totalCount=0;
String code = "R";
while (true)
{
while (i != m && i >= 0 && j != n && j >= 0 && !iList.contains(i) && !jList.contains(j))
{
if (code.equals("R"))
{
System.out.print(matrix[i][j]+" ");
j++;
totalCount++;
}
else if (code.equals("D"))
{
System.out.print(matrix[i][j]+" ");
i++;
totalCount++;
}
else if (code.equals("L"))
{
System.out.print(matrix[i][j]+" ");
j--;
totalCount++;
}
else if (code.equals("U"))
{
System.out.print(matrix[i][j]+" ");
i--;
totalCount++;
}
}
if (code.equals("R") || code.equals("L"))
{
iList.add(i);
}
else
{
jList.add(j);
}
code = directionMap.get(code);
if (code.equals("D"))
{
j--;
i++;
}
else if (code.equals("L"))
{
i--;
j--;
}
else if (code.equals("U"))
{
j++;
i--;
}
else if (code.equals("R"))
{
i++;
j++;
}
if(totalCount==(n*m))
{
break;
}
}
}
}
public static void printSpirally(int[][] a){
int j = 0;
for (int i = 0; i < a.length ; i++) {
if (i % 2 == 0) {
for (j = 0; j < a[i].length ; j++) {
System.out.print(a[i][j] + ", ");
}
} else {
for (j = a[i].length -1 ; j >= 0; j--) {
System.out.print(a[i][j] + ", ");
}
}
}
}
public class SpiralPrint {
public static class Direction {
public int leftRight = 0;
public int upDown = 0;
public Direction(int leftRight, int upDown) {
this.leftRight = leftRight;
this.upDown = upDown;
}
}
public static final Direction LEFT = new Direction(-1, 0);
public static final Direction RIGHT = new Direction(1, 0);
public static final Direction UP = new Direction(0, -1);
public static final Direction DOWN = new Direction(0, 1);
public static final Direction[] sequence = { RIGHT, DOWN, LEFT, UP };
public static void main(String args[]) {
int [][]value = {{ 1, 2, 03, 04, 05, 6 },
{ 16, 17,18, 19, 20, 7 },
{ 15, 24,23, 22, 21, 8 },
{ 14, 13,12, 11, 10, 9}};
int directionIndex = 0;
int row = 0, col = 0;
Map<String, Boolean> visited = new HashMap<String, Boolean>();
int matrixSize = value.length * value[0].length;
while (true) {
Direction direction = sequence[directionIndex%4];
directionIndex++;
int nrow = row + direction.upDown;
int ncol = col + direction.leftRight;
// Found the end of the matrix, visited all of the nodes
if (visited.keySet().size() == matrixSize)
break;
do {
System.out.print(value[row][col] + " ");
visited.put(row + "," + col, true);
row = nrow;
col = ncol;
nrow = row + direction.upDown;
ncol = col + direction.leftRight;
} while (ncol >= 0 && ncol < value[0].length &&
nrow >= 0 && nrow < value.length &&
!visited.containsKey(nrow + "," + ncol));
}
System.out.println("\nRotations = " + directionIndex);
}
}
def spiral(m):
if (len(m) == 0):
return
top = left = 0
down = len(m) - 1
right = len(m[0]) - 1
def check():
return (top > down or left > right)
while(True):
# Print top row
for i in xrange(left, right+1):
print m[top][i]
top += 1
# Print the rightmost column
for i in xrange(top, down+1):
print m[i][right]
right -= 1
if check(): break
for i in xrange(right, left-1, -1):
print m[down][i]
down -= 1
if check(): break
for i in xrange(down, top-1, -1):
print m[i][left]
left += 1
if check(): break
if __name__ == '__main__':
m = [[1, 2, 3], [12,13,14], [11,16,15], [10,9,8]]
for i in m:
print i
spiral(m)
My solution for printing it both in clockwise and anti-clockwise spiral
def spiral(x, y):
"""
printing the matrix clockwise
"""
rows = [0, x]
columns = [0, y]
def _range(*args):
if args[0] >= args[1]:
raise StopIteration
return range(*args)
while True:
i = rows[0]
for j in _range(*columns):
yield (i, j)
j = columns[1]-1
rows[0] += 1
for i in _range(*rows):
yield (i, j)
columns[1] -= 1
i = rows[1]-1
for j in reversed(_range(*columns)):
yield (i, j)
j = columns[0]
rows[1] -= 1
for i in reversed(_range(*rows)):
yield (i, j)
columns[0] += 1
def anti_spiral(x, y):
"""
printing the matrix anti clockwise
"""
rows = [0, x]
columns = [0, y]
def _range(*args):
if args[0] >= args[1]:
raise StopIteration
return range(*args)
while True:
j = columns[0]
for i in _range(*rows):
yield (i, j)
columns[0] += 1
for j in _range(*columns):
yield (i, j)
rows[1] -= 1
for i in reversed(_range(*rows)):
yield (i, j)
columns[1] -= 1
for j in reversed(_range(*columns)):
yield (i, j)
rows[0] += 1
def iter_spiral(arr):
x = len(arr)
y = len(arr[0])
for i, j in spiral(x, y):
yield arr[i][j]
print
for i, j in anti_spiral(x, y):
yield arr[i][j]
if __name__ == '__main__':
m = [[3, 4, 2, 7], [9, 2, 5, 1], [14, 23, 44, 22], [5, 2, 8, 1]]
for n in iter_spiral(m):
print n,
package intrerview;
public class Spiral {
/**
* @param args
*/
private static int maxRow=5,maxCol=5,minRow=1,minCol=1;
private static int i=1,j=1,value=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
while (true) {
if (minRow > maxRow || minCol > maxCol){
break;
}
if (i==minRow && j==minCol) {
printColInc();
System.out.println("");
} else if (i==minRow && j==maxCol) {
printRowInc();
System.out.println("");
} else if (i==maxRow && j==maxCol) {
printColDec();
System.out.println("");
} else if (i==maxRow && j==minCol) {
printRowDec();
System.out.println("");
}
}
}
private static void printColInc() {
for (; j<=maxCol; j++)
System.out.print(" ("+i+","+j+"):- "+value++);
j--;
i=++minRow;
}
private static void printRowInc() {
for (; i<=maxRow; i++)
System.out.print(" ("+i+","+j+"):- "+value++);
i--;
j=--maxCol;
}
private static void printColDec() {
for (; j>=minCol; j--)
System.out.print(" ("+i+","+j+"):- "+value++);
j++;
i = --maxRow;
}
private static void printRowDec() {
for (; i>=minRow; i--)
System.out.print(" ("+i+","+j+"):- "+value++);
i++;
j=++minCol;
}
}
package intrerview;
public class Spiral {
/**
* @param args
*/
private static int maxRow=5,maxCol=5,minRow=1,minCol=1;
private static int i=1,j=1,value=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
while (true) {
if (minRow > maxRow || minCol > maxCol){
break;
}
if (i==minRow && j==minCol) {
printColInc();
System.out.println("");
} else if (i==minRow && j==maxCol) {
printRowInc();
System.out.println("");
} else if (i==maxRow && j==maxCol) {
printColDec();
System.out.println("");
} else if (i==maxRow && j==minCol) {
printRowDec();
System.out.println("");
}
}
}
private static void printColInc() {
for (; j<=maxCol; j++)
System.out.print(" ("+i+","+j+"):- "+value++);
j--;
i=++minRow;
}
private static void printRowInc() {
for (; i<=maxRow; i++)
System.out.print(" ("+i+","+j+"):- "+value++);
i--;
j=--maxCol;
}
private static void printColDec() {
for (; j>=minCol; j--)
System.out.print(" ("+i+","+j+"):- "+value++);
j++;
i = --maxRow;
}
private static void printRowDec() {
for (; i>=minRow; i--)
System.out.print(" ("+i+","+j+"):- "+value++);
i++;
j=++minCol;
}
}
def spiral(m):
rows, cols = len(m), min([len(row) for row in m])
row = 0
while row < rows/2:
for i in m[row][row:cols-row]:
yield i
for j in m[row+1:rows-1-row]:
yield j[cols-1-row]
for i in reversed(m[rows-1-row][row:cols-row]):
yield i
for j in reversed(m[row+1:rows-1-row]):
yield j[row]
row += 1
from __future__ import print_function
[print(i) for i in spiral([[3, 4, 2, 7], [9, 2, 5, 1], [14, 23, 44, 22], [5, 2, 8, 1]])]
Java Solution for the problem mentioned. This code displays the elements of any dimension in spiral order.
import java.util.Scanner;
public class SpiralMatrix {
int[][] matrix; /*= {{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};*/
Scanner scan = new Scanner(System.in);
int numRows = 4, numCols = 4;
int count = 0;
public static void main(String[] args) {
SpiralMatrix sm = new SpiralMatrix();
sm.buildMatrix();
System.out.println("Matrix is....");
sm.printMatrix();
System.out.println("Matrix in spiral order...\n");
sm.printSpiralMatrix(sm.matrix, sm.numRows, sm.numCols);
}
private void printSpiralMatrix(int[][] matrix, int m, int n) {
for(int i = count, j = 0 + count; j < n - count; j++) {
System.out.print(matrix[i][j] + " ");
}
for(int i = count + 1, j = n-1-count; i < m-count; i++) {
System.out.print(matrix[i][j] + " ");
}
for(int i = m-1-count, j = n-2-count; j > count; j--) {
System.out.print(matrix[i][j] + " ");
}
for(int i = m-1-count, j = count; i > count; i--) {
System.out.print(matrix[i][j] + " ");
}
count++;
if(count <= (m/2)) {
printSpiralMatrix(matrix, m, n);
}
}
private void printMatrix() {
for(int i = 0; i < numRows; i++) {
for(int j = 0; j < numCols; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.print("\n");
}
}
private void buildMatrix() {
System.out.print("Enter the Row size of matrix: ");
numRows = scan.nextInt();
System.out.print("Enter the Column size of matirx: ");
numCols = scan.nextInt();
matrix = new int[numRows][numCols];
System.out.println("Enter the value to populate " + numRows + "x" + numCols + " matrix");
for(int i = 0; i < numRows; i++) {
for(int j = 0; j < numCols; j++) {
System.out.print("Enter the value for matrix["+i+"]["+j+"]: ");
matrix[i][j] = scan.nextInt();
}
}
scan.close();
}
}
public class SpiralMatrix {
public static void main(String[] args) {
int arr[][] = {{1,2,3,4,5},{10,9,8,7,6},{11,12,13,14,15},{20,19,18,17,16},{21,22,23,24,25}};
int rowCount = arr.length;
int spiralLevel = arr.length -2;
int row = 1;
//Print first part
int count = arr[0].length;
for (int i = 0; i < count; i++) {
System.out.print(arr[0][i] + " ");
}
//Print second part
for (int i = 1; i < rowCount-1; i++) {
int index = arr[i].length;
System.out.print(arr[i][index-1] + " ");
}
//Print third part
int lastRowCol = arr[rowCount-1].length - 1;
while (lastRowCol >= 0) {
System.out.print(arr[rowCount -1][lastRowCol] +" ");
lastRowCol--;
}
//Print fourth part
int rowCount1 = rowCount - 2;
while(rowCount1 > 0){
System.out.print(arr[rowCount1][0] + " ");
rowCount1 --;
}
//print spiral
for (int i = 0; i < spiralLevel; i++) {
if(row%2 != 0){
for (int j = 1; j < arr[row].length-1; j++) {
System.out.print(arr[row][j]+ " ");
}
}else{
for (int j = arr[row].length-2; j >0; j--) {
System.out.print(arr[row][j]+ " ");
}
}
row++;
}
}
}
package com.sanjeet.general;
public class SpiralPrint2DArray {
public static void main(String[] args) {
int[][] A = { { 1, 2, 3, 4 },
{ 12, 13, 14, 5 },
{ 11, 16, 15, 6 },
{ 10, 9, 8, 7 } };
int[][] A1 = { { 1, 12, 3, 4 },
{ 2, 13, 14, 15 },
{ 7, 9, 5, 6 },
{ 10, 16, 8, 11 } };
printSpiral(A); //Prints 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
System.out.println();
printSpiral(A1);//1, 12, 3, 4, 15, 6, 11, 8, 16, 10, 7, 2, 13, 14, 5, 9,
}
private static void printSpiral(int[][] a) {
int rowStart = 0, colStart = 0;
int changingRowLength = a.length, changingColLength = a[0].length;
for (int i = rowStart; i < changingRowLength; i++) {
// first row
for (int j = colStart; j < changingColLength; j++) {
System.out.print(a[rowStart][j] + ", ");
}
rowStart++;
// last column
for (int k = rowStart; k < changingRowLength; k++) {
System.out.print(a[k][changingColLength - 1] + ", ");
}
changingColLength--;
// last row
for (int l = changingColLength - 1; l >= colStart; l--) {
System.out.print(a[changingRowLength - 1][l] + ", ");
}
changingRowLength--;
// first column
for (int m = changingRowLength - 1; m >= rowStart; m--) {
System.out.print(a[m][colStart] + ", ");
}
colStart++;
}
}
}
/**
*
*/
package snippet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* @author ya0036
*
*/
public class ArraySort {
public static void main(String[] args) {
Integer [] a ={ 1, 2, 3, 4 };
Integer [] b= { 12, 13, 14, 5 };
Integer [] c= { 11, 16, 15, 6 };
Integer [] d={ 10, 9, 8, 7 };
List<Integer> aL = Arrays.asList(a);
List<Integer> bL = Arrays.asList(b);
List<Integer> cL = Arrays.asList(c);
List<Integer> dL = Arrays.asList(d);
List<Integer> fL = new ArrayList<Integer>();
fL.addAll(aL);
fL.addAll(bL);
fL.addAll(cL);
fL.addAll(dL);
Collections.sort(fL);
System.out.println(fL);
}
}
/**
*
*/
package snippet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* @author ya0036
*
*/
public class ArraySort {
public static void main(String[] args) {
Integer [] a ={ 1, 2, 3, 4 };
Integer [] b= { 12, 13, 14, 5 };
Integer [] c= { 11, 16, 15, 6 };
Integer [] d={ 10, 9, 8, 7 };
List<Integer> aL = Arrays.asList(a);
List<Integer> bL = Arrays.asList(b);
List<Integer> cL = Arrays.asList(c);
List<Integer> dL = Arrays.asList(d);
List<Integer> fL = new ArrayList<Integer>();
fL.addAll(aL);
fL.addAll(bL);
fL.addAll(cL);
fL.addAll(dL);
Collections.sort(fL);
System.out.println(fL);
}
}
this is valid only if input is like this, but your solution doesn't work properly for general case.
Can you please mention one or two general case, for which my algorithm/code doesn't work ?
There is no mention of data sorting in the question. It is just a coincidence (IMHO) that spiral printing is resulting in the sorting data. So, I guess your solution is not a generic one. For and example if the input is
[1,12,3,4]
[2,13,14,15]
[7,9,5,6]
[10,16,8,11]
spiral printing would result in 1, 12, 3, 4, 15,6,11,8,16,10,7,2,13,14,5,9.
but your solution which is sorting also will result in 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.
Apology if something has been overlooked by me.
- Rakesh Roy October 10, 2013