Microsoft Interview Question Software Engineer / Developers




Comment hidden because of low score. Click to expand.
1
of 1 vote

void PrintSpiral(int **a, int rowsStart, int rowsEnd, int colsStart, int colsEnd)
{
	if(rowsStart > rowsEnd && colsStart>colsEnd)
		return;

	// Print top row
	for(int i = colsStart ; i<=colsEnd; i++)
		cout<<a[rowsStart][i]<<" ";

	// If row start == row end then all the element got print in the previous loop 
	// no need to print any column so putting the breaking condition for columns
	if(rowsStart == rowsEnd)
		colsStart = colsEnd+1;

	// Top row is done so remove the top row
	rowsStart++;

	// Print right rows
	for(int i = rowsStart ; i<=rowsEnd; i++)
		cout<<a[i][colsEnd]<<" ";

	// If col start == col end then all the element got print in the previous loop 
	// no need to print any rows so putting the breaking condition for rows
	if(colsStart == colsEnd)
		rowsStart = rowsEnd+1;

	// Right most column is done so removing it
	colsEnd--;

	// Print Bottom row
	for(int i = colsEnd ; i>=colsStart; i--)
		cout<<a[rowsEnd][i]<<" ";

	// If row start == row end then all the element got print in the previous loop 
	// no need to print any column so putting the breaking condition for columns
	if(rowsStart == rowsEnd)
		colsStart = colsEnd+1;

	// Bottom row is done so removing it
	rowsEnd--;
	// Print Left Row
	for(int i = rowsEnd ; i>=rowsStart; i--)
		cout<<a[i][colsStart]<<" ";

	// If col start == col end then all the element got print in the previous loop 
	// no need to print any rows so putting the breaking condition for rows
	if(colsStart == colsEnd)
		rowsStart = rowsEnd+1;

	// left most column is done so removing it
	colsStart++;
	PrintSpiral(a, rowsStart, rowsEnd, colsStart, colsEnd);
}

- Paras on February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for bad formatting.
The idea is.
1. Print the top row and then increment the rowStart by one.
2. Then Print the right most column and decrement the colsEnd by one.
3. Print the bottom row and decrement the rowsEnd by one
4. Print the left most column and increment the colsStart by 1.
5. Do this recursively.

I hv put extra check to for this algo to support rectangular matrix

Any feedback is welcome.

Thanks

- Paras on February 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[3][3] = {
					{1,2,3},
					{4,5,6},
					{7,8,9}
				};
	int m=3, n=3;
	for(int i=0; i<m; i++)
	{
		if(i%2)
			for(int j=n-1; j>=0; j--)
				cout << a[i][j] << " ";
		else
			for(int j=0; j<n; j++)
				cout << a[i][j] << " ";
		cout << endl;
	}

- Anonymous on February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the right answer

- Anonymous on March 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It will print in zig-zag manner.

A spiral is a curve which emanates from a central point, getting progressively farther away as it revolves around the point.

- sandygupta on February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What does 2d spiral mean?

- Anonymous on February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Spiral output for the sample in teh pgm
will be like
1 2 3 6 9 8 7 4 5

- Anonymous on February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Array not be square, can be rectangular as well.

- Anil on February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't matter whether square OR not :

{12345}
{56789}
{!@#$%}

123459%$#@!5678

- PKT on February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it shud b like this:

11 
         10   12
       9   3    13  
      8  2   4   14
       7  1  5  15
          6    16
            17

- lasttroll on February 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my output for a sample run:

ARRAY: 

  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  26  27  28  29  30  31  32 
 33  34  35  36  37  38  39  40 
 41  42  43  44  45  46  47  48 
 49  50  51  52  53  54  55  56 
 57  58  59  60  61  62  63  64 
 65  66  67  68  69  70  71  72 
 73  74  75  76  77  78  79  80 

SPIRAL: 

                      57
                   56      58
                55      31      59
             54      30      32      60
          53      29      13      33      61
       52      28      12      14      34      62
    51      27      11      03      15      35      63
  50      26      10      02      04      16      36      64
    49      25      09      01      05      17      37      65
  80      48      24      08      06      18      38      66
    79      47      23      07      19      39      67
       78      46      22      20      40      68
          77      45      21      41      69
             76      44      42      70
                75      43      71
                   74      72
                      73

And for the interested, the code (It's messy):

// SpiralArray.c
// (c) souravgh@usc.edu
// Sun Feb 27 1130
// Prints a 2D array spirally.
#include <cstdlib>
#include <cstdio>

using namespace std;

#define RowsInt 10
#define ColsInt 8

typedef struct {
  int xPosInt;
  int yPosInt;
  int noInt;
} Point;

#define ExchangePoints(p1, p2) {\
  Point tempPoint = p1;\
  p1 = p2;	       \
  p2 = tempPoint;      \
  }

enum Direction {LeftUp, RightUp, RightDown, LeftDown};

void updateXY (int *xIntPtr, int *yIntPtr, Direction direction) {
  int xDxInt = (direction == LeftUp || direction == LeftDown) ? -1 : 1;
  int yDyInt = (direction == LeftUp || direction == RightUp) ? -1 : 1;

  *xIntPtr += xDxInt;
  *yIntPtr += yDyInt;
}

void calculateSpiralCoords (Point *pointPtr, int sizeInt) {
  int lastXInt = 0, lastYInt = 0, countInt = 1;
  Direction dirsPtr[4] = {LeftUp, RightUp, RightDown, LeftDown};
  int currentDirectionInt = 0;

  // Calculate the x,y positions of the points
  // as if we are about to plot a 2D polygon graph.
  for (int indexInt = 0; indexInt < sizeInt; ) {
    for (int updateCountInt = 0; updateCountInt < countInt && indexInt < sizeInt; updateCountInt++) {
      pointPtr[indexInt].xPosInt = lastXInt;
      pointPtr[indexInt].yPosInt = lastYInt;

      updateXY (&lastXInt, &lastYInt, dirsPtr[currentDirectionInt]);
      indexInt++;
    }

    currentDirectionInt = (currentDirectionInt + 1) % 4;
    if (currentDirectionInt % 2 == 0) {
      countInt++;
    }
  }

  // Do some base offset additions to all points.
  // This brings all coordinates into +ve values.
  // This could have been done in the same loop above,
  // but enough was already being done there!
  int minXInt = 0, minYInt = 0;

  // Find the minimum x and y positions.
  for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
    minXInt = (minXInt > pointPtr[indexInt].xPosInt) ? pointPtr[indexInt].xPosInt : minXInt;
    minYInt = (minYInt > pointPtr[indexInt].yPosInt) ? pointPtr[indexInt].yPosInt : minYInt;
  }

  // minXInt and minYInt are now 0 or -ve.
  // Offset all points.
  for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
    pointPtr[indexInt].xPosInt -= minXInt;
    pointPtr[indexInt].yPosInt -= minYInt;
  }
}

void sortPoints (Point *pointPtr, int sizeInt) {
  // Do a simple bubble sort to sort the points.
  for (int iIndexInt = 0; iIndexInt < sizeInt; iIndexInt++) {
    for (int jIndexInt = 0; jIndexInt < sizeInt - iIndexInt - 1; jIndexInt++) {
      if (pointPtr[jIndexInt].yPosInt > pointPtr[jIndexInt + 1].yPosInt || 
	  (pointPtr[jIndexInt].yPosInt == pointPtr[jIndexInt + 1].yPosInt && 
	  pointPtr[jIndexInt].xPosInt > pointPtr[jIndexInt + 1].xPosInt)) {
	ExchangePoints (pointPtr[jIndexInt], pointPtr[jIndexInt + 1]);
      }
    }
  }
}

void plotPoints (Point *pointPtr, int sizeInt ,FILE *outFilePtr) {
  // First we space out the points along the X axis.
  for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
    pointPtr[indexInt].xPosInt *= 3;
  }

  for (int indexInt = 0; indexInt < sizeInt; ) {
    int currYInt = pointPtr[indexInt].yPosInt;
    int currXOffset = pointPtr[indexInt].xPosInt;

    fprintf (outFilePtr, "%*s", currXOffset, " ");

    for (; currYInt == pointPtr[indexInt].yPosInt && indexInt < sizeInt; indexInt++) {
      fprintf (outFilePtr, "%*s%02d", pointPtr[indexInt].xPosInt - currXOffset, " ", pointPtr[indexInt].noInt);
      currXOffset = pointPtr[indexInt].xPosInt;
    }
    fprintf (outFilePtr, "\n");
  }
}

void printSpiral (int arrIntPtrPtr[RowsInt][ColsInt]) {
  Point pointPtr[RowsInt * ColsInt];

  fprintf (stdout, "\nARRAY: \n\n");
  for (int yIndexInt = 0; yIndexInt < RowsInt; yIndexInt++) {
    for (int xIndexInt = 0; xIndexInt < ColsInt; xIndexInt++) {
      pointPtr[yIndexInt * ColsInt + xIndexInt].noInt = arrIntPtrPtr[yIndexInt][xIndexInt];
      fprintf (stdout, "%3d ", arrIntPtrPtr[yIndexInt][xIndexInt]);
    }
    fprintf (stdout, "\n");
  }
  fprintf (stdout, "\nSPIRAL: \n\n");

  // Calculate the spiral 2D coordinates.
  calculateSpiralCoords (pointPtr, RowsInt * ColsInt);

  // Sort the points by Y and break ties for same Y using X.
  sortPoints (pointPtr, RowsInt * ColsInt);

  // Plot points to stdout
  plotPoints (pointPtr, RowsInt * ColsInt, stdout);
}

int main (void) {
  int arrIntPtrPtr[RowsInt][ColsInt];

  for (int yIndexInt = 0; yIndexInt < RowsInt; yIndexInt++) {
    for (int xIndexInt = 0; xIndexInt < ColsInt; xIndexInt++) {
      // Increasing ints.
      arrIntPtrPtr[yIndexInt][xIndexInt] = yIndexInt * ColsInt + xIndexInt + 1;
    }
  }

  printSpiral (arrIntPtrPtr);

  return EXIT_SUCCESS;
}

- souravghosh.btbg on February 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A tricky solution:
#include<stdio.h>

int main()
{
int a[3][3] = {1,2,3,4,5,6,7,8,9};

int i = 0;
int j = 0;
int inc = 1;
for(;i<3;++i)
{
for(;(j<3 && j>-1);)
{
printf("%d ", a[i][j]);
j += inc;
}
j -= inc;
inc = -inc;
}
}

- Rahul on March 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define ROW 5
#define COL 5

int arr[ROW][COL] = {
{1, 2, 3, 4, 9},
{12, 13, 14, 5, 2},
{11, 16, 15, 6, 23},
{10, 9, 8, 7, 56},
{34, 35, 36, 37, 78}
};

void printArrSpiral(int arr[][COL],int level,int row, int col)
{
int i = 0;
for(i = level; i < col-level; i++)
cout<<arr[level][i]<<" ";

for(i = level+1; i <= row-level-1; i++)
cout<<arr[i][col-level-1]<<" ";


if(row-level-1 > level)
{
for(i = col-level-2; i >= level; i--)
{
cout<<arr[row-level-1][i]<<" ";
}
}

if(col-level-1 > level)
{
for(i = row-level-2; i > level; i--)
cout<<arr[i][level]<<" ";
}

cout<<endl;
}

int main()
{
int row = ROW;
int col = COL;
int level = (row/2 <= col/2)?row/2:col/2;
for(int i = 0; i<= level; i++)
{
printArrSpiral(arr,i,ROW,COL);
}
return 0;
}

- Anonymous on March 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Also try this:

input: int[][] arr
output: print output
assumption: Array is not empty

void PrintArray(int[][] arr){
	int m = arr[0].Length;
	int n = arr.Length;
	for (int i=0;i<m;i++) print(arr[0][i]);
	int i = 1, step = n-i, x = m-1, y = 0;
	Direction dir = Direction.Down;
	while(step > 0){
		switch(dir){
			case Direction.Down:
				while(step -- > 0) print(arr[x][++y]);
				step = m-i; dir = Direction.Left;
				break;
			case Direction.Left:
				while(step -- > 0) print(arr[--x][y]);
				step = m-(++i); dir = Direction.Up;
				break;
			case Direction.Up:
				while(step -- > 0) print(arr[x][--y]);
				step = m-i; dir = Direction.Right;
				break;
			case Direction.Right:
				while(step -- > 0) print(arr[++x][y]);
				step = m-(++i); dir = Direction.Left;
				break;
		}
	}
}

enum Direction{
	Down,
	Left,
	Up,
	Right
}

- binrengoog on March 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey25465" class="run-this">public class Matrix
{
private int[][] matrix;

public Matrix(int[][] inputMatrix)
{
matrix = inputMatrix;
}

public void PrintSpirally()
{
for (int i = 0; i < matrix.Length; i++)
{
int startIndex = 0;
int endIndex = matrix[i].Length - 1;
int increment = 1;

//zig zag; even rows go from left to right. odd rows go from right to left
if (i % 2 == 1)
{
increment = -1;
int temp = startIndex;
startIndex = endIndex;
endIndex = temp;
}

while (startIndex != endIndex)
{
Console.Write(matrix[i][startIndex] + ",");
startIndex += increment;
}
Console.Write(matrix[i][startIndex]);

Console.WriteLine();
}
}
}</pre><pre title="CodeMonkey25465" input="yes">
</pre>

- Anonymous on November 20, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More