Microsoft Interview Question
SDE1sTeam: Azure
Country: United States
Interview Type: In-Person
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)
}
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();
}
}
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:
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()
}
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();
}
}
}
/* 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);
}
}
/* 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);
}
}
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);
}
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
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)
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;
}
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 --).
- R@M3$H.N January 13, 2017