Microsoft Interview Question
Software Engineer in Tests#include<stdio.h>
int main()
{
int n;
scanf("%d", &n);
int a[n][n];
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j] = -1;
}
}
int k;
i=0;j=0;
int dir=0;
for(k=1;k<=(n*n);k++)
{
a[i][j] = k;
if(dir==0 && (n==(j+1) || a[i][j+1] != -1 ))
{
dir=1;
i++;
}
else if(dir==1 && ( (i+1)==n || a[i+1][j] != -1 ) )
{
dir = 2;
j--;
}
else if(dir==2 && (j==0 || a[i][j-1] != -1) )
{
dir =3;
i--;
}
else if(dir==3 && (a[i-1][j] != -1) )
{
dir =0;
j++;
}
else if(dir==0)
j++;
else if(dir==1)
i++;
else if(dir==2)
j--;
else if(dir==3)
i--;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%3d ", a[i][j]);
printf("\n");
}
return 0;
}
#include <stdio.h>
#define ROW 5
#define COL 5
void printSpiral (int matrix[ROW][COL])
{
int rightCol=COL-1,downRow=ROW-1;
int leftCol=0,upRow=0,index=0;
int count=ROW*COL;
while(count)
{
while((index<=rightCol)&&(count))
{
printf("[%d]", matrix[upRow][index]);
index++;
count--;
}
upRow++;
index=upRow;
while((index<=downRow)&&(count))
{
printf("[%d]", matrix[index][rightCol]);
index++;
count--;
}
rightCol--;
index=rightCol;
while((index>=leftCol)&&(count))
{
printf("[%d]", matrix[downRow][index]);
index--;
count--;
}
downRow--;
index=downRow;
while((index>=upRow)&&(count))
{
printf("[%d]", matrix[index][leftCol]);
index--;
count--;
}
leftCol++;
index=leftCol;
}
}
int main ()
{
int matrix [ROW][COL] = {
{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}
};
printSpiral(matrix);
printf("\n");
}
<pre lang="" line="1" title="CodeMonkey10349" class="run-this">#include <vector>
#include <memory> // for auto_ptr
#include <cmath> // for the ceil and log10 and floor functions
#include <iostream>
#include <iomanip> // for the setw function
using namespace std;
typedef vector< int > IntRow;
typedef vector< IntRow > IntTable;
auto_ptr< IntTable > getSpiralArray( int dimension )
{
auto_ptr< IntTable > spiralArrayPtr( new IntTable(
dimension, IntRow( dimension ) ) );
int numConcentricSquares = static_cast< int >( ceil(
static_cast< double >( dimension ) / 2.0 ) );
int j;
int sideLen = dimension;
int currNum = 0;
for ( int i = 0; i < numConcentricSquares; i++ )
{
// do top side
for ( j = 0; j < sideLen; j++ )
( *spiralArrayPtr )[ i ][ i + j ] = currNum++;
// do right side
for ( j = 1; j < sideLen; j++ )
( *spiralArrayPtr )[ i + j ][ dimension - 1 - i ] = currNum++;
// do bottom side
for ( j = sideLen - 2; j > -1; j-- )
( *spiralArrayPtr )[ dimension - 1 - i ][ i + j ] = currNum++;
// do left side
for ( j = sideLen - 2; j > 0; j-- )
( *spiralArrayPtr )[ i + j ][ i ] = currNum++;
sideLen -= 2;
}
return spiralArrayPtr;
}
void printSpiralArray( auto_ptr< IntTable >& spiralArrayPtr )
{
size_t dimension = spiralArrayPtr->size();
int fieldWidth = static_cast< int >( floor( log10(
static_cast< double >( dimension * dimension - 1 ) ) ) ) + 2;
size_t col;
for ( size_t row = 0; row < dimension; row++ )
{
for ( col = 0; col < dimension; col++ )
cout << setw( fieldWidth ) << ( *spiralArrayPtr )[ row ][ col ];
cout << endl;
}
}
int main()
{
auto_ptr< IntTable > temp = getSpiralArray( 10 );
printSpiralArray( temp );
}</pre><pre title="CodeMonkey10349" input="yes">
</pre>
package home;
public class SpiralMatrix {
int arr[][] = null;
int c = 1;
int n = 0;
int[][] createSpriralMatrix(int n) {
this.n = n;
arr = new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
arr[i][j] = 0;
moveRight(0,0);
return null;
}
void moveRight(int i, int j) {
if (arr[i][j] != 0)
return;
for (; j < n; j++)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveDown(i + 1, j - 1);
}
void moveDown(int i, int j) {
if (arr[i][j] != 0)
return;
for (; i < n; i++)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveLeft(i - 1, j - 1);
}
void moveLeft(int i, int j) {
if (arr[i][j] != 0)
return;
for (; j >= 0; j--)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveUp(i - 1, j + 1);
}
void moveUp(int i, int j) {
if (arr[i][j] != 0)
return;
for (; i >= 0; i--)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveRight(i + 1, j + 1);
}
public static void main(String args[]){
int n=2;
SpiralMatrix spiralMatrix = new SpiralMatrix();
spiralMatrix.createSpriralMatrix(n);
int arr[][] = spiralMatrix.arr;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
System.out.print(" "+arr[i][j]);
System.out.println("\n");
}
}
}
But stack will grow
package home;
public class SpiralMatrix {
int arr[][] = null;
int c = 1;
int n = 0;
int[][] createSpriralMatrix(int n) {
this.n = n;
arr = new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
arr[i][j] = 0;
moveRight(0,0);
return null;
}
void moveRight(int i, int j) {
if (arr[i][j] != 0)
return;
for (; j < n; j++)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveDown(i + 1, j - 1);
}
void moveDown(int i, int j) {
if (arr[i][j] != 0)
return;
for (; i < n; i++)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveLeft(i - 1, j - 1);
}
void moveLeft(int i, int j) {
if (arr[i][j] != 0)
return;
for (; j >= 0; j--)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveUp(i - 1, j + 1);
}
void moveUp(int i, int j) {
if (arr[i][j] != 0)
return;
for (; i >= 0; i--)
if (arr[i][j] == 0) arr[i][j] = c++;
else break;
moveRight(i + 1, j + 1);
}
public static void main(String args[]){
int n=2;
SpiralMatrix spiralMatrix = new SpiralMatrix();
spiralMatrix.createSpriralMatrix(n);
int arr[][] = spiralMatrix.arr;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
System.out.print(" "+arr[i][j]);
System.out.println("\n");
}
}
}
But stack will grow :)
#include<stdio.h>
- nee.agl June 09, 2011int main()
{
int n;
scanf("%d", &n);
int a[n][n];
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j] = -1;
}
}
int k;
i=0;j=0;
int dir=0;
for(k=1;k<=(n*n);k++)
{
a[i][j] = k;
if(dir==0 && (n==(j+1) || a[i][j+1] != -1 ))
{
dir=1;
i++;
}
else if(dir==1 && ( (i+1)==n || a[i+1][j] != -1 ) )
{
dir = 2;
j--;
}
else if(dir==2 && (j==0 || a[i][j-1] != -1) )
{
dir =3;
i--;
}
else if(dir==3 && (a[i-1][j] != -1) )
{
dir =0;
j++;
}
else if(dir==0)
j++;
else if(dir==1)
i++;
else if(dir==2)
j--;
else if(dir==3)
i--;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%3d ", a[i][j]);
printf("\n");
}
return 0;
}