Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
#include<iostream.h>
#include<conio.h>
int matrix[8][8]=
{
{4,6,3,5,5,5},
{4,2,5,7,6,3},
{5,3,7,5,3,9},
{5,2,8,5,9,2},
{2,6,3,8,1,4},
{5,2,8,3,2,5}
};
//------- i=0 .....1,m-1 2,m-1 3,m 4,m-----------2,m-2 3,m-2
void spiral(int matrix[][8],int n,int m)
{ int i,j=0,x;
if(n%2==0) x=n/2;
else x=n/2+1;
for(i=0;i<x;i++)
{
cout<<"\nround 1-->";
for(j=i;j<m-i;j++)
cout<<matrix[i][j]<<" ";
cout<<"\nround 2-->";
for(j=i+1;j<n-i;j++)
cout<<matrix[j][(m-1)-i]<<" ";
cout<<"\nround 3-->";
for(j=m-i-2;j>=i;j--)
cout<<matrix[n-i-1][j]<<" ";
cout<<"\nround 4-->";
for(j=n-i-2;j>i;j--)
cout<<matrix[j][i]<<" ";
cout<<endl;
}
}//
void printMatrix(int matrix[][8],int n,int m)
{
for(int register i=0;i<n;i++)
{
for(int register j=0;j<m;j++)cout<<matrix[i][j]<<" ";
cout<<endl;}
}
int main()
{ int i=0;
clrscr();
cout<<endl<<"start "<<endl;
for(i=2;i<7;i++)
{
cout<<endl<<"matrix printing start "<<endl;
printMatrix(matrix,i,i); cout<<endl<<"outputt";
spiral(matrix,i,i);
getch();
clrscr();
}
getch();
return 0;
}
Comment from OP
void spiraltraversal( int (*a)[], int r, int c, int startr = 0, int startc = 0 )
{
if( r == 1 && c== 1 )
print(a[sr][sc])
return;
for( i = sc; i <= sc+c-1; i++ )
print(a[sr][i]);
for( i = sr; i <= sr+r-1; i++ )
print(a[i][sc+c-1]);
if( r != 1 )
for( i = sc+c-1; i >= sc; i-- )
print(a[sr+r-1][i]);
if( c != 1 )
for( i = sr+r-1; i >= sr+1; i-- )
print(a[i][sc]);
if( r-2 <= 0 || c-2 <= 0 )
return;
else
spiraltraversal( a, r-2, c-2, startr+1, startc+1 );
return;
}
struct Point {
int x;
int y;
};
void spOnce(char **a, Point p0, Point p1) {
if(p0.x==p1.x) {
if(p0.y<=p1.y) {
for(int i=p0.y; i<=p1.y; i++) {
cout<<a[p0.x][i];
}
} else {
for(int i=p0.y; i>=p1.y; i--) {
cout<<a[p0.x][i];
}
}
} else {
if(p0.x<=p1.x) {
for(int i=p0.x; i<=p1.x; i++) {
cout<<a[i][p0.y];
}
} else {
for(int i=p0.x; i>=p1.x; i--) {
cout<<a[i][p0.y];
}
}
}
}
void spiralTrav(char **a, int m, int n) {
Point pt[4];
pt[0].x=0; pt[0].y=0;
pt[1].x=0; pt[1].y=n-1;
pt[2].x=m-1; pt[2].y=n-1;
pt[3].x=m-1; pt[3].y=0;
int pos=0;
while (pt[0].x<=pt[3].x) {
spOnce(a, pt[pos], pt[(pos+1)%4]);
switch(pos) {
case 0:
pt[0].x++; pt[1].x++;
break;
case 1:
pt[1].y--; pt[2].y--;
break;
case 2:
pt[2].x--; pt[3].x--;
break;
case 3:
pt[3].y++; pt[0].y++;
break;
default:
break;
}
pos=(pos+1)%4;
}
}
int a[4][4] = { {12, 23, 15, 17}, {34, 22, 176, 23}, {345, 62, 11, 19}, {18, 223, 112, 152}};
int l=0, k=0, N = 4, M = 4;
bool ltr = true;
while (l < N && k < M)
{
std::cout << a[k][l] << " ";
if(l == N-1 && ltr)
{
ltr = false; ++k;
std::cout << std::endl;
}
else if(l == 0 && !ltr)
{
ltr = true; ++k;
std::cout << std::endl;
}
else
{
if(ltr)
++l;
else
--l;
}
}
- ashot madatyan March 09, 2012