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.

Leetcode 269: Alien Dictionary

March 11, 2018

Introduction

It is time for me to review graph algorithm called topological sort. Here are a few blogs I documented my practice more than 2 years ago, in 2016.

Course schedule, here is the blog.
Alien dictionary, here is the blog one; here is the second blog.

Algorithm practice

It is so interesting to read the blog I wrote more than 2 years ago. I like to laugh about it, the writing style is kind of different, but I am so glad to know that I can trace what my thought process and learning process after 2 years. It is so sweet to read what I did write and draw. I felt so good to enjoy my own work, review the learning process again.

What I like to do is to write a C# version, and also find 3 ideas in discussion panel and write a C# version for each idea.

Also I like to post a question on code review website. I need to learn better this time.

Actionable Item

Plan to review the old algorithm related in Leetcode. Leetcode 133: clone graph, Course Schedule and course schedule II.


May 3, 2018

I had a mock interview with the friend. And he told me to work on the alien dictionary algorithm. I do not need to write the code, but please tell him how to work on the solution.

I remembered that I worked on the algorithm before, a few years ago. And then he asked me what kind of graph algorithm I can apply. I said that it may be topological sorting. It is a graph algorithm. But I do not remember too much detail any more.

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