Bonetrousle - HackerRank world code sprint #6 - code study

August 28, 2016


Study 5+ C# submission code, put some notes here as well.

1. Use Queue, using structure, excellent code to study -
C# submission to study.

 rank before 190/ 5332




Great workout using Queue, Julia came out this idea through practice, but she could not write down code. She tried to write recursive function.

2. a while loop, less than 40 lines code
C# submission

rank before 200/ 5332, score around 250/380

3. C# submission

4. C# submission

5. Great code! C# submission


rank in range of 270 - 300/ 5332 participants (score in range of 

180- 200/380)

Time to go over C# string class: 

C# string class join method

Motivation talk:

work hard! 

Julia ranks 1112 on world code sprint #6. If she can work out the algorithm - Bonetrousle, based on her current score is 100, she can score another 50, from score of 100 to 150, then, she can get into top 1100 to top 550 - 650 ranking. 

Leetcode 126: word ladder II - using BFS - Queue, Set Paths (Practice VI)

May 30, 2016

Study the blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-study-c.html

And continue to write C# solution - focus on coding, design ideas.
1. First practice, with a bug on just after line 111 - missing to add tmpList to newList.
https://gist.github.com/jianminchen/9e45848c86ebaaa8f0bc0d881cfd1ad5

2. Fix the bug and pass the test case, add line 112:
https://gist.github.com/jianminchen/e3466a9f1319f62f869aa53487c05536

Questions and Answers:

1. How is the practice?

Here are some sharing:
1. Write down the comment about the idea to solve the problem, from line 23 - line 58

Good idea is to solve 50% of problem. Repeat the idea in the following:

Explain the idea using the test case:

dot -> dog           hit->hot ->                    -> cog                               lot -> log           so, the queue process is (breadth first search)           first  layer:        hit           second layer:   hot           third  layer:      dot, lot           forth  layer:      dog, log           fifth  layer:        cog                      build ladders step by step, from startWord to current.                       Dictionary<string, List<List<string>>> ladders                      each string will be the key in ladders           hit -> hit           hot -> one list, {"hit", "hot"}           dot -> one list, {"hit", "hot", "dot"}           lot -> one list, {"hit", "hot", "lot"}           dog -> one list, {"hit", "hot", "dot", "dog"}           log -> one list, {"hit", "hot", "lot", "log"}           cog -> two lists,                            {"hit", "hot", "dot", "dog", "cog"}                            {"hit", "hot", "lot", "log", "cog"} 2. Some highlights? First of all, first writing is wrong. There are 5 levels, 4 loops and then one if, Julia got confused the position of code. So, marks are added in the comment just after the loop - start statement and also close }. Work on indentation - Better to write down your own marks.  line 75   // level 1, while loop      line 88   // level 2, for loop           line 93   // level 3, for loop                   line 97   // level 4, for loop                       line 104  // level 5, if statement                       line 121 //  end of level 5, }                   line 122 // end of level 4, }           line 125 // end of level 3, - end for loop for hop string length     line 128   // end of level 2, - processing - all nodes in the same distance in the queue line 139  // level 1 - processing queue - queue.Count > 0 line 95, char variable name: char backtracking_char, just friendly remind to do backtracking later on line 124. line 102, string variable name change: newstring -> nextHop, hopefully the current one is more meaningful. 3. Actionable items? Write again a few times, try to finish coding in 30 minutes, and write down issues not resolved. Coding is like sports, just do it!  4. More to share about the algorithm? Share one graph to illustrate the graph problem of word ladder: 5. A lot of people complained the problem is too tough. Julia, you miss the most important things in the design? Time out is a big issue. And also, we need to discuss how to avoid a cycle in the list; multiple paths can be found from start word to end word. Challenge 1:  The visited word must be removed sometime to avoid a cycle; Challenge 2:  When to remove visited words from dictionary properly? Same distance, one word can repeat multiple times. Sure, let us talk about it! on line 84, inside the while loop, Hashset<string> nextHops_BFS are defined. We need to examine this Hashset: on line 120, nextHop is added one by one to the HashSet, but no action is taken on the HashSet. Lazy processing here! Until all nodes in the current layer are processed, dequeue from the queue. From line 133 - 137, add next layer hops into the queue, where to find the nodes - nextHops_BFS . Remove the words from wordList just before adding to the queue. Put line 135 just after line 120, and see what is difference. The program will generate no output for test case:                               dot -> dog           hit->hot ->                    -> cog                               lot ->  log log word's next layer is cog, and dog word's next layer is cog as well. Both routes have same word, terminate word. cog can not be removed from wordDist Hashset until two routes are processed both. Actually, the graph should look likes the following:                                     dot -> dog -> cog           hit->hot ->                                                  lot -> log -> cog  In fifth layer, cog word shows up on line 102 twice: line 102 if (wordList.Contains(nextHop)) So, 2 lists can be added with the same word "cog" as last one. It is important to keep wordList untouched until the whole layer is processed, then, remove words in HashSet nextHops_BFS from wordList.  Rules to obey in the design:1. The same word does not repeat twice in the same list. For example, hit->hot->lot->log->lot-log..., it may go on forever.  2. One word does not show up in more than one list, except start word and end word. For example, test case, hit, cog are only exceptions.  Not True. "hot" shows up in two lists.  3. Words in the distance n should not be any word in distance 0 to n-1.                               dot -> dog           hit->hot ->                    -> cog                               lot ->  log So, when dog or log are processed in the queue, all words less than 4, hit, hot, dot, lot should be removed from HashSet wordList.  Need to go through those cases one by one.  Actionable items: Read the blog and then implement the solutions as well. http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html

Leetcode 126: word ladder II - study C++ code using BFS - Queue (Practice V)

May 30, 2016

Study the code:
http://mrsuyi.com/2016/01/31/leetcode-126/

C# code:

https://gist.github.com/jianminchen/3e99a564341995e2dd93e2fd3580aaef

Questions and Answers:

1. How is the practice? 

Julia spent more than 1 hour to work on practice.

Test case:
hit -> hot -> dot -> dog - > log
hit -> hot -> lot -> log  ->  cog

1. Line 40 - 43, add beginWord into Dictionary. The code can be extracted to one standalone function.

2. Line 52, inside while loop, HashSet, try to figure out the purpose, named: bfs_nextNodes
    same distance nodes to startWord will stay in the same HashSet.

3. Line 70, arr.ToString(), debug runtime error, the string will be "new String()". Bug is fixed, using "new string(char[])"

4. Line 84 - 87, add discussion of ladders.ContainsKey(newstring), otherwise,
    ladders[newstring].AddRange(newList) through runtime error. ladders[newstring] is null pointer.
Test case:
1. First time try, only one path is added; miss the second path (hit -> hot -> lot -> log  ->  cog)

5. line 99, Dictionary API ContainsKey, not Contains, vs. HashMap

2. What is the idea to implement the solution using your own words?

The idea is much clever. Explain the idea using the test case:

dot -> dog           hit->hot ->                    -> cog                               lot -> log           so, the queue process is (breadth first search)           first  layer:        hit           second layer:   hot           third  layer:      dot, lot           forth  layer:      dog, log           fifth  layer:        cog                      build ladders step by step, from startWord to current.                      Dictionary<string, List<List<string>>> ladders                      each string will be the key in ladders           hit -> hit           hot -> one list, {"hit", "hot"}           dot -> one list, {"hit", "hot", "dot"}           lot -> one list, {"hit", "hot", "lot"}           dog -> one list, {"hit", "hot", "dot", "dog"}           log -> one list, {"hit", "hot", "lot", "log"}           cog -> two lists,                            {"hit", "hot", "dot", "dog", "cog"}                            {"hit", "hot", "lot", "log", "cog"}

Connect nodes at the same level in a binary tree

May 16, 2016 

Connect nodes at the same level in a binary tree  

http://www.geeksforgeeks.org/connect-nodes-at-same-level/   (? bug)

better one:
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html

Using Queue - 
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree.html

Question and answer:

1. How long do you study the problem? What do you learn? 

Julia spent more than 1 hour to study the blogs above. She will write down her own notes about the test case, analysis and solution, and post them in the blog. Encourage herself to write, to share and to improve her confidence on problem solving. 

Will come back soon. 

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

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

Warmup coding: 

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

https://gist.github.com/jianminchen/9cf4702b56dc7a57ec6b699449b89593

Question and answer: 

1. How is the warmup experience? 

Because this is the second one, after 1 hour writing, debugging the code in first practice using dimensional array/ queue, this one is much easy. Just replace the dimension array using jagged array. 

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. 

Leetcode 210: course schedule

April 30, 2016

Read the problem and analysis, read python code 10 - 20 minutes.

http://www.tangjikai.com/algorithms/leetcode-207-208-course-schedule-i-ii


Read Java code later.
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/210.course-schedule-ii.java

Understand the problem and solution quickly through this blog: (10 minutes to read)

http://www.voidcn.com/blog/qq508618087/article/p-5039267.html

Another 10 minutes to read this blog:

http://www.cnblogs.com/grandyang/p/4504793.html

Read 10-20 minutes about graph representation:  (11:40am - 12:00pm)

https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Spent 20 minutes to watch the video:
https://class.coursera.org/algo-003/lecture

Take some notes:
1. Sink Vertex - concept
2. To compute topological ordering:
- Let v be a sink vertex of G
- set f(v) = n
- recurse on G-{v}

why does it work? when v is assigned to position i

Topological Sort vis DFS
DFS-Loop (graph G)
- mark all nodes unexplored
- current_label = n [to keep track of ordering]
- for each vertex v in set G:
  - if v not yet explored [ in some previous DFS call]
    - DFS( G, v)

DFS( graph G, start vertex s)
- mark s explored
- for every edge (s, v):
  - if v not yet explored
   - DFS (G, v)
- Set f(s) = current_label
- current_label --


Read an article: (1:04pm - 1:14pm)
http://www.geeksforgeeks.org/topological-sorting/

Fun part later:

play with visual presentation through the link:
https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html

C# code for Leetcode 210:

https://gist.github.com/jianminchen/5873fc014e806d626807917959e05ea2

update C# code to add the example in the comment, and then, update code to match the example:
https://gist.github.com/jianminchen/85478d1bed0faf4410b76a7af3a48fc3

Question and answer: 

What do you learn today? And what is idea to solve this course schedule problem? 

1. First, Julia learned how to do the topological sort, here is an example with its diagram:

The image should be the following: directed edge 0->1, which means that 0 is prerequisite course. 

Double check with geekforgeeks article:

http://www.geeksforgeeks.org/topological-sorting/

Confused since it is the first time to draw the diagram. 

So, always start from nodes with 0 indegree (node 0, node 4). 

So, the ordering can be 0, 1, 2, 3, 4; or 4, 0, 1, 2, 3

2. So, Julia also practices to do some counting for vertex. 

vertex 0: indegree 0, but dependency list: 1, 2, 3

vertex 1: indegree 1, but dependency list: empty set

...

So, Julia learns to manage the graph using indegree array for the graph, and dependency list for each vertex. 

3. Julia also learns the easy way to do toplogical sorting using the above graph, and also make the code easy to read, once you remember the graph, you can read the code in 5 minutes. 

So, I updated the version of C# code to match this test case:

https://gist.github.com/jianminchen/85478d1bed0faf4410b76a7af3a48fc3

add explanation variable - line 51:

int[] tmpDep = new int[2] { prerequisites[i][1] , prerequisites[i][0] };

tmpDep[0] - 0 is the index, similar to the above diagram node 0, add dependency list: 1, 2, 3

tmpDep[1] - 1 is the index, similar to the above diagram node 1.

4.  Now, understanding one example. Ready to talk about idea of problem solving. 

The idea to solve this course schedule problem is first for each vertex to get indegree value and also dependency list.  

Do not get confused with dependency.   

In above diagram, the directed graph,  course 1 should take after course 0, so course 1 is depending on course 0; course 1 has indegree 1 related from course 0. course 0 has no indegree.  If course 2, 3 also has to take after course 0, so course 0 has dependency list: 1, 2, 3. If course 0 is dequeue, then, course 0's dependency list: 1, 2, 3, 3 courses' indegree value has to be decremented by one. 

Secondly, to find all nodes in the graph with indegree's value 0; put them in the queue {4, 0}, and then, dequeue one by one, add to the result list; and then, each node in the dependency list will decrease the indegree value by 1; and then, if any node is found with 0 indegree value, then, it will be added to the queue as well. 

In other words, here are steps:

1. Add nodes with indegree value 0 to the queue; 

2. if queue is not empty, dequeue one in the front, 

    add one to the result; 

    check dependency list one by one, 

       decrement one on indegree value,     

       if the node's indegree value is 0, then add to the queue

More reading:

http://baike.baidu.com/view/4573323.htm

http://baike.baidu.com/view/288212.htm

statistics:
Time spent: 5+ hours

K index - Algorithm (II) using Queue

April 18, 2016

More code writing. Try to use Queue to solve the problem. Write more than one solution using Queue.

Julia practiced twice, first one hour she failed some test cases using HackerRank. And then, she tried again.

Practice #2:
https://gist.github.com/jianminchen/ce7ccfa5db5b57c36d6742b622e9153e

First blog about this algorithm - K index:

http://juliachencoding.blogspot.ca/2016/04/k-index-algorithm.html

Julia wrote C# implementation using Queue,
https://gist.github.com/jianminchen/63c0bccec2ab476d71abbe43c8837566

Test cases:
1. Input
4
1     2   3     4
5     6   7     8
9   10 11   12
10 14 15   16
2
Yes, 10 is found at arr[3,0], 2 steps away from arr[2,1]


Time spent:
More than 30 minutes

Learned from mistakes:
1. Two dimension array arr[,], use getLength(0) and getLength(1) for first and second dimension length; But, jagged array - arr[][], getLength(1) will throw exception, use arr.Length, arrp[0].Length to check the size.
 
The first practice using queue, Julia created a run-time exception - index out of range; the error is so late to catch, not in compile time. So, take it seriously. Array, two dimensional array, jagged array are very basics.

https://gist.github.com/jianminchen/93f963043c47649a496a2fccc862d801

change search array to use two dimensional array:
https://gist.github.com/jianminchen/9346c2d2cb2e611ec2db3519dc7a879a

Read blog:
http://stackoverflow.com/questions/597720/what-are-the-differences-between-a-multidimensional-array-and-an-array-of-arrays
http://stackoverflow.com/questions/12567329/multidimensional-array-vs?lq=1

https://msdn.microsoft.com/en-us/library/aa288453(v=vs.71).aspx

April 21, 2016
Julia found something she likes - C# tutorial
read it every day when you have 20 minutes in the morning.

https://msdn.microsoft.com/en-us/library/aa288436(v=vs.71).aspx

HackerRank - Connected Cell In A Grid (II) - C# solution (II) using Queue

April 17, 2:50 - 3:25

Problem statement


First practice using C#,  solution written by Julia:

C# practice by Julia


Study the code: 1. Use Queue, instead of using recursive calls, using 2 dimension array, excellent code to study:

Study code 

So, Julia did one more practice, and just wrote second implementation using idea in the above blog. 

Write C# code again using idea - 2 dimension array, queue, and also, mark the visited node using '2'. 
C# solution 1

Second Practice

It takes 30 minutes to write and fix bug, log interesting things happening in the practice:

1. First, fix the issue to read a row to a string, and then go over one char a time to get each node for the row.

   use Console.ReadKey()  first <- fatal error

2. use wrong local variable about key

3. Count should be 5 but 11 for one test case, count same thing more than once! - > add extra checking before counting. Or, set node is visited just before adding to the queue. 

Compare to the solution #1, two dimension array uses integer 1 or 0, my copy is using char '1', '0';
And also, the solution #1, every node sets visited true before adding to queue.
And my design, do not set, which causes problem. Same node is added to the queue more than once.

It is better to add unvisited node to the queue once.

Julia, you have to make sure that no bug in the code, it does not matter what idea you use. 

Third practice:

Write in 20 minutes, no bug:

3rd practice using C#


Again, 3 practices:

No. 1 - C# code

No. 2 - C# code

No. 3 - C# code

HackerRank: Connected Cell in a Grid - C# solution - using DFS

April 16, 2016

Practice one DFS algorithm this Saturday.

problem statement: connected cell in a grid


C# solution written by Julia:


Time spent:  4:48pm - 5:41pm 
20 minutes to think about design, 
30 minutes to write the code
Feeling: nervous when thinking about solution - DFS, it took more than 15 minutes
Study other submissions, and see if I can learn something, also figure out how to cut time to write the code. 

C# solution: 
Time spent: 60 minutes

1. Use Queue, intead of using recurisve calls, using 2 dimension array, excellent code to study.

Tips to learn: 
1. use integer as key: i*10+j
2. mark the visited node using value 2

2. Design the function to return a value 

Julia, people are smart, no need for extra bool array[row][col], just mark the visited node using a new value:

1. mark visited node using 'X'

3. use C# Tuple class, declare a shift array to get more organized. 8 neighbors nodes - go through array twice.


4. study the code


5. declare offset array for x and y - Julia likes the idea.

https://gist.github.com/jianminchen/737138aeb946961aded556181c06502e

Statistics:

1. 10 submissions, there are at least 2 of them using queue - Julia, you have to catch up this using queue!  <- write queue version, practice it 20 minutes, post your version down here!
2. 10 submission, 2-3 DFS algorithm return count <- easy way to track the count
3. Different ways to mark the node is visited.

Reviewed the algorithm on Nov. 16, 2016
- some one found the page through yahoo.com search.

Leetcode 102: Binary tree level order traversal

July 23, 2015

Problem statement:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

写代码发现很多问题. 程序要多写, 多练. 背算法可能也是一个途径. 从C++代码, 转化成C#, 犯了几个错. 一下学习到很多C#知识, 感觉不错! 练习6种方法. 

1. Solution 1: (push extra null node in the queue to divide level)

Read the blog:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeLevelOrderTraversal.cpp

convert it to C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal.cs

C# code passing leetcode online judge:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal2.cs

Solution 2: (using 3 variables to help queue to do BFS algorithm)

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal3.cs

Solution 3: DFS algorithm:

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

Solution 4: using two containers for current level, next level 

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal5.cs

Solution 5: one queue and iteratively solution (单个queue的迭代解法)
blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal6.cs

Solution 6: one queue and extra node null into queue to mark end of level

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal7.cs

Blogs to read:

1. http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/

2. http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html

3. http://blog.csdn.net/ljphhj/article/details/22428939