March 16, 2016
Problem statement
Given a 2D array
(matrix) named M, print all
items of M in a spiral
order, clockwise.
For example:
M = 1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
The clockwise spiral print is: 1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12
Mock interview practice
I had a mock interview recently and my algorithm is Spiral matrix. The code I wrote in mock interview using C# is here.
Let us take a look at evaluation from the mock interviewer, as a matter of fact the peer gave me the honest feedback, I have to figure out how to work on the improvement:
Code review
After the mock interview, I thought about more how to improve the
solution. I do not have good idea to solve the problem. Based on my mathematics background and I tried to define how many variables in the problem.
Let us look at one variable, let us call it layer, using variable name row, value is from 0 to (N+1) / 2, where N is how many
columns in the matrix. So, the spiral matrix output is to follow the order of clockwise starting from (0,0).
N - how many
columns
M - how many
rows
Four corners are left-top, right-top, bottom-right, bottom-left, abbreviation using four variables: LT, RT, BR, BL
LT coordinates: ( row, row )
RT coordinates: ( row, N - 1 - row)
BR coordinates: ( M - 1 - row, N -1 - row)
BL coordinates: ( M - 1 - row, row)
private static void leftToRight(Coordinate[] A)
TopToDown,
RightToLeft, and DownToUp
row
0 1
2
-------------->
1
2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17
18 19 20
The above case, LT = (0, 0), RT =
(0, 4), BR = (3, 4), BL = (3, 0)
C# practice code based on the above idea is here.
Continue to improve the idea.
LT, BR those two pointers should be checked on the conditions, M – 1 - row >= row, N – 1 - row >= row; in other words, left top pointer is above the bottom right pointer, therefore it should be row <= Math.Min((M - 1)/ 2, (N - 1)/ 2).
It is true that the idea I came out just after the mock interview was not so good. But the hard work spirit is good, and also it is very good to write down the idea and review later on.
Issues found in mock interview
I like to write down a few issues in
my practice.
1. Jagged array initialization
Julia spent more than 5 minutes to
look up the internet.
2. Try another idea. Use one variable instead of two variables.
Assuming that N rows and M columns,
how many layers of spiral? Use the variable i to denote the number.
It should be from 0 to (N+1)/2, but it is hard to figure out correct answer first time, it should be 0 to Math.Min((M-1)/2, (N-1)/2).
Julia spent more than 20 minutes to debug in the practice.
Spiral matrix practice in 2015
I practice once in 2015 on Leetcode 54 Spiral matrix algorithm. I found the blog and it is very interesting to read the code I wrote back in 2015 June. Here is the blog about the practice.
Follow up
May 23, 2017
It is such great experience to compare the current practice to the one in 2016. Julia learned that she made such great improvement on coding readability, and she starts to know how important it is to document and track the progress.
After considering a few of options, it is much easy to write a while loop to track the total visited nodes in the original array.
Instead of using i, j, use variable row and col because it is more meaningful.
Do not run the code and depend on the compiler;
Test the code by yourself.
C# practice is here.
In order to make sure that the code is working, Julia used the same idea to write a solution for Leetcode 54. The solution failed to pass one row test case [1, 2, 3].
The C# code is fixed to add one row and one column checking. The code is here.
