New habit to share practice on Leetcode discuss

August 11, 2018

Introduction

It takes a village to raise a child.

It is time for me to build a good habit to share on Leetcode discuss.

One thing I can do is to share all my practice with leetcode discuss. I think that it is smart to share with others on Leetcode discuss, specially as a C# programmer. Since I learn so many things from other's ideas and also C# code, it is also interesting to see how I join the community and have some interaction with others.

My two weeks drill - 40 algorithm practice 

It was so exciting two weeks. It is the first time for me to write 40 algorithm on leetcode.com and submitted each algorithm at least once from July 10 to July 31.

I put all my practice in github folder. Here is the link.

My sharing 

I like to spend time to share my practice on Leetcode discuss.

Leetcode 684

Here is my sharing on Leetcode 684 using union-find algorithm implemented using array.

Here is my sharing on Leetcode 684 using disjoint set concept based on Dictionary<int, HashSet<int>>.

Leetcode 687

Here is my sharing on the algorithm.
Here is my sharing on the practice failed to pass all test cases.

Leetcode 684: redundant connection - union find using array

July 22, 2018

Introduction

It is a medium level algorithm related to graph, and it can be solved using union find algorithm. The array can be used to store each node's parent node. I practiced a few times in the past, and this is the first time I wrote one and it passes the online judge.

My practice

Here is the C# code. I just copied the code from Java code in discussion panel. I may have issues when I write one by myself.

Leetcode 684: redundant connection

July 21, 2018

Introduction

It is a medium level algorithm called redundant connection. It can be solved using disjoint set data structure. I came cross the algorithm and was introduced through a mock interview more than six months ago. But I have not submitted any code on Leetcode online judge yet.

It is perfect time for me to write the code for the algorithm this Saturday.

My first practice 

Now it is 11:12 PM. I spent over 60 minutes and worked with online judge, and then wrote the code to pass all test cases.

I finally understood that the code is not easy to write using disjoint set data structure. I did a lot of learning through the those 60 minutes .

Here is C# code.

Second practice 

I read the discussion panel and one of ideas is to write union find algorithm, it takes less than 20 lines of code. I should be able to finish it in less than 20 minutes.

Leetcode 684: redundant connection

January 20, 2018

Introduction

One of ways to learn the algorithm is to ask the peer to solve the algorithm after mock interview. I met a peer this morning 10:00 am mock interview. He is graduating from K.I.T. a university in German. He likes to apply Switzerland Google instead of German one.

Algorithm problem solving

The peer came out the idea of the algorithm Kruskal's algorithm. And he also talked about minimum spanning tree. How does the edge joins the union by determining if the node is belonging to the union or not. If both of nodes of edge is in the same union, then the extra edge is found.

I asked him what is last time he worked on the Kruskal's algorithm recently. He said that he did not work on. But he worked on video project, cycle detection, filter, or canvas, video, use interface, when the video start time clip something related to the algorithm.

Aha, how do you compete with some one with super talent, and also hands on with projects outside the university, job?

And also the peer is super calm when he worked on the algorithm. He said that let me think about 1 to 2 minutes. And then at last, I asked him if I gave him the hint, he said no.

Leetcode 684: redudant connection

January 17, 2018

Introduction

It is the second time to meet the peer again in less than one week. Julia chose to give a medium level algorithm for peer to solve, Leetcode 684: redudant connection.

Discussion

Here is the transcript for the discussion.

Highlights of good things in discussion

Peer did:

1. First the peer came out to check if the graph has a cycle

2. Second the peer drew a more complicated tree, and then try to add one edge to make it a cycle

3. Third the peer write down a list of graph algorithm he worked before.



I try not to give out hint explicitly. So what I talk is about the example a tree drawed by the peer how node 1 is connected to node 7.

What is the connected meaning for us? The nodes are connected.

Also, I added one more graph algorithm called Kruskal algorithm, and then share the wiki page for the algorithm. I talked about the algorithm for minimum spanning tree using disjoint set data structure. And then I asked if the peer knew the data structure before.

I explained the data structure, what is for, why we need this data structure. Since the path from one node to other node is not needed, all we care about is if two nodes are connected. We do not need to search a path from one node to other node.

At last, I tried to give the explanation how to solve it in less than five minutes.


Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3         
 

Julia's explantion:


At the beginning, each node has its own set.
{1}, {2}, {3}, {4}, {5}.

[1,2] first edge is to connect 1 to 2, so {2} likes to join {1].


{1} <- {2}, {3}, {4}, {5}.

we have {1, 2}, {3}, {4}, {5}.

[2,3] second edge is to connect 2 to 3, 2 is not the set, but 3 is not in the set.


{1, 2} <- {3}, {4}, {5}
we have {1, 2, 3}, {4}, {5}

[3,4] third edge is to connect 3 to 4, 3 is in the set, but 4 is not in the set.

{1, 2, 3} <-{4}, {5}
we have {1, 2, 3, 4}, {5}

[1, 4] fourth edge is to connect 1 to 4, 1 is in the set, and 4 is also in the set. Then we know that node 1 and node 4 are connected, but direct connected edge 1 to 4 is to be added. Then edge [1, 4] is to form a cycle.

Leetcode 684: redundant connection

January 8, 2018

Introduction

It is another 10:00 PM mock interview. I asked the peer to give me another algorithm for interview, and he gave me the algorithm Leetcode 684.

Algorithm analysis

It is very good discussion between two peers. I shared the transcript here.

Here are the search results of union find practice in my past 12 months. I have practiced over 6 times union-find algorithm on Hackerrank.

Mock interview

Mock interview can be such a good activity, I thought about hiring a tutor met on mock platform, and then sent messages and talked to a few Chinese graduate student met on mock platform, none of them showed the interest. I know that I am out of date on this tutoring idea.

So I just go for the mock interview, if I meet a strong talented peer, just ask the peer to give me a tough algorithm to work on. The peer chose this one and it is the medium level. After the mock interview, I went to bathroom and looked at mirror, I almost cried since I felt that a drop of tear came out. Life is tough, mock interview is tougher than hackerrank contests. You have to push yourself to understand the algorithm, ask good questions, and then argue to myself to define the problem related to the given example, solve a well-defined simple problem. This algorithm can be solved with the experience of the union find algorithm. I do have over 10 times to work on the union find algorithm last 12 months by tracking coding blog, I played contest, asked code review called value of friendship, and practiced to write C# code, but I still miss the important part, solve the problem and present to the peer.

In my mock interview, I read the problem statement loud, 2 or 3 times, in order to understand the requirement, and then I told the peer that the graph has a cycle, we have to determine if there is a cycle. Usually the depth first search can be conducted to explore the graph.

We can go over any node and then start from it to do depth first search and determine if there is a cycle. One thing is to go back to the root node.

After 10 -15 minutes discussion, I told the peer that depth first search may not be necessary, I saw that the algorithm can be solved just using hashset or hashmap.

My personality

Definitely I have some personality, and then I have to figure out what to do with it and make most from own personality. One thing I noticed is the pressure from the peer. Usually the programmer working in silicon valley has more pressure, the peer may prepare onsite interview of tier 1 companies. It is hard to be the peer and relax all the time.

One thing I like to do is to review the Chinese blog about union find algorithm, and write down notes, and write an English version blog. I really find the blog author is such a good writer and work hard to present nice and rich graph to explain the algorithm.

I could not tell the quick find and union find difference right away. And also my mock interview algorithm does not require me to work on edges in detail, just need to check if it is in the graph or not. I tight the constraints to make my problem hard to solve.

Here is the blog about union find algorithm.

Quora post

The things to work on from a facebook recruiter quora.com answer. The link is here.

Follow up 

March 14, 2018

Plan to read disjoint-set data structure wiki article.