Case study: Union find algorithm study code - ranking 176

April 4, 2019

Introduction

It is my study time to go over those union find algorithm from top ranking 100 to 200 in weekly contest 112 on Leetcode.com. I like to write a case study on my learning of player 176.

Case study

I chose to write a C# code based on player ranking 176. I wrote C# code but I found out the code could not pass online judge.

It is good thing since I can learn how to trouble shooting the problem. I could not pinpoint the bug, so I continued to study more about union find algorithm.

After more than one hour study, I found the bug. I submitted the code, here is my C# code.

I also learned how to write a path compression function using iterative solution. I learned from the website of lecture note.

Iterative way path compression

I also like to continue to learn.

Buggy code 

It took me more than one hour to find the bug. I spent time to write down each step of union, and then figure out why there are two trees in test case 1. One of reasons is that Parent member should be private, so that it can not be accessed directly, only available for function Find.

Rule No. 1
Only work on root of tree in union find. Connect one root as another root's child. Do not confuse the parent node with root node.

union find algorithm - 7th mock interview from the coach

May 28, 2018

Introduction

It is my most favorite algorithm called union find algorithm. My coach asked me to solve the algorithm to find maximum group. We had discussion around 100 minutes. Through the discussion, the coach showed me how to do time complexity, and then we had good time to discuss a few topics. At last, I asked the coach to write two function, one is to quick find, one is to union.

Transcript

Here is the transcript of mock interview on May 27, 8:00 AM.

Follow up

I spent a few hours to review my past practice on this union find algorithm, and then I wrote C# code for review. Also I was asked to write a depth first search algorithm, and I will write one.

Number of Isalnds II

January 21, 2018

Introduction

It is the second time I heard the algorithm through mock interview conversation. Last December I could not find time to work on the algorithm. I just wrote one blog to leave for future. Today I like to study the blog written by Grandyang, and then write a C# code later on.

Algorithm analysis

Most of important is to write down study notes from the above algorithm blog. Try to understand the problem using the analysis.

Here is the note I wrote down to study the blog written in Chinese.

Here is the gist I created to study Leetcode discussion on the algorithm.

Here is the C# code I wrote based on the above Leetcode discussion in Java language.

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.

Union find lecture note study

January 9, 2018

Introduction

It is always best time in the day to read some algorithm lecture notes. I just wonder what is best thing to do celebration of new year 2018, maybe the lecture note of union find is good thing to start. There are around 49 pages, I like to write down some notes and put together a nice blog with some good understanding of the algorithm.

Lecture note

Here is the lecture note.

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.

Leetcode Number of Island II

Dec. 28, 2017

Plan to study the algorithm Leetcode Number of Island II.

Follow up

1/21/2018 3:19 PM
I like to follow up on this algorithm. I spent over 10 minutes to read the discussion about one solution. I like to put Java code into github and create a gist first, and then I will write a C# solution as well.

Also plan to study the algorithm blog written in Chinese, the blog link is here.

Leetcode 200: Number of Islands

Dec. 28, 2017

Introduction

Plan to study the algorithm Leetcode 200: Number of Islands. I got the advice to work on the algorithm from my mock interview peer on Dec. 27, 2017.

Union Find Algorithm - one hour workout

May 5, 2017

Introduction

It is a good idea to have my own union find C# class and also put some test cases together for future use.

Here is the article to talk about union find in details on hackerearth.com.

Here is the blog to document the study on the topic.

Here is the blog to document more than one hour study on union find algorithm in world codesprint 10 contest.

Union Find Coding

It is in incognito mode, Julia did not share any code because she played the Rookie3 contest.

Follow up 

May 7, 2017 9:27am

Julia spent hours to test the union find algorithm, and planned to apply the algorithm to solve one of Rookie3 contest algorithms. She just applied the test case in less than one hour and solved the algorithm on Rookie3, score 25 point very easily. She did not have chance to look into the detail of the algorithm. 

May 10, 2017

Code review C# solution, and C# code is here. 

The path compression is implemented in the above algorithm. Every node's parent node is set to the root node of tree.

Maximal tourism - rookieRank 3

May 5, 2017

Introduction

Problem statement is here. Plan to work on the problem.

Code study 

Follow up 

May 7, 2017 9:22 am

Code submission in the contest is here. Score fulls score. 

Julia did not write any code, she reviewed union find algorithm and tried to get some experience of union find C# code, she just used the algorithm to test her union find code as the second test case.