Amazon Interview Question
Country: United States
Interview Type: Phone Interview
//I have modfied since result is not required, also some local variable should be moved outside
public static void circularWay (int[][] matrix) { int[][] hash = new int[matrix.length][matrix[0].length]; int[][] moves = new int[][] {{0,1},{1,0},{0,-1},{-1,0}}; int i = 0;
int j = 0;
int m = 0;
int row;
int column;
while (hash[i][j] == 0) { row = i + moves[m][0];
column = j + moves[m][1]; if ((row < matrix.length) && (column < matrix[0].length) && (row >= 0) && (column >= 0) && (hash[row][column] == 0)) { System.out.print( matrix[i][j]+" "); hash[i][j] = 1; i = row;
j = column; } else { m++; if (m > 3) m = 0; row = i + moves[m][0]; column = j + moves[m][1]; if ((hash[row][column] != 0)) { System.out.print(matrix[i][j]+" "); hash[i][j] = 1; } }
}
}
//reformatting for making more readable
//I have modfied since result is not required, also some local variable should be moved outside
public static void circularWay (int[][] matrix) {
int[][] hash = new int[matrix.length][matrix[0].length];
int[][] moves = new int[][] {{0,1},{1,0},{0,-1},{-1,0}};
int i = 0; int j = 0;
int m = 0;
int row;
int column;
while (hash[i][j] == 0) {
row = i + moves[m][0];
column = j + moves[m][1];
if ((row < matrix.length) && (column < matrix[0].length)
&& (row >= 0) && (column >= 0)
&& (hash[row][column] == 0)) {
System.out.print( matrix[i][j]+" ");
hash[i][j] = 1;
i = row;
j = column;
} else {
m++;
if (m > 3) m = 0;
row = i + moves[m][0];
column = j + moves[m][1];
if ((hash[row][column] != 0)) {
System.out.print(matrix[i][j]+" ");
hash[i][j] = 1;
}
}
}
}
public class Printing_Matrix_in_Spiral_Order {
/*
* iven a matrix (2D array) of m x n elements (m rows, n columns),
* write a function that prints the elements in the array in a spiral manner.
* For example:
* int[] test={
* 1, 2, 3, 4,
* 5, 6, 7, 8,
* 9,10,11,12,
* 13,14,15,16
* }
*
* output: 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
*/
public static void showSpiralOrder(int[][] test){
int TopLeftRow=0;
int TopLeftCol=0;
int BottomRightRow=test.length-1;
int BottomRightCol=test[0].length-1;
while(TopLeftRow<=BottomRightRow&&TopLeftCol<=BottomRightCol){
int beginX=TopLeftRow;
int beginY=TopLeftCol;
int endX=BottomRightRow;
int endY=BottomRightCol;
if(beginX==endX){
for(int i=beginY;i<=endY;i++){
System.out.print(test[beginX][i]+" ");
}
}
else if(beginY==endY){
for(int i=beginX;i<=endX;i++){
System.out.print(test[i][beginY]+" ");
}
}
else{
int curCol=beginY;
while(curCol!=endY){
System.out.print(test[beginX][curCol]+" ");
curCol++;
}
int curRow=beginX;
while(curRow!=endX){
System.out.print(test[curRow][endY]+" ");
curRow++;
}
while(curCol!=beginY){
System.out.print(test[endX][curCol]+" ");
curCol--;
}
while(curRow!=beginX){
System.out.print(test[curRow][beginY]+" ");
curRow--;
}
}
TopLeftRow++;
TopLeftCol++;
BottomRightRow--;
BottomRightCol--;
}
}
public static void main(String[] args) {
int[][] test={
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9,10,11,12},
{13,14,15,16}
};
showSpiralOrder(test);
}
}
The popup might be annoying, but it is useful.
"It looks like you're typing some code..."
use "
" and "
"
#python code
#works for any sized matrixes
EAST, WEST, NORTH, SOUTH = range(4)
step = [(+1,0), (-1,0), (0,-1), (0, +1)]
data = [[1,2,3], [8,9,4], [7,6,5]]
#data = [[1,2,3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 8]]
rows = len(data)
cols = len(data[0])
movements = []
def gen_movements(rows, cols):
steps_east = cols-1
steps_south = rows-1
steps_west = steps_east
steps_north = steps_south-1
movements.extend([EAST for x in range(steps_east)])
movements.extend([SOUTH for x in range(steps_south)])
movements.extend([WEST for x in range(steps_west)])
movements.extend([NORTH for x in range(steps_north)])
if((cols-2) > 0 or (rows-2) >0):
movements.append(EAST)
gen_movements(rows-2, cols-2)
gen_movements(rows, cols)
print movements
r = 0
c = 0
print data[r][c]
for i in movements:
delta_c, delta_r = step[i]
r = r+delta_r
c = c+delta_c
print data[r][c]
public class CircularPrint {
/**
* @param args
*/
public static void main(String[] args) {
//int[][] input = {{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};
int[][] input = {{1,2,3},{8,9,4},{7,6,5}};
int horMin = 0;
int horMax = input.length-1;
int verMin = 0;
int verMax = input[0].length-1;
for (;horMin<horMax && verMin<verMax;) {
boolean incr = true;
int i=verMin,j=horMin;
for (; (i<verMax && incr) || (j<horMax && incr)
|| (i>verMin && !incr) || (j>horMin && !incr);) {
if (incr) {
if (j>=horMax) {
System.out.println(input[i++][horMax]);
} else {
System.out.println(input[verMin][j++]);
}
} else {
if (j<=horMin) {
System.out.println(input[i--][horMin]);
} else {
System.out.println(input[verMax][j--]);
}
}
if (incr) {
incr = !(i==verMax && j==horMax);
}
}
horMin++;
horMax--;
verMin++;
verMax--;
}
if (horMin==horMax && verMin==verMax) {
System.out.println(input[verMin][horMin]);
}
}
}
#include<stdio.h>
int main(void)
{
int row=4;
int col=4;
int i=0,j=0,k=0;
int down=0,right=0,up=0,left=0;
int a[row][col];
int rmax,cmax;
int rmin,cmin;
int left_ind=-1;
for(i=0;i<row;i++)
for(j=0;j<col;j++)
a[i][j]=10*i+j;
printf("Array\n");
for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%3d ",a[i][j]);
printf("\n");
}
i=0;j=0;
rmax=row;cmax=col;
rmin=-1;cmin=0;
down=1;
for(k=0;k<row*col;k++){
if(left){
printf("%3d",a[i][j--]);
if(j==cmin){
left=0;
down=1;
cmin++;
j++;i++;
left_ind=k;
}
}
if(up){
printf("%3d",a[i--][j]);
if(i==rmin){
up=0;
left=1;
rmin++;
i++;j--;
}
}
if(right){
printf("%3d",a[i][j++]);
if(j==cmax){
right=0;
up=1;
cmax--;
j--;i--;
}
}
if(down && k!=left_ind){
printf("%3d",a[i++][j]);
if(i==rmax){
down=0;
right=1;
rmax--;
i--;j++;
}
}
}
printf("\n");
return 0;
}
// solution with three loops
void printCircularOrder (int **M, int rows, int cols)
{
int i,j;
int downRowLimit,upRowLimit;
int forColLimit, revColLimit;
bool fForward, fDown;
i = j = 0;
forColLimit = cols;
revColLimit = j;
downRowLimit = rows;
upRowLimit = i;
fForward = true;
fDown = true;
while ( (revColLimit <= forColLimit) && (upRowLimit <= downRowLimit))
{
for (j=i; (fForward? j <= forColLimit : j >= revColLimit); (fForward? j++ : j--)
print ("%d",M[i][j]);
if (fForward)
{
--forColLimit; // since this column would now be traversed by next time
fForward = false; // next time traverse backwards
}
else
{
++revColLimit; // since this column would be traversed by next time
fForward = true; // next time travel forwards
}
for (i=j; (fDown? i<= downRowLimit : i >= upRowLimit); (fDown? i++ : i--)
print ("%d", M[i][j]);
if (fDown)
{
--downRowLimit; //this row would be traversed in next iteration
fDown = false;
}
else
{
++upRowLimit;
fDown = true;
}
}
}
#include <stdio.h>
#include <string.h>
#define DIR_CNT 4
void printCircular(int **matrix, int height, int width)
{
int dir[DIR_CNT][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int h = 0, w = 0;
int dirIndex = 0;
int newH, newW;
bool *bPrinted;
bPrinted = new bool[height * width];
memset(bPrinted, false, height * width * sizeof(bool));
for (int i = 1; i <= height * width; i++)
{
printf("%d ", *((int *)matrix + h * width + w));
*(bPrinted + h * width + w) = true;
newH = h + dir[dirIndex][0];
newW = w + dir[dirIndex][1];
if (newH < 0 || newH >= height
|| newW < 0 || newW >= width
|| *(bPrinted + newH * width + newW) == true)
{
dirIndex = (dirIndex + 1) % DIR_CNT;
newH = h + dir[dirIndex][0];
newW = w + dir[dirIndex][1];
}
h = newH;
w = newW;
}
delete[] bPrinted;
}
int main()
{
int matrix[3][3] = {1,2,3,8,9,4,7,6,5};
printCircular((int **)matrix, 3, 3);
return 0;
}
/**
*
*/
package personal.abhijit.trial.general;
/**
* @author Abhijit
*/
public class MatrixPrint {
/**
* @param args
*/
public static void main(String[] args) {
MatrixPrint m = new MatrixPrint();
int[][] matrix = new int[3][3];
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[1][0] = 8;
matrix[1][1] = 9;
matrix[1][2] = 4;
matrix[2][0] = 7;
matrix[2][1] = 6;
matrix[2][2] = 5;
m.printMatrix(matrix);
}
void printMatrix(int[][] matrix) {
if (matrix == null) {
System.out.println("Null matrix");
}
if (matrix.length == 0) {
System.out.println("Empty matrix");
}
int ver = matrix.length;
int hor = matrix[0].length;
int i = 0, j, count = 1, jInit = 0, jCond = hor;
boolean finalBreak = false;
while (true) {
for (j = jInit;;) {
int div = (count) / 4, rem = count % 4;
if (rem == 1 || rem == 2) {
if (j == jInit && j >= jCond) {
finalBreak = true;
break;
} else if (j >= jCond)
break;
} else {
if (j == jInit && j < jCond) {
finalBreak = true;
break;
} else if (j < jCond) {
break;
}
}
if (rem == 1) {
System.out.println(matrix[i][j] + " ");
if (j == jCond - 1) {
jInit = i + 1;
jCond = ver - div;
break;
}
j++;
}
if (rem == 2) {
System.out.println(matrix[j][i] + " ");
if (j == jCond - 1) {
jInit = i - 1;
jCond = div;
break;
}
j++;
}
if (rem == 3) {
System.out.println(matrix[i][j] + " ");
if (j == jCond) {
jInit = i - 1;
jCond = (count + 1) / count;
break;
}
j--;
}
if (rem == 0) {
System.out.println(matrix[j][i] + " ");
if (j == jCond) {
jInit = i + 1;
jCond = hor - div;
break;
}
j--;
}
}
if (finalBreak)
break;
i = j;
count++;
}
}
}
class Program
{
static void Main(string[] args)
{
int[][] matrix = new int[3][] { new int[] { 1, 2, 3, 4}, new int[] { 5, 6, 7, 8 }, new int[] { 9, 10, 11, 12 } };
PrintMatrixCircle(matrix);
Console.Read();
}
public static void PrintMatrixCircle(int[][] matrix)
{
if (matrix.Length == 0) return;
if (matrix[0].Length == 0) return;
int numOfRows = matrix.Length;
int numOfCols = matrix[0].Length;
int loopNdx = 0;
while (numOfRows > 0 && numOfCols > 0)
{
// iterate top from left to rigth
int i = loopNdx;
int j = loopNdx;
for (; j < numOfCols + loopNdx; j++)
{
Console.WriteLine(matrix[i][j]);
}
// iterate right from top to bottom
i = i + 1;
j = numOfCols - 1;
for (; i < numOfRows + loopNdx; i++)
{
Console.WriteLine(matrix[i][j]);
}
// iterate bottom from right to left
i = numOfRows - 1;
j = j - 1;
for (; j > loopNdx - 1; j--)
{
Console.WriteLine(matrix[i][j]);
}
// iterate left from bottom to top
i = i - 1;
j = loopNdx;
for (; i > loopNdx; i--)
{
Console.WriteLine(matrix[i][j]);
}
numOfRows -= 2;
numOfCols -= 2;
loopNdx++;
}
}
}
given a NxN matrix, we can visit the first N elements in the first row from the top left position, then visit the (N-1) elements in the outer right edge, then another (N-1) elements in the outer bottom edge, then (N-2) elements in the outer left edge, then (N-2) elements in the second outer upper edge, .... , keep going down to visiting 2 elements for 2 times and keep flipping the edge we visit...
pesudo code:
Public Static int[] genVisitingOrder(int n){
if (n <= 2) {return null;}
int[] rtr = new int[(n-1)*2]();
int[0] = n;
for (int i = 1; i <= (n-1)*2; ++i){
int[i] = Math.Ceil((((n-1)*2) - i + 1) / 2);
}
int[(n-1)*2-1] = 2;
}
Public Static void printMatrix(int[][] matrix){
int x=0, y=0;
boolean dec = false; vertical = true;
int[] visitOrder = genVisitingOrder(matrx[0].size);
for (int i = 0; i < visitOrder.size; ++i){ // the first loop used
while (visitOrder[i]-- > 0){ // the second loop
int moving_point;
vertical ? moving_point = x : moving_point = y;
System.out.print(matrix[x][y]);
dec? --moving_point : ++moving_point;
vertical? x = moving_point : y = moving_point;
}
}
}
time complexity O(n^2), it;s the best we can do given we've got n^2 elements that we have to traverse.
Hey here is a simple code in c/c++, m and n represent no. of rows and columns,
there are four conditions inside the second loop which cover all four boundary we have to traverse each time.
circular_printer(int **arr, int m, int n)
{
for(int i= 0 ; i< (m+1)/2; i++)
{
int col=i,row=i;
std::cout<<"Value of i "<<i<<"\n";
do
{
if (row==i && col<n-i-1)
{
std::cout<<arr[row][col]<<" ";
col++;
}
else if (col==n-i-1 && row<m-1-i)
{
std::cout<<"sec"<<arr[row][col]<<" ";
row++;
}
else if (row==m-i-1 && col>i)
{
std::cout<<arr[row][col]<<" ";
col--;
}
else if (col==i && row>i)
{
std::cout<<arr[row][col]<<" ";
row--;
}
else std::cout<<arr[row][col]<<" ";
}while (col!=i || row!=i);
}
}
one implementation, if two loops meant two nested loops i.e O(n^2).
#include<cstdio>
#define MAX 100
int main()
{
//freopen("input.txt","r",stdin);
int n,a[MAX][MAX],i,j;
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
int start_i=1,end_i=n,start_j=1,end_j=n;
for(i=start_i;i<=(n+1)/2;i++)
{
for(j=start_j;j<end_j;j++)
printf("%d ",a[i][j]);
for(;i<end_i;i++)
printf("%d ",a[i][j]);
for(;j>start_j;j--)
printf("%d ",a[i][j]);
for(;i>start_i;i--)
printf("%d ",a[i][j]);
start_i++;end_i--;start_j++;end_j--;
}
return 0;
}
package testapps;
import java.util.Arrays;
public class TestApps {
public static void main(String args[]) {
int[][] matrix = new int[][]{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}};
int columnLen = matrix.length;
int rowLen = matrix[0].length;
int totalLen = rowLen * columnLen;
int[] answer = new int[totalLen];
int posX = 0, posY = 0;
int offsetLeft = 0, offsetDown = rowLen, offsetRight = columnLen, offsetUp = 0;
Direction direction = Direction.RIGHT;
boolean cycle = false;
for (int i = 0; i < totalLen; i++) {
switch (direction) {
case RIGHT:
cycle = false;
answer[i] = matrix[posX][posY];
posX++;
if (posX >= offsetRight) {
posX--;
posY++;
offsetUp++;
direction = Direction.DOWN;
}
break;
case DOWN:
answer[i] = matrix[posX][posY];
posY++;
if (posY >= offsetDown) {
posX--;
posY--;
offsetRight--;
direction = Direction.LEFT;
}
break;
case LEFT:
answer[i] = matrix[posX][posY];
posX--;
if (posX < offsetLeft) {
posX++;
posY--;
offsetDown--;
direction = Direction.RIGHT;
}
break;
case UP:
answer[i] = matrix[posX][posY];
posY--;
if (posY < offsetUp) {
posX++;
posY--;
offsetLeft++;
direction = Direction.RIGHT;
}
break;
}
}
System.out.println(Arrays.toString(answer));
}
enum Direction {
LEFT,
DOWN,
RIGHT,
UP
}
}
- JC September 26, 2012public static int[] circularWay (int[][] matrix) { int[] result = new int[matrix.length*matrix[0].length]; int[][] hash = new int[matrix.length][matrix[0].length]; int[][] moves = new int[][] {{0,1},{1,0},{0,-1},{-1,0}}; int i = 0; int j = 0; int m = 0; int pos = 0; while (hash[i][j] == 0) { int row = i + moves[m][0]; int column = j + moves[m][1]; if ((row < matrix.length) && (column < matrix[0].length) && (row >= 0) && (column >= 0) && (hash[row][column] == 0)) { result[pos] = matrix[i][j]; pos++; hash[i][j] = 1; i = row; j = column; } else { m++; if (m > 3) m = 0; row = i + moves[m][0]; column = j + moves[m][1]; if ((hash[row][column] != 0)) { result[pos] = matrix[i][j]; hash[i][j] = 1; } } } return result; }