Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
#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;
}
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.
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;
}
#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;
}
#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;
}
#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;
}
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;
}
}
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);
}
}
}
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
}
}
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);
}
}
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);
}
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;
}
}
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;
}
}
- Makarand August 26, 2017