HackerRank NCR code sprint: Spiral Message

March 23, 2018

Introduction

I spent more than 30 minutes to review my own question on stackexchange.com, and I like to post an answer after 15 months. Here is the question I asked in January 2017.

Code review

I wrote the code again, here is the C# code. I will write an answer in short future.

1. change variable names to make it more meaningful.
 startX is changed to rowStart,
 startY is changed to colStart,
 endX   is changed to rowEnd,
 endY   is changed to colEnd.

2. Remove code related to check base cases like one node, one row, one column, set direction variables.

3. Add base case one node and one column break statement just after the first leftmost column.
4. Add base case one row break statement just after the second top row.

My last 3 month practice

The matrix spiral print is my most favorite algorithm, first in January I was interviewed and got low performance 1/ 4 problem solving rating. After that I tried to practice more than 10 ideas using Leetcode 54 discussion panel, I asked the question on stackexchange.com, and then i used the algorithm to interview more than 13 interviewees on mock interview platform. If I do learn something, I must learn from this algorithm.

Here are the links to look up. I still get organized by adding/ modifying the labels on blog platform.

Search by keyword: spiral matrix print, here is the link. Search using keyword: Leetcode 54: Spiral matrix, link is here.

Spiral matrix print algorithm

March 8, 2018

Introduction

It is my most favorite algorithm in 2018. I learn so many lessons from the algorithm, and I can count so many hours I have spent on the algorithm. My most favorite experience is documented here, one thing I did not tell that the first mock interviewer on anonymous platform in 2018 failed me on this algorithm and marked me as poor as the technical skills. I did not write fully functioning code following the idea using direction array and automate the direction change.

One more interview

I chose the algorithm to interview the peer on March 7, 2018 10:00 PM. The peer spent near 45 minutes to complete the algorithm.

Here is C# code I reviewed.

Even though I have worked on the algorithm so many hours, I did not perform very well as an interviewer yesterday. I preferred one while loop instead of three loops with while/for/while, I confused and made wrong judgement to say that for loop will have dead loop, actually the for loop direction array only has size of 4.

Actionable Items

I like to replay the mock interview I did on January 23, 2018 to work on spiral matrix print algorithm. After 30 days of mock interview, I like to compare myself with all my 13 interviewee to work on the same algorithm.

What should I work on to perform better through mock interview?

Leetcode 54: Spiral matrix

Feb. 12, 2018

Plan to study Leetcode 54: Spiral matrix python solution. Here is the link.

Leetcode 54: Spiral Matrix

Feb. 8, 2018

Introduction

One more solution is here based on using two variable to switch direction clockwise. I read the idea from Leetcode 54 discussion, and then tried to write one using C# language.

One of ideas is to go over as many Leetcode discussion as possible, and then I will vote the idea I like and actively share my feedback. Because I like to use this algorithm for my mock interview as an interviewer, I like to do as many research as possible.

Please write at least ten ideas using C#. Be well prepared and learn one algorithm very well. I can  use the algorithm to tell who is real talented programmer in the world.

Using two direction variables

Here is C# code.

Leetcode 54: Spiral matrix

Feb. 2 2018

Introduction

It is the second time I asked leetcode 54: spiral matrix in the anonymous interview as an interviewer. I met a peer who was willing to be interviewed, and followed my hint and try to write a solution using one loop instead of four for loops for each direction.

Code review

Here is Java code to review. The peer spent around 20 minutes to work on coding, I was able to see how good the peer can write readable code.

I told the peer that he did better than me. When I was asked this algorithm and the idea to write one loop only, it took me more time to come out the ideas, and I needed two hints, one for direction array, one for visited array.

Compared to the peer, I knew that I have to learn to stay open and think hard in the mock interview.

Leetcode 54: Spiral matrix

January 30, 2018

Introduction

It is such a big surprise that my first mock interview as an interviewer turns out big success. The peer solved all four algorithms I asked in first 40 minutes. He is the best peer I have met in my peers, over 150 peers.

Best thing is that I got education how to design a perfect system design: Instagram scalability in 30 minutes. I could not believe that I may interview a top company senior developer in the future.

Code review

Here is the C# code I like to learn. The idea is very clear and it is the production ready code.

Leetcode 54: Spiral Matrix

January 28, 2018

Introduction

It is the algorithm I have to write on my 10:00 PM mock interview. I worked on the spiral matrix, and it took me in total 20 minutes to explain the solution and write the solution to pass all test cases.

Code review

The peer told me that I can save the space using four pointers instead of visited array. I explained to him that the mock interview is for me to write the correct solution using minimum time.

Here is the C# code I wrote.

Leetcode 54: Spiral Matrix

January 24, 2018

Introduction

It is the algorithm I have practiced over 6 times in mock interview and also interviewed other 6 peers from March 2017 to January 2018. On January 23, 3018 10:00 pm, I had my first mock interview on interviewing.io platform, and then I had to work on the algorithm. What I learned through the mock interview is to get rid of those 4 for loop inside a while loop. In other words, the interviewer told me that in order to perform a 20 minutes coding interview, I have to write only one loop, and adjust the direction accordingly.

Mock interview 

Here are the hints the interviewer gave to me:

1. After 20 minutes, he wrote down four directions in two one dimension array.
dr = new int[]{0, 1, 0, -1}
dc = new int[]{1, 0, -1, 0}

2. After another 10 minutes, he gave second hint to use visited array [][] to mark the visited node.
3. After that, he gave me another hint, how to write a checking for direction change.

if(row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] == 1)
{
      // change direction
}

Here is the transcript I copied from video clip at 50:00 of 51:00.

After the mock interview 

This the first time I used interviewing.io to practice mock interview. It turns out that the interviewer is much strong in technical skills and also interview skills. I have played the interview recording twice, and here are something I have to work on.

1. Do not interrupt the interviewer.
2. Say something like "Let me think about two minutes.". Actually calm down and think carefully in two minutes.
3. Stay calm and speak slowly.
4. Take hint and write down the hint quickly, and really think about hint. Follow the hint.
5. It is too slow to take the hint, and work out a solution based on the hint.
6. I should work on the example and write fully functional C# code in mock interview.
7. Check the time I spend and act fast.

Define the keywords for the problem, write down in mock interview. So it is very easy to discuss with the peer for various ideas. Seek and you will find, brainstorm the ideas related to time complexity, space complexity.

Direction - There are four direction. Change direction if need, in the order of clockwise, starting from top left corner (0,0).
Range - Stay inside the array
Visit - visit each element in the array only once. Do not visit more than once.
Order - follow the order of clockwise, start from (0,0).

Ideas can be searched through those keywords. Let us go over one keyword together.

For example, direction can be managed smartly using array for four direction, or manually specified. Every edge in one direction can be specified by start point and end point two variables, but it also can be implicitly specified using visited array. Just relax and talk to the peer in mock interview, and go over each possible options. Evaluate pros and cons, have a conversation.

Follow up 

Here is the C# code I wrote after the mock interview. I really like the idea and the solution is so easy to write, I write on purpose to add fourDirections in order to make the code more readable.

I am planning to post a code review on the stackexchange.com as well. The link is here.

Feeback is gold

It takes a village to raise a child. 

Interviewing.io is my new village. 

Matrix spiral print algorithm

January 6, 2018

Introduction

It is another 10:00 AM mock interview. The peer worked on the algorithm called the matrix spiral print algorithm. So surprisingly, I learned a new way to write the solution and also the code is much simple and easy to follow.

Code study

Here is C++ code to pass all test cases.

It is so interesting to read the blog I write back in March 2016, the first time I practiced the same algorithm on mock interview platform. At that time, I was so shy and the code I wrote was not so clean and readable. And I even read the code I wrote back to 2015.

Mock interview (4th practice): Matrix Spiral Print

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.