Microsoft Interview Question
Software Engineer in Testspublic static void PrintMatrixClockwise(int[,] a, int columns, int rows )
{
int sri = 0, eri = rows-1;
int sci = 0, eci = columns-1;
for (int i = sri, j= sci; j <= eci;j++ )
{
Console.Write(a[i,j] + " ");
}
for (int j = eci, i = sri + 1; i <= eri - 1; i++)
{
Console.Write(a[i, j] + " ");
}
for (int j = eci, i = eci ; j >= sci - 1 && j !=0; --j)
{
Console.Write(a[i, j] + " ");
}
for (int i = eri, j = sci; i >= sci-1 && i != 0 ; --i)
{
Console.Write(a[i, j] + " ");
}
}
static void printmatrixspirally(int[,] a, int rows, int cols)
{
int currRow = 0, currCol = 0;
int rowMax = rows - 1;
int colMax = cols - 1;
while(!(currRow <0 || currRow>rowMax || currCol <0 || currCol > colMax))
{
for (; currCol <= colMax; currCol++)
Console.WriteLine(a[currRow, currCol]);
for (currCol--, currRow++; currRow <= rowMax; currRow++)
Console.WriteLine(a[currRow, currCol]);
currRow--;
currCol--;
if (currRow > (rows - 1) - rowMax && currCol >= (cols - 1) - colMax)
{
for (; currCol >= (cols - 1) - colMax; currCol--)
Console.WriteLine(a[currRow, currCol]);
for (currCol++, currRow--; currRow > (rows - 1) - rowMax; currRow--)
Console.WriteLine(a[currRow, currCol]);
}
currRow++;
currCol++;
rowMax--;
colMax--;
}
}
//adding some comments with some correction...I have checked with wide variety of inputs, this is in c#, please let me know if this is failing for any input..
static void printmatrixspirally(int[,] a, int rows, int cols)
{
int currRow = 0, currCol = 0;
int rowMax = rows - 1;
int colMax = cols - 1;
//loop until currRow or currCol is out of last visited boundary saved in rowMax and colMax
while(!(currRow <0 || currRow>rowMax || currCol <0 || currCol > colMax))
{
//loop to get the elements in top row
for (; currCol <= colMax; currCol++)
Console.WriteLine(a[currRow, currCol]);
//loop to get teh elements in right column
for (currCol--, currRow++; currRow <= rowMax; currRow++)
Console.WriteLine(a[currRow, currCol]);
currRow--;
currCol--;
//make sure currRow and currCol have not already been visited.
if (currRow > (rows - 1) - rowMax && currCol >= (cols - 1) - colMax)
{
for (; currCol >= (cols - 1) - colMax; currCol--)
Console.WriteLine(a[currRow, currCol]);
for (currCol++, currRow--; currRow > (rows - 1) - rowMax; currRow--)
Console.WriteLine(a[currRow, currCol]);
currRow++;
currCol++;
}
//modify the last visited row and column.
rowMax--;
colMax--;
}
}
tested with few cases.
base idea is: we have 4 loops within a big loop; each time we print a row/column, we shrink the matrix (by left boundary, right, up or down: it depends) by 1. <-- in this way we gradually narrow down our matrix...
void print_matrix_spirally(int **m, int r, int c){
int left=0,right=c-1,top=0,down=r-1;
while(left<=right&&top<=down){
bool sw1=false,sw2=false,sw3=false,sw4=false;
for(int i=left;i<=right;i++){
cout<<m[top][i]<<" ";
if(!sw1)
sw1=true;
}
if(sw1)
top++;
for(int i=top;i<=down;i++){
cout<<m[i][right]<<" ";
if(!sw2)
sw2=true;
}
if(sw2)
right--;
for(int i=right;i>=left;i--){
cout<<m[down][i]<<" ";
if(!sw3)
sw3=true;
}
if(sw3)
down--;
for(int i=down;i>=top;i--){
cout<<m[i][left]<<" ";
if(!sw4)
sw4=true;
}
if(sw4)
left++;
}
}
The same question was asked in microsoft interview again. Here is the java code and some test runs:
public class PrintMatrixSpiral {
public static void main(String[] args) {
int a[][] = { { 1 ,2,3}, { 4,5,6 }, { 7,8,9 }, {10,11,12} };
printSpiral(a, 4, 3);
int b[][] = { { 1 ,2,3,4}, { 4,5,6,7 }, { 8,9,10,11 }, {12,13,14,15} };
printSpiral(b, 4, 4);
int c[][] = { { 1 ,2,3,4}};
printSpiral(c, 1, 4);
int d[][] = { { 1} ,{2},{3},{4}};
printSpiral(d, 4, 1);
int e[][] = { {1}};
printSpiral(e, 1, 1);
}
private static void printSpiral(int[][] a, int m, int n) {
int x = 0;
int y = 0;
int i = 0;
int j = 0;
while (x <= m / 2) {
// step1: print the row
i = 0 + x;
for (j = 0 + y; j <= (n - 1) - y; j++) {
System.out.print(a[i][j] + " ");
}
// step 2: print the right column
j = (n - 1) - y;
for (i = x + 1; i <= (m - 1) - (x + 1); i++) {
System.out.print(a[i][j] + " ");
}
// step3: print bottom row
i = m - 1 - x;
if (i > 0 + x) {
for (j = (n - 1) - y; j >= (0 + y); j--) {
System.out.print(a[i][j] + " ");
}
}
// step 4: print left column
j = (0 + y);
if (j < (n - 1) - y) {
for (i = (m - 1) - (x + 1); i >= (x + 1); i--) {
System.out.print(a[i][j] + " ");
}
}
x++;
y++;
}
System.out.println();
}
}
//Print the martix clockwise using direction of navigation.
enum dir {
left, right, down, up
};
public static void printSpirally(int a[][], int row, int col) {
int rowTop = 0, colTop = 0;
dir d = dir.right;
for (int k = 0, i = rowTop, j = colTop; k < row / 2; k++) {
do {
System.out.print(a[i][j]);
switch (d) {
case right:
if (j < col - 1) {
j++;
} else {
i++;
d = dir.down;
}
break;
case down:
if (i < row - 1) {
i++;
} else {
j--;
d = dir.left;
}
break;
case up:
if (j > 0) {
j--;
} else {
i--;
d = dir.up;
}
break;
default:
if (i > 0) {
i--;
}
break;
}
} while (i != rowTop && j != colTop);
System.out.println();
i += 1;
j += 1;
}
}
int a[4][4] = { {1,2,3,4 },
- manoj gupta June 15, 2010{5,6,7,8},
{9,10,11,12},
{13,14,15,16} };
int _tmain(int argc, _TCHAR* argv[])
{
int i = 0;
int j =0;
int totalElems = 4*4;
enum Direction{l2r,t2b,r2l,b2t};
int numFlips[4] = {0,0,0,0};
Direction d = l2r;
while(totalElems--)
{
std::cout<<a[i][j]<<" , ";
switch(d)
{
case l2r:
{
if ( j == 3 - numFlips[d])
{
++numFlips[d];
d = t2b;
i++;
std::cout<<"\n";
}
else
j++;
} break;
case t2b:
{
if ( i == 3 - numFlips[d])
{
++numFlips[d];
d = r2l;
--j;
std::cout<<"\n";
}
else
i++;
} break;
case r2l:
{
if ( j == numFlips[d])
{
++numFlips[d];
d = b2t;
--i;
std::cout<<"\n";
}
else
--j;
} break;
case b2t:
{
if ( i == numFlips[d] + 1)
{
++numFlips[d];
d = l2r;
j++;
std::cout<<"\n";
}
else
--i;
} break;
}
};
return 0;
}