Leetcode 269: Alien dictionary

May 3, 2018

Introduction

Plan to spend time to review the algorithm again. I like to make the algorithm my favorite graph algorithm in May, 2018.

I know that it takes a lot of sacrifice from a friend who coached me through mock interview, how to pay attention to detail. I like to write the blog to express my thankfulness to those people. Like my hitting partner on tennis court, those algorithm practice trains me to think harder, work harder.

One day I wish I can use my mathematics training over years and be able to use some of them in the work. First I have to learn how to be a good software programmer first, my crafting skills has to be improved first.

Learn how to talk in Chinese about the algorithm

It is interesting to learn how to express the algorithm in Chinese first. I did 10 minutes study and made a gist based one a blog. Here is the gist. The algorithm with some improvement is here.

Plan to write a C# solution based on the above Java code.

Past practice

Here is my past practice. I need to warm up and write a solution. It is such great warmup to review code written more than 2 years ago, here is code I reviewed and wrote this time.

HackerRank - week code 28 - The value of friendship

January 14, 2017

The value of friendship - problem statement

In the contest

Read the discussion, and prepare to write some code.

Test case: 1 5 3 1 2 3 4 4 

What about 1 5 3 1 2 3 4 4 5 Would the answer be 16?

Discussion is here.

Test case - 16


One more discussion is here.

example:

Disjoint set

Review the content on wiki.

Julia spent a few hours to read discussion, and did some research to see how people in top-ranking of content discuss and share their experience. Anything she needs to catch up.

She studied the profile:

Another one shared the advice of using disjoint set, here is the comparison to his contest:

After the contest

Need to practice a few of them.
Study a few submissions in C#, first one is here.

Code review one of C# submission, and work on a test case - a graph with five nodes, 4 connected friendship,   1-2-3  4-5,   also 1 is friend of 3. 4 friendships, 1 - 2, 2 - 3, 1 - 3, 4 -5.

2+ hours study and debug, code review, continuously made improvements
C# code comparison:  Original is here, and Julia made a new one.

Highlights of change:
1. Change variable names - make it more meaningful.
2. Add one extra variable name in the class GraphNode.
3. Add one sample test case, and use the test case to help understand the code.
    Add comment for each function, help user to understand the algorithm.
                 

Status Report

Julia has to work on graph's algorithm in 2017, she understood the algorithm in the contest, but she did not have very strong confidence how to write a very clear, short, concise code in 1-2 hours. There are so many ideas in the submissions, a lot of them are with very short and clear, readable code.

Need to catch up and work hard on the algorithm.

Stackexchange.com code review is here.

Study leaderboard:
1. Eric Sheng
http://ericsheng.com/
printing ascending ascii code.
2. Computer faculty, facebook engineer - click here.
3. PH.D., click here.
4. engineer, coursera achievements, click here.
coursera certificate of algorithm? Look into later.
5. A lot of competition, SQL server program manager before, click here.
6. Look for intern, a lot of competition activities in programming, click here.
7. coursera course, master student, click here.
8. FSU financial math Ph.D., click here.
9. Banking industry experience, J2EE, click here.
10. Alibaba, click here.
11. ASU math phd., ranking around 400, click hackerrank, here.
12. A researcher, click here.
13. over 20 medals, graduate student, Microsoft, click here.
14. CA state programming contest, ranking around 500, HP engineer
15. undergraduate, google intern, ranking around 653,
16. rank 900 - a bachelor student - click here.

Continued Study:

1. More code review by Julia, Julia likes to find out code with good style, 22 C# submission with maximum score, all of players are in ranking top 500, Julia will have a good time learn graph algorithm this time.

Julia learns to write one by one.

Good variable names, click here.
DisjointSet class, click here.

One of code review, click here. (It took hours to rewrite, study first and then try to think about better way to represent.)

Code with unit test cases, study first (ID: yambe2002, ranking: 111/10432), link is here. Code review, link is here.

Julia learned a few things in S.O.L.I.D. principles through code review wiki post, and then she likes to do some code review using some of principles. Code is here.

HackerRank: World codesprint #4 - Roads in HackerLand - II - code study

July 20, 2016

First blog on this algorithm:

HackerRank: World codesprint #4 - Roads in HackerLand

http://juliachencoding.blogspot.ca/2016/06/hackerrank-world-codesprint-4-roads-in.html

Come back to work on this problem. Study editorial solution provided by HackerRank, and then,
review union find, minimum spanning tree algorithm with code first:

3 steps:
step 1: union find algorithm
step 2: minimum spanning tree
step 3: roads in hackerLand

 Blogs to read:
1.
https://en.wikipedia.org/wiki/Minimum_spanning_tree

2.
http://www.ics.uci.edu/~eppstein/161/960206.html

Work on union find algorithm first:  (step 1)
July 21, 2016

1. Union find algorithm - detect cycle

http://www.geeksforgeeks.org/union-find/

2. Union by rank and path compression

http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

Then, work on minimum spanning tree algorithm: (step II)

3.
http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

4.
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/


And then, study 10 code submission scoring 60/60 in Java, C++, C#. Practice one by one. (step III)

A better way to learn an algorithm - minimum spanning tree - work on a concrete example, make it fun learning experience.

1. Java implementation:
https://gist.github.com/jianminchen/20775a7ac1eeb83fa141e92633ea7d78

2. C++ 14
https://gist.github.com/jianminchen/28b5c3bf191a27250b67ce4e7656166b

3. C#
https://gist.github.com/jianminchen/7a21dfe2a62f1bcf4bc305480ef2f51e

4. C#
https://gist.github.com/jianminchen/8a15be7b83770d22647f34371fb48a97

5. C++
https://gist.github.com/jianminchen/5a3e680b86d2c5ffc0f090f29f074089


6. C++
https://gist.github.com/jianminchen/dcac67099aa7ddcb4497565f0732fe5e

7. C++
https://gist.github.com/jianminchen/10983fdcbbe15fef37bd73a60fe87430

8.

9.

10.

Follow up after 8 months

March 9, 2017
Read the tutotial first. And then write a C# solution, post a question on code review.

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

HackerRank: Even Tree (V) C# solution - use queue to help counting spanning tree's node

April 23, 2016

  Problem statement:

https://www.hackerrank.com/challenges/even-tree

C# solutions to study:

Code to study: 

 written by an engineer in Microsoft
https://gist.github.com/jianminchen/5c6b6cb4de9c4a2faf6237b7ac331a41

Julia modified the C# code to use DFS, spanning tree's node count, but still got the run time error/ wrong answer. 

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

Later, find out what is wrong. ( Probably, here is the reason:
The edge is directed. 
Do not duplicate the edge. 
For example, 2 1, just 2->1, do not add 1->2; 
but 
vertex[1].add(2), 
vertex[2].add(1), 
edge just add Tuple(2,1) )

Now, write exactly same code using study code, and see what I can learn.

The following code passes all the test cases.
https://gist.github.com/jianminchen/0e40bb76011e60f8aaf4683ed9c9c3d6

Julia's comment:

The edge is directed. Do not duplicate the edge and save two copy of the edge. But, vertex list is added for both vertexes of one edge.

Follow up - on April 24, 2016 8:40pm
Read Graph Toplogical Sorting:
http://www.geeksforgeeks.org/topological-sorting/

Follow up - on April 30, 2016 11:52pm
Read graph reprenstation
Use Adjacency Matrices
Use Adjacency Lists
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Notes from the blog:
How much space do adjacency lists take? We have $|V|$ lists, and although each list could have as many as $|V|-1$ vertices, in total the adjacency lists for an undirected graph contain $2|E|$ elements. Why $2|E|$? Each edge $(i,j)$appears exactly twice in the adjacency lists, once in $i$'s list and once in $j$'s list, and there are $|E|$ edges. For a directed graph, the adjacency lists contain a total of $|E|$ elements, one element per directed edge.

HackerRank: Even Tree - Graph Problem (I) - Just thinking

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

Motivation to work on graph problem:
1. There are over 10,000 submission on this problem, definitely, Julia likes to give it a try.

Statistics:
1:20 - 2:30pm  more than 1 hour wild thinking.

Think about the graph problem, before Julia writes any code, she think about how the problem is developed:

1. Have to remove as many edges from the tree as possible; <- kind of greedy algorithm
2. Each connected component of the forest should contain an even number of vertices.
<- Otherwise, odd number, 1 node itself, cannot be called forest; at least, 3.
3. Think about the how to remove one edge:
both ends should be ok; if one end only has one edge, then, no for removing the edge.
so, the node checks its edge count:
= 0 <- not possible - > "even number of vertices"
= 1 <- impossible
= 2 <- possible, can keep one, remove one

But think about forest with even number 2, 4,
for number 2, only one case:  3 connects to 4 in the test case
for number 4, only one case: one node in the center, all other 3 are connected to the same one.
for number 6, only one case: one node in the center, all other 5 are connected to the same one;
otherwise, one node connects to other 4 nodes, the 6th one will connect to the one of the node (other 4 nodes), then, it can be break into 2 and 4.

So, it should be two checking:
1. if the node only has one edge, keep it; do nothing;
2. if the node has more than one edge, remove all edges with more than 1 count.


Add comment on 10:00pm on April 23, 2016
1. Julia, you took distributed system in Florida Atlantic University around 2001, talking about spanning tree, ad hoc routing protocol; one thing is about spanning tree. Use DFS, and then, discuss spanning tree; if the root node's  child has a tree with even length, then, edge can be removed.

Find if a Directed Acyclic Graph has a cycle.

April 22, 2016

Find if a Directed Acyclic Graph has a cycle. Use DFS with coloring to find if cycle exists.

Given a directed graph of 10 cities, each of which may or may not be connected to each other, represented by an adjacency list, write an algorithm to find if there is a write from a city that eventually cycles back to the same city. What is the time complexity of your algorithm? You may use reasonable extra storage, or modify the structure of the graph node class.

Question and Answers:

Julia, read a few blogs, and then quickly go over first time. 30 minutes:
1. https://www.quora.com/How-can-DFS-and-BFS-be-used-to-find-out-if-there-are-cycles-in-a-graph

2. http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
Take notes here:
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. 

In other words, Julia, using DFS, to detect the cycle; 

DFS for a connected graph produces a tree; So, from graph -> DFS -> Tree; 

Then, work on Tree, to see if there is a back edge present in the tree; 

What is back edge? How to track? ancestor node in a stack - using array. 

Question and Answer: 

Walk through the code, and add the comment: 

https://gist.github.com/jianminchen/2eea7cc7cca69f296fc105c3fc3faafa

Read another blog:
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Read another blog from HackerRank:
https://www.hackerrank.com/topics/topological-sorting

Actionable item:

Work on HackerRank graph problem today:
https://www.hackerrank.com/challenges/even-tree

And then, study as many as possible solution about this graph problem. Get ideas how people are talented on graph problem solving.