Microsoft Interview Question for SDE1s


Team: Azure
Country: United States
Interview Type: In-Person




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

Left to Right.
Move variable i from rowStart till columnLength. (Print data from first row till last column.)

Top to Bottom.
Move variable i from (rowStart+1) till rowLength. (Print data in last column till)
We need to start from (rowStart+1) because, we already printed corner element in Left to Right printing and no need to include it again. Same treatment for corner elements in other directions.

Right to Left.
Move variable i from columnLength-1 till columnStart. (Print data in last row)

Bottom to Up.
Move variable i from rowLength-1 till rowStart. (Print data in first column)

After printing all 4 directions, In next iteration,
we need to start from second row and second column, so increment
(rowStart ++) and (columnStart++).
we need to print till second Last column and till second Last row, so decrement
(columnLength --) and (rowLength --).

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	    vector<int> result;
		
		int rowStart = 0, rowLength = matrix.size() - 1, columnStart = 0, columnLength = matrix[0].size() - 1;
		while(rowStart<=rowLength && columnStart<=columnLength) {
		    //Right Sweeping 
		    for(int i=columnStart;i<=columnLength;i++) {
		        result.push_back(matrix[rowStart][i]);
		    }
		    //Downward Sweeping
		    for(int i = rowStart + 1; i <= rowLength; i++) {
		        result.push_back(matrix[i][columnLength]);
		    }
		    //Left Sweeping
		    if(rowStart != rowLength)
		    for(int i = columnLength - 1; i >= columnStart; i--) {
		        result.push_back(matrix[rowLength][i]);
		    }
		    //Upward Sweeping
		    if(columnStart != columnLength)
		    for(int i = rowLength - 1; i > rowStart; i--) {
		        result.push_back(matrix[i][columnStart]);
		    }
		    rowStart++;rowLength--;
		    columnStart++;columnLength--;
		}
		return result;  
    }

- R@M3$H.N January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A pure functional programming solution in Scala:

type Matrix[T] = Array[Array[T]]

def spiralElements[T](matrix: Matrix[T]): Seq[T] = {

    val (n, m) = size(matrix)

    def spiral(depth: Int, acc: Seq[T]): Seq[T] =

      if(depth >= n/2 || depth >= m/2) acc else {

        val left2right = (depth until (m-depth))
        val right2left = left2right.reverse.tail

        val top2bottom = ((depth+1) until (n-depth))
        val bottom2up = top2bottom.reverse.tail

        val crust = left2right.map(matrix(depth)(_)) ++
                      top2bottom.map(matrix(_)(m-1-depth)) ++
                        right2left.map(matrix(n-1-depth)(_)) ++
                          bottom2up.map(matrix(_)(depth))

        spiral(depth+1, crust.reverse ++ acc)

      }

      spiral(0, Seq.empty)

    }

- contact@pablofranciscoperez.info January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the spiral starts on the outside and goes towards the center, starts from the top-left and forms clockwise.

public class SpiralMatrix {
    private final int RIGHT = 0;
    private final int DOWN  = 1;
    private final int LEFT  = 2;
    private final int UP    = 3;

    private int[][] m;
    private int currCol = 0, currRow = 0;
    private int rowLower, rowUpper;
    private int colLower, colUpper;
    private int direction = RIGHT;

    public SpiralMatrix(int[][] m) {
        this.m = m;
        rowLower = 0;
        colLower = 0;
        rowUpper = m.length-1;
        colUpper = m[0].length-1;
    }

    private boolean advance() {
        switch (direction) {
            case 0:
                currCol += 1;
                if (currCol > colUpper) {
                    currCol -= 1;
                    rowLower += 1;
                    return false;
                }
                break;
            case 1:
                currRow += 1;
                if (currRow > rowUpper) {
                    currRow -=1;
                    colUpper -= 1;
                    return false;
                }
                break;
            case 2:
                currCol -= 1;
                if (currCol < colLower) {
                    currCol += 1;
                    rowUpper -= 1;
                    return false;
                }
                break;
            case 3:
                currRow -= 1;
                if (currRow < rowLower) {
                    currRow += 1;
                    colLower += 1;
                    return false;
                }
        }
        return true;
    }

    public void printSpiral() {
        int rowLower = 0;
        int colLower = 0;
        int rowUpper = m.length-1;
        int colUpper = m[0].length-1;

        while(true) {
            System.out.print(m[currRow][currCol]+" ");

            if (!advance()) {
                direction = (direction + 1) % 4;
                if (!advance())
                    break;
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] m1 = new int[][] { {1} };
        int[][] m2 = new int[][] { {1,2,3} };
        int[][] m3 = new int[][] { {1,2,3,4}, {5,6,7,8} };
        int[][] m4 = new int[][] { {1,2,3,4}, {5,6,7,8}, {9,10,11,12} };
        int[][] m5 = new int[][] { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} };

        SpiralMatrix sm1 = new SpiralMatrix(m1);
        SpiralMatrix sm2 = new SpiralMatrix(m2);
        SpiralMatrix sm3 = new SpiralMatrix(m3);
        SpiralMatrix sm4 = new SpiralMatrix(m4);
        SpiralMatrix sm5 = new SpiralMatrix(m5);
        sm1.printSpiral();
        sm2.printSpiral();
        sm3.printSpiral();
        sm4.printSpiral();
        sm5.printSpiral();
    }
}

- j January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- test January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution rests on calculating the required distance of the next move given a direction and the current position (i,j) in the matrix.

var rightWas = null
var downWas = null
function calculateNextDistance(direction, i, j, matrix) {
  var distance = 0
  switch (direction) {
  case 'right':
    // Label the columns of the matrix (1, 2, 3...n).
    // Starting from a `virtual` 0th column (at index -1),
    // when you go `right` you will always go row length of
    // the matrix - (2 * column #) elements
    var row_length = matrix[0].length
    distance = row_length - (2 * (j + 1))
    rightWas = distance
    break
  case 'left':
    // When you go left, you will always need to do
    // so a distance of -1 of the distance you went
    // right
    distance = rightWas - 1
    break
  case 'down':
    // Label the rows (0, 1, 2..n-1). When going `down`
    // you will always go column length of the matrix
    // - ((2 * row #) + 1) elements
    var column_length = matrix.length
    distance = column_length - ((2 * i) + 1)
    downWas = distance
    break
  case 'up':
    // The distance you need to go back up is
    // always -1 of the distance you went down.
    distance = downWas - 1
    break
  default:
    throw new Error('Unknown direction specified.')
  }
  return distance
}
module.exports = function (matrix) {
  var i = 0
  var j = -1
  var direction = ['right', 'down', 'left', 'up']
  var offset = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0]
  ]
  var k = 0

  var solution = ''
  
  if (!matrix.length || !matrix[0].length) {
    return solution
  }
  var d = calculateNextDistance(direction[k], i, j, matrix)

  // While there is still remaining distance to go, keep going.
  while (d > 0) {
    for (var q = 0; q < d; ++q) {
      i += offset[k][0]
      j += offset[k][1]
      solution += matrix[i][j] + ' '
    }
    k++
    if (k >= direction.length) {
      k = 0
    }
    d = calculateNextDistance(direction[k], i, j, matrix)
  }

  return solution
}
var matrixes = [[
    // NxN Matrix
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
  ], [
    // NxM Matrix (N < M)
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    [10, 11, 12]
  ], [
    // NxM Matrix (N > M)
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
  ], [
    // NxM Matrix (M = 1)
    [1, 2, 3, 4]
  ], [
    // NxM Matrix (N = 1)
    [1],
    [2],
    [3],
    [4]
  ], [
    // Empty Matrix
  ]
]
for (var m = 0; m < matrixes.length; ++m) {
  var solution = module.exports(matrixes[m])
  console.log(['CASE #', m + 1, ': ', solution].join(''))
}

$ node spiral.js 
CASE #1: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
CASE #2: 1 2 3 6 9 12 11 10 7 4 5 8 
CASE #3: 1 2 3 4 8 12 11 10 9 5 6 7 
CASE #4: 1 2 3 4 
CASE #5: 1 2 3 4 
CASE #6:

- srterpe January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basic structure is this :

def spiral( m ){
  bound = size(m) ; times = bound
  row = 0 ; col = 0
  while ( bound > 0 ){
    while ( times != 0 ){ printf(' %d ', m[row][col]) ; col += 1 ;  times -= 1 }
    bound -= 1 ; times = bound  ; col -= 1 ; row += 1  
    while ( times != 0 ){ printf(' %d ', m[row][col]) ; row += 1 ; times -= 1 }
    times = bound ; col -= 1 ; row -= 1 
    while ( times != 0 ) { printf(' %d ', m[row][col]) ; col-= 1 ;  times -= 1 }
    bound -= 1 ;  times = bound ; row = times ; col += 1  
    while ( times != 0 ) { printf(' %d ', m[row][col]) ; row-= 1 ;  times -= 1 }
    col += 1 ; row += 1 ; times = bound 
  } 
  println()
}

- NoOne January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heres the java implementation of the spiral matrix print.

//package com.learning.java;

/**
 * Created by ejangpa on 1/13/2017.
 */
public class PrintArraySpirally {
    public static void main(String[] args) {
       int n = 4;
        int m = 4;
        int[][] number = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };
        System.out.println("Initial Array");
        printArray(number);
        System.out.println("Spiral Array");
        printSpirallyMyCodeSchool(number, n, m);
    }


    /**
     * printSpirally prints array in spiral manner
     * @param number
     */
    static void  printSpirallyMyCodeSchool(int[][] number, int n, int m) {
        int T = 0;
        int R = n - 1;
        int B = m - 1;
        int L = 0;
        int dir = 0;
        while (L <= R && T <= B) {
            if(dir == 0) {
                for (int k = L; k <= R; k++) {
                    System.out.println(number[T][k]);
                }
                T++;
            } else if (dir == 1) {
                for(int k = T; k <= B; k++) {
                    System.out.println(number[k][R]);
                }
                R--;
            } else if (dir == 2) {
                for (int k = R; k >= L; k--) {
                    System.out.println(number[B][k]);
                }
                B--;
            } else if (dir == 3) {
                for (int k = B; k >= T; k--) {
                    System.out.println(number[k][L]);
                }
                L++;
            }
            dir = (dir + 1) % 4;
        }
    }

    /**
     * printArray() prints array Elements
     */
    static  void printArray(int[][] number) {
        for (int i = 0; i < number.length; i++) {
            for(int j = 0; j < number.length; j++) {
                System.out.print(number[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

- Jabongg January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* print elements of an matrix in spiral form*/
public class SpiralMatrix {
	
	private void print(int[][] matrix){
		for (int i = 0; i<matrix.length; i++ ){
			for(int j=0; j<matrix[i].length; j++){
				System.out.println( matrix[i][j]);
			}
		}
	}
	
	
	private void printSpiral(int[][] matrix){
		boolean oddLine = true;
		for (int i = 0; i<matrix.length; i++ ){
			if(oddLine){
				for(int j=0; j<matrix[i].length; j++){
					System.out.println( matrix[i][j]);
				}
			}
			else {
				for(int j=matrix[i].length-1; j>=0; j--){
					System.out.println( matrix[i][j]);
				}
			}
			oddLine = !oddLine;
		}
		
	}
	
	public static void main(String args[]){
		int[][] matrix = new int[][]{{1, 2,3},{4, 5, 6},{7,8,9}};
		SpiralMatrix sprialMatrix = new SpiralMatrix();
		sprialMatrix.printSpiral(matrix);
	}
}

- Mritunjay Kumar January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* print elements of an matrix in spiral form*/
public class SpiralMatrix {
	
	private void print(int[][] matrix){
		for (int i = 0; i<matrix.length; i++ ){
			for(int j=0; j<matrix[i].length; j++){
				System.out.println( matrix[i][j]);
			}
		}
	}
	
	
	private void printSpiral(int[][] matrix){
		boolean oddLine = true;
		for (int i = 0; i<matrix.length; i++ ){
			if(oddLine){
				for(int j=0; j<matrix[i].length; j++){
					System.out.println( matrix[i][j]);
				}
			}
			else {
				for(int j=matrix[i].length-1; j>=0; j--){
					System.out.println( matrix[i][j]);
				}
			}
			oddLine = !oddLine;
		}
		
	}
	
	public static void main(String args[]){
		int[][] matrix = new int[][]{{1, 2,3},{4, 5, 6},{7,8,9}};
		SpiralMatrix sprialMatrix = new SpiralMatrix();
		sprialMatrix.printSpiral(matrix);
	}
}

- Mritunjay Kumar January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I print just the board of the matrix, like a square, for each deepth.

public static void spiralMatrix(int[][] a){
        printAround(0,0, a.length-1, a[0].length-1, a);
    }

    private static void printAround(int rowIni, int colIni, int rowEnd, int colEnd, int[][] a) {
       if(rowIni > rowEnd || colIni > colEnd) return;
       
       for(int i =colIni; i<colEnd+1; i++){
           System.out.println(a[rowIni][i]);
       }
       for(int i =rowIni+1; i<rowEnd+1; i++){
           System.out.println(a[i][colEnd]);
       }
       for(int i =colEnd-1; i>=colIni; i--){
           System.out.println(a[rowEnd][i]);
       }
       for(int i =rowEnd-1; i>=rowIni+1; i--){
           System.out.println(a[i][colIni]);
       }
       printAround(rowIni+1,colIni+1,rowEnd-1,colEnd-1,a);

}

- William Barbosa January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def print_spiral(grid):
    r_start = 0
    r_end = len(grid) - 1
    c_start = 0
    c_end = len(grid[0]) - 1
    
    while r_start <= r_end  and c_start <= c_end:
        for c in xrange(c_start, c_end + 1):
            print grid[r_start][c],
        r_start += 1
        if r_start > r_end: break
        
        for r in xrange(r_start, r_end + 1):
            print grid[r][c_end],
        c_end -= 1
        if c_start > c_end: break
        
        for c in xrange(c_end, c_start -1, -1):
            print grid[r_end][c],
        r_end -= 1
        if r_start > r_end: break
        
        for r in xrange(r_end, r_start - 1, -1):
            print grid[r][c_start],
        c_start += 1
        if c_start > c_end: break

- Nitish Garg January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def spiral(N):

L = [k for k in range(1,N**2+1)]

max_l = len(str(N**2))

g = [[None]*N for k in range(N)]

p = [N-1,1]

D = {(-1,0):(0,1),(0,1):(1,0),(1,0):(0,-1),(0,-1):(-1,0)}

step = lambda p,delta: [p[0] + delta[0],p[1] + delta[1]]

delta = (0,-1)

for n in L:

n_step = step(p,delta)

if max(n_step) == N or min(n_step) < 0 or g[n_step[1]][n_step[0]] is not None:

delta = D[delta]

n_step = step(p,delta)

p = n_step

g[p[1]][p[0]] = n

for row in range(N):

out = ''

for n in g[N-1-row]:

ns = str(n)

if len(ns) < max_l:

length = max_l - len(ns)

ns = " "*int(length/2) + ns

ns += " "*(length - int(length/2))

out += ns + ' '

print(out)

- Anonymous February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<vector<int> > generateMatrix(int A) 
{

   vector<vector<int>> ans(A,vector<int>(A));
    
    
    int dir = 0;
    int up = 0;
    int down = A;
    int left = 0;
    int right = A;
    int paint = 1;
    int end = A*A;
    while ( paint <= end )
    {
        if ( dir == 0 )//left to right
        {
            
            for ( int i = left; i < right; i++ )
            {
                ans[up][i] = paint++;
            }
            dir = 1;
            print(ans);
            continue;
        }
        
        if ( dir == 1 )//top to down
        {
            
            for ( int i = up+1; i < down; i++ )
            {
                ans[i][right-1] = paint++;
            }
            dir = 2;
            print(ans);
            continue;
        }

        if ( dir == 2 )//right to left
        {
            
            for ( int i = right-2; i > left-1; i-- )
            {
                ans[down-1][i] = paint++;
            }
            dir = 3;
            print(ans);
            continue;
        }
         print(ans);
        if ( dir == 3 )//bottom up
        {
            
            for ( int i = down-2; i > up; i-- )
            {
                ans[i][left] = paint++;
            }
            up++;
            left++;
            right--;
            down--;
            dir = 0;
        }
         print(ans);
    }
    return ans;
}

- drolmal April 07, 2017 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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