Wednesday, May 11, 2016

HackerRank – Connected Cell in a Grid - Warm up with Five Practices

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016.

First practice, it takes her close to 60 minutes to write, fix issues.  Use dimensional array, use queue to do BFS – breadth first search.


Here are mistakes:
      1. Forget to add boundary check function, do boundary check (source code: line 108)

      2. Forget to introduce neighbor_X, neighbor_Y  (source code: line 90, 91)

      3. Neighbor_X is mistakenly written as neighbor_Y, so wrong answer;
          Debug the code and find the issue. It takes more than 20 minutes, a lot of stress. (source code: line 96)

So, it is excellent chance to learn and improve the performance.

Write a small function to debug the code, figure out the wrong answer issue – testRoutine, source code: line 36.


Second practice, using queue, but use jagged array:  (20 minutes to write)

          

Third practice, use DFS – recursive function, which also returns the count.

         

Fourth practice, using DFS – recursive function, but use an argument – reference int to track value


Fifth practice, using stack instead of recursive function, implement the DFS algorithm:



Question and answer:

      1. What do you learn through the warm up? Do you learn some better ways to fix the bugs?
It is better to write down the functions needed to help the task, this way, you will be more efficient.

Here are 4 tasks:
     1. Calculate the key
     2. Boundary check 
     3. Maximum value search
     4. Using queue to do search

     2.  Why do you do warm up this time? What are the advantages?

Julia still remembers the favorite tip to work on the tasks:
1.    Just mark the visited node as 0 from value 1
2.    Update node value from 1 to 0 before it is added to the queue
3.    Use key = row * 10 + col, since row < 10, col < 10 to track each node in the queue

Julia likes to write code and do some warm up, therefore, she can get more experience; she tries to improve performance to 20 minutes for this kind of DFS, BFS, matrix, search algorithm.

3. Do you reproduce the experience of high stress to trouble shooting and work on bug fix? 

Julia reproduced the issue of high stress, she could not fix the bug on her first practice. So, she wrote a small debug function try to figure out; actually, it is a mistake in writing. 

Next time, reexamine every line of code, every variable, every executable path, when the code is executed. Do not depend on debugging, running the code, because stress level is high. 

No comments:

Post a Comment