Code review: At least 2 paths down the binary tree have the same sum

Dec. 23, 2017

Introduction

It is my most favorite algorithm in the world in June 2016. I had to go through the transition to accept myself as a software programmer, and learn how to improve myself through this simple algorithm. I did the practice and then stopped without writing an optimal solution in June 2016. Now after more than 12 months, I know that at the time I do not have high standards on practice at all.

Here is the algorithm I practice in June 2016.

I reviewed the code on Dec. 23, 2017 and asked the question on code review website. Here is the code review web link.

June 2016

It is tough to deal with frustration, what I did is to write a blog to study the failure on June 5, 2016. I was so excited to go over one day meeting with the most highest standard software company. And then I experienced so many issues through meetings. One thing is that I did not perform very well on the similar algorithm using C# LINQ.

Add one more paragraph

One thing I like to do is to add one more paragraph on the code review. Since I do not get any upvote after 24 hours, so I like to step out and do something to help myself.

Here is the paragraph:

Code improvements

I decided to make a few improvements based on my last practice over 18 months ago. Internal class is used instead of external class. I choose to use camel case for public method, and rename the function DuplicateCheckingPathSum to make the function name self-documenting. Specially I took 10 - 20 minutes to go over those stackoverflow links to learn LINQ and also ASP.NET C# class and I found that those links are really helpful for me to warm up LINQ. It is tough for me to see that after 18 months I still do not make big progress on LINQ and the functional programming syntax still looks like foreigners to me.

Most of important change is that I learn better recursive function design after 18 months. I was surprised that I ended my last practice with so many issues. The base case should be selected to avoid duplicated count of each path. I like to see the depth first search algorithm specially a recursive function is written in very structured way, base case is very clear and also the recurrence formula afterwards.

Follow up 

Dec. 25, 2017
Early in the morning I got code review, and I was so excited to read the review. Here is the link of code review.

Binary tree root to leaf path minimum path value with the path

Nov. 15, 2017

I like to document my mock interview practice on this algorithm. The topic is about analysis of the algorithm, how to reason to find possible bugs?

Here is C# practice code.  I added line 27 to line 32 to fix the bug since the peer told me that the edge case with no children. The advice from the peer is "After writing the code need to analyze more before running it". 

Story of analysis

I need to explain how the depth first search works since peer asked if I should add an argument of function to pass the existing value. I did explain the algorithm in the mock interview, but the peer felt that he did not know C# very well and got confused. 

I like to write my story to show how I analyze the algorithm after the mock interview, try to make the explanation to a very good one. 

Let us go over  a tree with the following nodes:

      0
  /   |   \
 4   3   6
 /
3

The depth first search algorithm can be solved this way. The root node with value 0 has a tree, to find its minimum path to the leaf node, first if the root node is null, then value is 0; if the root node is not null, and if the root node has no children, it is a base case, the minimum path is the value of root. Otherwise, go over each children of root node with value 0, and go to each child in the array [node 4, node 3, node 6], and ask each node to get its minimum value for the path, denoted as Mi, and just add root node value 0 to Math.Min(Mi, i from 0 to 2).

Miss a base case

From the above paragraph, I highlighted the base case I missed in mock interview using brown color, and the peer had to tell me that there will be a problem if there is no children. In other words, in the tree showing in the above diagram, if the root node with value 0 has no children, it is a base case, the minimum path is the value of root.

Binary tree root to leaf path minimum path value with the path

June 14, 2017

Introduction

   

It is very interesting to practice binary tree path sum with the same value. Julia did the practice in 2016. Today she did practice twice, first she rewrote the algorithm better to represent her understanding the algorithm - the recursive function.

And then she practice mocking experience, she wrote an extended algorithm to find the minimum path sum from root to leaf, the return value is the minimum path sum and also return the path.

 

 

Code practice 

 

3 practices: 

 July 28, 2016, C# practice

 June 14, 2017, C# practice

June 14, 2017 9:49pm  - C# practice

In 3rd practice, Julia was asked to extend the algorithm in the mocking experience, add the minimal sales path to the output as well. 

It is again the opportunity to practice how DFS works, use a string variable to track all the nodes in the path. 

 

Rookie in recursive function design

May 29, 2017

Introduction

It is the great experience to teach myself how to write a correct recursive function to implement a depth first search algorithm. Julia spent over hours to teach herself, how to track a route in depth first search over one hour.

In order to figure out the issue, Julia wrote a depth first search algorithm using stack to help herself. She compared to the version using stack to the one using recursive function. She found out that the issue she had, she did not need to use memoization, she needed a memo to mark visited node to avoid dead loop.

Code practice 

C# code with dead loop, stack overflow issue. Mocking code is here. 

C# code to write a stack to implement Depth First Search (DFS). Code is here. 

C# code to write a recursive function. Code is here. 

A cheerful heart is medicine. Smile to my own mistake, next time I will ace the recursive function. Coding is done by a human, crafting takes practice!

Recursive - HARD TO TELL

Argument:

Use non-recursive depth first search algorithm to help the design. Using an explicit stack, it is much easy to follow. Write pseudo code, figure out base case, the design to avoid dead loop, cycle issue, memoization issue, structure the algorithm first. And then use it as the helper of recursive function design.

Recursive function is short and efficient to implement DFS, but error-prone. It is not straightforward. Practice this way to help yourself.

Use stack to help

Every mistake is valuable

I should say that memoization is extra, next step. Need to work on basic recursive function boundary check first. One thing is to test the code with the sample test cases, slowly and carefully, mark the test case for each line of code using comment.

To be a good tester all the time. Read your own code and go over it, with test cases. Julia, you got the tip from mocking experience.

Max Score - RookieRank 3

May 6, 2017


Plan to work on the algorithm: Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.

Follow up 

May 7, 2017 9:20am

C# code in the contest is here, scored 3.5 out of 35.

Follow up 

Study the discussion about the solution, the link is here.

1. The following implementation uses memoization, backtracking, and backward processing:

C# practice code is here which passes all test cases.

2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is here.

3. Bit mask - pass all test cases
C# practice code is here.

Bit manipulation 4 things to review

1. Get integer 2ⁱ:
//use left shift i times,
bitToCheck = 1 <<  i

2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck

3. Get ith bit:
bitmask |= bitToCheck,

4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck


4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is here.
string.Join(",", bitmask) takes too much time.

Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].

5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.

Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.

Algorithm analysis

It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.

The maximum score of k problem can be solved by choosing any number as the last kth number, and then work on the maximum score of k - 1 problem. Use bitmask as key to do memoization.

Actionable Items

Review previous practice, and find some cases to use bitmask.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union        
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

2. Hackerearth.com dynamic programming and bit masking, article link is here.

Recursive function small talk

April 19, 2017

Introduction

It is a good practice to write down a simple test case, and go over the test case and explain the algorithm, write down every step and every detail to show how you are serious about the talk; show some good analysis by writing down some notes, like mathematical expression, some terms about computer algorithm, and things like pseudo code will be perfect because a person knows recursive function, her writing will terminate because one iteration is enough.

Julia recalled her only experience in 2016 and then she knew that she should write down more transcript instead of code. Try to put 10 minutes in coding writing, first 10 minutes to write down the problem, and everything to ensure the problem is communicated properly, and also the idea will help to lead a bug-free solution.

Julia learned in April after 5 or 6 mocking experience, suddenly she did not scare at all. She likes to play free and use this non-algorithm approach.

Recursive function or DFS algorithm is the most popular algorithm Julia learned to master in 2017.

Recursive function 

Transcript is here to review.

Transcript is being compiled to a new version. Here is the C# code.

Hackerrank: Colliding Circles

April 14, 2017

Problem statement: Colliding Circles

Work on the algorithm.

Plan to spend 2 hours to work on algorithm 4:00 pm - 6:00 pm.

Discussion

Julia read this comment and try to learn from the sharing.

blubberdiblub

comment about colliding circles -

5 lines of code - math - combinatorics, full score

recursive - get 10 points

recursive and memorization - get 32.50

Wishful thinking

Stay outdoor and enjoy sunshine and tennis sport this beautiful day in Vancouver - Easter holiday

French Open

What is your first Impact of tennis game?

Impact The Game: What Makes Your Game Unique?

Setting the scene for Roland Garros 2015 feat. Ana, Simona, Jo and Fabio


US Open: Behind the Scenes with Ana Ivanovic, Simona Halep, Jack Sock & Jo-Wilfried Tsonga

Code review: Lucky number 8

March 5, 2016

Problem statement

Introduction

Julia had a few submissions in the contest, she tried 12 submissions. Scores is an interesting array like this, [0, 2, 1.8, 3.6, 10.8]. The final version in the contest, a C# practice in the contest, scored 10.8 out of maximum score 19.80 30.

Lucky number 8 is the medium level algorithm in the week of code #28, Julia took the recursive function as an approach, in order to score more points, she wrote more than 450 lines of code.

Julia did not have too many choices in the contest, the dynamic programming approach is too difficult for her to figure out. Actually she was math major graduate, and then she just enjoyed the workout on this analysis. She was writing a "book" (a joke to verbose coding), actually computer science on hackerrank contest taught her a lesson - to be thrift on time to write code, if she can be ...

Julia spent some time to review hackerrank contest performance  and then looked into the issues of week of code #28, she took a look at the algorithm submissions, she was so surprised, my God, it is such a great workout on recursive function. This is like sports - but it is a time-consuming marathon. This is her first time to write a recursive function and spent more than a few hours, and experienced a little success. Cheers! Julia, good job, even it is 10.8, 30% of maximum score 30. Julia likes to call this algorithm with this submission with a beautiful name by Vancouver islands: Tufino, a vacation place she should take instead of going back to China, a popular summer place to visit whales from touring boats.

Today, Julia likes to show herself how to score maximum score. Learn a dynamic programming after she learned the lesson through the contest.

The most important is to work on the example 968 and figure out how to solve the problem to get the answer 3.

Lesson learned

450 lines of code using recursive function cannot beat 20 50 lines of code using dynamic programming. But Julia also learned the lesson through practice, not at work. That is the importance of practice!

Facts:

In order to score more points in the contest, Julia continuously wrote more code until 450 lines. She had determination to make more points, she showed her passion to solve the problem.

Actionable Items

1. Read editorial notes:

In this problem, you are given a sequence of digits of length . You have to find the number of non-contiguous subsequences, such that the number formed by their concatenation is divisible by .

Observe a bit,

The number is formed by concatenating the non-contiguous subsequences, which implies that the number itself is a subsequence and vice-versa.

So the problem boils down to counting the ways you can make a subsequence divisible by . This can be done by Dynamic Programming.

At any position of the sequence, you need to consider two cases:

1. Concatenate the digit at the position with your current subsequence and move to next position.
2. Leave the digit and move to next position.

The idea can be coded with states: Current position and Remainder of the subsequence modulo 8.

2. Check all Google's employees' submission on this algorithm:
Study Java code first, write C# solution with comments.

Work on frequency table to help understanding the algorithm:

Read the above table, we can tell that numbers: 96, 8, 968 are 3 numbers to be divisible by 8, and we found the answer. Is that easy to follow this frequency table?

C# code for Code review is here. Extract a function, make other changes, this version of C# code is better for review, here.

3. Google keyword search:

states? Current position and Remainder of the subsequence module 8

4. Dynamic programming vs recursive function - check stackoverflow.com

Code review

Plan to make the code more meaningful, and then post a question on codereview.stackexchange.com.

HackerRank - university code sprint - Array construction - code review

Dec. 25, 2016

Introduction
A few of facts about the algorithm:
1. In contest, spent over 10 hours to work on
2. The algorithm is advanced one
3. Score 8 out of 80
4. The algorithm is really a challenging one
5. Spent over 10 hours to work on after the contest, studied C# code


http://juliachencoding.blogspot.ca/search/label/array%20construction%20%28series%201%20of%205%29

Workout 

1. Plan to write a code review request on stackexchange.com.
2. Need to study how to post a good code review on stackexchange.com
3. Be careful that do not get down vote, off-topic
4. Put down ideas why to ask code review
5. Julia also learned through the code review, how to write better English, her grammar mistakes.


Code Review Link

Case study:
http://meta.codereview.stackexchange.com/a/1035/123986

http://meta.codereview.stackexchange.com/users/11974/user1131146-account-abandoned

Array Construction - Code Review

Dec. 11, 2016

Introduction

Array construction is the first advanced algorithm Julia tried to work on in the contest, she did try to work on over 10 hours, but she scored 0 (maximum score 80). Through the contest, she started to understand the algorithm and built up strong interest in problem solving.

Later, she read one of solution, and then, spent over 4 hours to understand the pruning idea to avoid timeout issue.

Later, she did very intensive research on recursive function. But, she needs to get it on stackexchange.com, share her interest and questions, and then, see if she will get any surprise. Success after team work, Julia likes to practice the belief.

Previous blogs about the algorithm:
Labels: Array Construction (Series 1 of 5)

http://juliachencoding.blogspot.ca/2016/11/hackerrank-codesprint-array.html

Workout:

Plan to post a question on stackoverflow.com code review for code review.

Leetcode 329: Longest increasing path in matrix

June  20, 2016

problem statement:

Given an integer matrix, find the length of the longest increasing path.From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

329. Longest Increasing Path in a matrix

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Study the code written in Java:

http://blog.csdn.net/sbitswc/article/details/50707203

1st practice using C#: 

https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4

Question and answer:

1. How is the practice? 

The study was very good. DFS - using recursive call, and then, tricky part is to use memorization to 

avoid duplicated calculation. 

2. Talk more with an easy example, therefore, next time you will not forget the problem after 

a few months. 

Answer: Will write something here. 

1. Talk about node row = 2, col =1, value is 1, denoted as start1,  3 neigbors, left (value 2), right (value 1), up(value 6)

2. Try to avoid loops - base case checking, always go to the node value >= current value >= start node '1'

3. Also, if neighbour node left (value 2) has maximum increasing path in matrix n, then, what we can know:

   value 1 < value 2, then, start1's longest path at least 1 + value2's longest increasing path. Need to check other 2 

  neighbors to see if it is larger value

    left neighbor (value 2)'s longest increasing path in matrix 2->6->9, length is 3;

    right neighbor (value 1)'s longest increasing path in matrix 1->8, length is 2; 

    upper neighbor (value 6)'s longest increasing path in matrix (actually 2 of them, 6->9 or 6->8), length is 2. 

4. DFS algorithm can be set up using recursive function; also, there are total 3*3 = 9 nodes in the above matrix, 

    each node's increasing path in matrix should not count more than once. 

    For example, nums[0,0] = 9, is maximum value of matrix, so the longest path = 1. 

    Let us put a sentence together. How about the following:

    Be greedy, check your neighbors (at most 4), and find maximum one with longest increasing path in matrix, and then use the path

to build your own. The value is 1 + that neighbor's problem, where the recursive function is constructed. 

5. The design of algorithm - brute force solution - how many paths in the matrix - n^4 = n x n x n x n; filter out non-

increasing path, then find maximum value - not efficient

6. For each node in matrix, find its longest increasing path in matrix, nxn nodes, each node, DFS algorithm is applied. 

    at most nxn node is checked about increasing order. <- try to reason the time complexity -> ...

    Will be less than n^4. 

7. Prepare a check list for the design:

    1. Run time issue - index out of range - array - boundary check 

        loops - always go to bigger value - no loop 

    2. time complexity - nxn node, each one does DFS; each DFS, at most 4 n^2 comparison of value. 

    3. space complexity - use extra array nxn to store bool value - memorization  

    4. value is bigger/ smaller / 0, 0 - not possible, at least 1, miss count - recursive, should be easy. 

    5. Brute force solution and its issues - more time consuming etc., duplication calculation    

Most important discussion: 

find the idea to store in extra array: 

1. Extra array to store the length of "longest increasing path in matrix" for each node in the array - (working idea)

2. Extra array to mark the node is visited or not -  (not enough for calculation!)

 denote DFS function to calculate the longest increasing path in matrix, then starting from start1, the function will be

left->left->up->up, in other words, from 1->2->6->9, and then, 

up->right,    1->6->8   

up-> up,       1->6->9, 

the visiting order of neighbors is left, down, right, up.

https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4

anti-clockwise, left, down, right, up  - line 116 - 120

So, the cache value of (2, 1) is 4, longest path is 4 (1->2->6->9); and 6 nodes in matrix are calculated and saved with 

cache value - 2 matrix(2,0), 6(1,0), 9(0,0), 6(1,1), 8(1,2), 9(0,1), the order of saving is 

9(0,0),          - 0 neighbor

6(1,0),          - 1 neighbor

2 matrix(2,0) - 1neighbor, value 1

6(1,1)

8(1,2)            

9(0,1)

6(1,1)   - 2 neighbors, comparison 1 vs 1 

1(2,1)   - 2 neighbors, comparison 3 vs 2

Use stack to help to track the order: 

start1 node, 2 neighbors

go to left neighbor first, 

      push to stack, 2, 6, 9

no down neighbor, skip right

then go to up neighbour, 

     ...

Statistics: 

Time to work out order of calculation cache value in the above list takes more than 10 minutes. 

Two motivations to work on reasoning and analysis:

1. Leetcode 329 is hard

2. Being able to write down bug free, executable code in 20 minutes. 

  3. Study more solutions from others, and then, practice it using C#. Study one using C++. 

C++ solution:

http://gaocegege.com/Blog/algorithm/leetcode329

http://codingmelon.com/2016/01/20/longest-increasing-path-in-a-matrix-leetcode-329/

To be continued. 

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

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:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

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

         https://gist.github.com/jianminchen/2279967c64a712fb138355b69a6201dd

Question and Answer:

1. What do you like this approach? DFS using recursive function, which returns the count? 

It is easy to write, less error prone; most efficient in time consumption. 

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.

C# code 

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.

C# code with an extra debug function

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

C# code using jagged array

          

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

C# code using DFS, recursive function

         

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

C# code using reference integer in function argument     

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

C# code using stack

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. 

HackerRank: Connected Cell in a Grid (III) - C# solution (III) - using recursive function

April 17, 2016

problem statement:

https://www.hackerrank.com/challenges/connected-cell-in-a-grid

Here is the code studied using DFS function with return value.

https://gist.github.com/jianminchen/bc2c399407a30181ca68292459a3c791

Julia likes to practice using same idea, write her own implementation.

Practice #1: 

https://gist.github.com/jianminchen/fd909c3545e2081cf2dd2b6daea5900f

Time spent:

Copy main function from previous implementation, and write recursive function - it takes less than 15 minutes.

First time write, no bug!

April 18, 2018

Here is another writing over 30 minutes:
Practice #2: 
https://gist.github.com/jianminchen/d434bcc59ebc8eb7c2cbb20c6f48ac06

The practice goal is to see if I can shorten the time to 10 minutes in writing. How good I can write.

But, surprisingly, the practice takes 30 minutes; and I found out the several issues:
1. Timeout - recursive calls, if/ while checking
2. Array.GetLength api

First, time out issue; read a row of '0' or '1', should be if, I put a while. <- it takes more than 10 minutes to find out. I pinpoint recursive call, because I have doubt, not 100% sure.

And then, I tried to avoid the recursive call to itself, and then, (dr, dc), mistakely I put (dr, dr); HackerRank shows wrong answers for 2 test cases.

Make one change a time, and see if I can shorten the time to 10 minutes.

Study Array.getLength()
https://msdn.microsoft.com/en-us/library/system.array.getlength(v=vs.110).aspx

Another version, it takes 14 minutes to write, without a bug:
Practice #3: 
https://gist.github.com/jianminchen/bd155e574b32ebb163455dad02fa76b1

Julia's performance is up and down, from 15 minutes to 30 minutes.
Again, all practices links:
#1
https://gist.github.com/jianminchen/fd909c3545e2081cf2dd2b6daea5900f
#2
https://gist.github.com/jianminchen/d434bcc59ebc8eb7c2cbb20c6f48ac06
#3
https://gist.github.com/jianminchen/bd155e574b32ebb163455dad02fa76b1

Work on speed and accuracy. Practice, more concentrated on writing. More alert on bug code. More knowledge about api, and basic things.

Learn Jagged Array -
http://stackoverflow.com/questions/597720/what-are-the-differences-between-a-multidimensional-array-and-an-array-of-arrays

HackerRank: Count string (III)

April 9, 2016

 Problem statement

 Solution to study:

Julia's C# practice with bugs


 The code has time out issue, wrong answer, and it only scores 3 out of 80.

code source:

https://www.hackerrank.com/casaro

Statistics:

Time spent:  1:00pm - 3:00pm
Go through test cases

C# code to study, also show C# source code here.



April 10, 2016

Action items:

Need to think about in computer theory, NFA, DFA, and argue that the above solution in theory has flaws.

Follow up after 12 months

Julia checked the blog statistics, and the blog has a lot of views recently. So, she reformatted the blog style and she will review the algorithm very soon, and also post a question on code review.

quicksort: a practice makes difference

February 2, 2016

Introduction

Julia likes to work on basic things on algorithm problem solving, like brute force solution, recursive function design, divide and conquer solution, partitioning; So, she can write code everyday on algorithm.

Review the quicksort algorithm, and then, practice using C# programming language. So many times Julia went through the review of quick sort algorithm, but to write it in less than 10 minutes, without a bug, without stress, takes more dedicated effort - maybe write a blog to share will help.   

Julia likes to rewrite the above paragraph in April 9, 2018.

Quicksort warmup

First review the blog - the quick algorithm written in Java programming language. Julia must like the idea of choosing pivot value - "// simple version - pick the right most value as the pivot ". As a sports programmer, Julia knows that the power of using a simple test case, she likes to do it here. 

Let us describe how quick sort works: - explain it using 5 minutes - 10 minutes to write the code 

1. First, using partition, and then, divide and conquer, use recursive function calls to solve the problem.

Most important technique, is to design a partition - 2-way partition, how to design the partition, choose pivot point, and how to do partition step by step.

Let us work on a simple example and have discussion, show the procedure of partition.

Let us say that array 1, 2, 3, 4, 5, 6, sorted, and then we like to derive the above sorted array using this one, 1, 3, 2, 5, 4, 6.

One of ideas to choose pivot position, is to choose last number in the array.  For the example, choose last one in the array, 6, the position of pivot point, left side <= 6, right side > 6. So, do you see the problem, 6 is not ideal case. No swap, second partition with 0 values; in other words, all values go to first partition. 

Two way partition

Let us work on another order: 1, 6, 2, 5, 4, 3, 

1. Choose pivot value - last element in the array, value 3
2. Work on partition the array, left partition <= 3, right partition > 3
3. Two partitions are 1, 2, 6, 5, 4, 3

4. Put the pivot point in-between, 1, 2, 3,  6, 5, 4
5. Divide and conquer, solve two small subproblems, use recursive call. 

Use a diagram to show progress:      

Scan the array once from left to right, and then keep track of the start position of right partition. Anything less than 3 will be in left partition.  

The easy way to remember is to find right partition's start position. 

Two way partition - test case

1, 2, 6, 5, 4, 3  -> move pivot value 3 between two partitions

1, 2, 3,  6, 5, 4

Step by step, 

first, after partitioning, the array is the following:

1, 2, 6, 5, 4, 3 

so right side partition starting from array's index value 2 to 4, values are highlighted in background color of green. 

Left side partition:

1  2

left partition, array's index is from 0 to 1. 

Right side partition -  start and end position. 

6 5 4 

right partition, array's index is from 2 to 4. 

And then the pivot value 3 is inserted in-between left partition and right partition. 

1, 2, 3,  6, 5, 4

Let us recap what we practice here, go over a simple test case, and then choose a pivot value, and then partition, divide and conquer, go to solve two small problems using recursive calls. 

Julia's practice:

Quick sort algorithm writing in C# - less than 20 minutes (18 minutes to write the code with comments)

2nd practice using C# 

Quicksort Lecture Study

Julia, spend one hours to read the webpage, and enjoy the great lecture. Reading is much important than coding. And then, work on some questions in the lecture.

princeton lecture notes

Questions and Answers

February 3, 2016

After reading her favourite lecture notes, Julia likes to respond something to entertain quicksort algorithm practice, put something together with her own thinking based on discussion from reading material:

Fact 1:
Q1. Quick sort algorithm will work even in worst case, no dead loop. Why? 
Arguments:
1. Each recursive function, at least one value is resolved, no more work for the value. That is pivot point. So, at most, each recursive call solves one value, n recursive call will solve all n values in the array. Is it fun to design the algorithm? Yes.

Q2. Quicksort function design - only solve one value to position correctly, in the whole array. This is not efficient? 
Arguments:
1. This is the fact. And it works fine. And if you remember that, you can write a quick sort algorithm in less than 5 minutes. 
2. So, position one value, partition array into two sections. 

Q3. Partition can use different strategies, only important and should work on more is to find one, work out as fast as you can. And make it easy to remember. What is your advice? 
Advice:
  Choose last one in the array as a pivot point, and then, find the partition - swap and maintain a partition (each value in the partition  >  pivot value) just on right side of array. Use two pointers to find the partition two values - start, end position. 

Q4. Is this algorithm using in-place without extra space? 
Answer: 
Yes, the answer is staying in the original array, no extra space (O(1), not O(n)). So, array is used to store result, only swap two nodes' value if need. 

Facts: at most how many swap?     it depends. O(n^2)
           How many recursive calls?  n 

Because it is using in-place, the quicksort function design takes 3 input arguments, original array, start, end. 

If you cannot come out best design using in-place, you may need extra time. 

Feb. 4, 2016 Q5. Work on Leetcode - partition list
86. Partition list
http://www.cnblogs.com/springfor/p/3862392.html

328. Odd Even Linked List

Follow up after 9 months

Nov. 24, 2016
Review the code review about quick sort. 
Answer the question, link is here.  

Follow up after 13 months

March 14, 2017
1. Read all algorithms in the blog, the blogger got Google and Linkedin offer. The algorithms may be a good study material for Julia.

2. Practice one more time, C# code. Add test case for partition method and quicksort method.