Leetcode 269 - Alien Dictionary - Practice 2 more times

June 16, 2016

Try to find a small topic to start to do some research every day at least 20 minutes, and then build up more later on.

Today topic is about writing algorithm code - problem solving, 1st writing (study other's code and understand) vs 1st writing (with simple test case with a diagram, more focus, a small problem):

Here is the cycle Julia goes through for Leetcode 269 - Alien Dictionary:

Coding process ->
choose an algorithm to code ->
study 4 or 5 solution from over 10 solutions ->
cannot learn an algorithm just by reading, stop reading ->
write C# code based on one of them (Java, or C++) ->
add comment, make code readable, debugging ->
code works ->
wait 10 - 20 minutes ->
draw a diagram to work on a simple test case ->
rewrite the code 2nd time->
big difference, a new story to write - it takes close to one hour -> 
interesting experience. ->
3rd rewrite ->
document the difference 

First blog of Leetcode 269 Alien Dictionary:

http://juliachencoding.blogspot.ca/2016/06/leetcode-269-alien-dictionary.html

1st good writing in C#:
https://gist.github.com/jianminchen/85129ed50ce597f896b0f0c5a2fa5586

Afterwards, work out a simple test case, and then, write down the graph with detail data structure and data, write code based on the picture. New ideas come out naturally to improve:

1st writing focusing on the above diagram: C# implementation
https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733

3rd writing using C# code:
https://gist.github.com/jianminchen/8d4c1f601bae0ca7ef27e470dfe1e636

Highlight the differences 3rd time:
1. line 26, base case is updated: words.Length <= 1 instead of <1
2. Add comments what to find in the function alienOrder
    1. spell error topological -> topoligical
    2. add nodes variable as part of graph
3. getNodes function -
    look into string.ToList() -> List<char>
    study HashSet.UnionWith() input argument and its type IEnumerable<T>
4. rewrite graphSetup function tasks from line 62 - 79
    explain very clearly to find an edge if there is one;
   what to construct in the graph.
   add precondition for the function.
5. rewrite the function comment for topologicalSort
6. missing line 163 - 164, run time error - array access - out-of-index

statistics:
Time spent: 3rd practice - more than 40 minutes

Quick tip:
{"wrt", "wrf", "er", "ett", "rftt"}

first char, comparison (all five words)            =>  w -> e -> r
third char comparison (first two words - "wrt","wrf")          =>  t->f
second char comparison (third, fourth words -"er","ett") =>  r-> t

So, the order is "wertf"

Comparison:
alienOrder - two things noticed documented in comment.

3rd writing - take some time to look up HashSet.UnionWith argument type: IEnumerable<T>, good time to learn something here.

Practice to write down what to do, in order to write good code, also need to explain what to do first. Good writing right side! Bravo!

Find a bug, 2nd version, left side, no edge case: return; should be continue; line 89

https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733

Also, write down tasks before writing code, good habit to train to focus on tasks when writing.

Use node in neighbors to make code more readable.

One algorithm a time. Take your time to master an algorithm.

Everyone asks me what’s next. I’m here to stay, taking it one game at a time.#CreateYourMark pic.twitter.com/CzDq5CIGMA

— Angelique Kerber (@AngeliqueKerber) May 21, 2016

Leetcode 269: Alien Dictionary

June 15, 2016

Leetcode 269 Alien dictionary

Choose to work on a graph problem - using Topological Sorting:

Study C++ solution:
http://www.cnblogs.com/jcliBlogger/p/4758761.html

Discussion about the problem description:
https://leetcode.com/discuss/53997/the-description-is-wrong

Study C++ solution:

https://leetcode.com/discuss/54024/straightforward-c-solution?show=54024#q54024


Java solution to study:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/269.alien-dictionary.java

http://www.cnblogs.com/yrbbest/p/5023584.html

Julia worked on C# code:
https://gist.github.com/jianminchen/07546625d828f63e762ba03b463fe8aa
line 75, 76, after queue.peek() is called, need to call dequeue. (dead loop)

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

Add more comment, where to be careful, to avoid bugs:
https://gist.github.com/jianminchen/47f516b54686080c3a68bc8c3f1d04cb

More comment, variable name refactor:
https://gist.github.com/jianminchen/85129ed50ce597f896b0f0c5a2fa5586

Read blogs:
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

Comparison between 2 versions:
variable name change: graph -> dependencyList, more meaningful. The graph has nodes, dependency list, inDegree array.

Change function name: getCharSet -> getNodes

Love those comment, so helpful to get start to coding...

Left side first implementation:

for(int j=0; j < shortLength; j++)

{

...

break;

}

confusing, not very easy to follow. line 154 - line 176, 22 lines of code. The big scope to handle. 

Also, this for loop is nested loop, too many lines of code inside. 

Replacement of while loop is short, only 3 lines of code. 

graphSetup -> what we can tell here? ... later!

Question and answer:
1. Can you work on a simple example to explain the idea of your solution?

Here is the warm up for topological sorting using two strings {"wrt","wrf"}:

Review previous blog:

http://juliachencoding.blogspot.ca/2016/04/leetcode-208-course-schedule.html

Warmup practice:
statistics: 1 bug, more than 60 minute to write. Totally new program
https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733
a few changes to highlight:
1. line 24 - 26 add comment what to do about graph
2. line 49 - 65 motivation talk - help to design the function
    using the graph above {"wrt","wrf"}, help to write code
3. line 72 - 74 special case words length is 1
4. line 81 - line 85 use one pointer to slide forward <- more flat code
5. line 87 add comment - no edge -> very good comment
6. line 91 - 94 first writing with a bug - prev, curr, but prev twice

Here is the comparison file:
https://github.com/jianminchen/Leetcode_C-/blob/master/Leetcode269FirstAndSecondPractice.pdf

Statistics:
time spent: 3hours +

I don't feel fear when I am on court. That's where I feel at home #CreateYourMark #RG16 @adidastennis @adidasFR pic.twitter.com/ZVNcZvWZE0

— Kristina Mladenovic (@KikiMladenovic) May 20, 2016

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