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: 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.

Monk missing home

January 10, 2018

Introduction


It is hard to manage myself to learn disjoint set. I did read the tutorial over 6 months ago, but I failed to perform in Leetcode 684: redundant connection on January 8, 2018. One of drills I came out is to work on hard level algorithm on hackerearth this time, so I learn more through the practice.

Plan to work on the algorithm called Monk missing home.

Maximum Disjoint Subtree Product - World codesprint 10

April 29, 2017

Introduction

It is a wise decision to spend time for each algorithm in the contest. Even Julia did not make any points last few hours, she found out that it is better to write a brute force solution even scoring 0, or write a blog about the algorithm.

The maximum disjoint subtree product algorithm should be a DFS/ BFS tree problem. Julia had some idea to solve the problem, but she was not sure how simple the code should be.

The problem statement is here. Just work on the most simple test case, and then write some code first.

Plan to do 60 minutes workout on the algorithm. 3:03pm - 4:03pm.

Code preparation 

Read one of players resume, and go over all the players in united states scoring 60 on the algorithm. 3:13 pm, study those players and get myself ready to think about a solution and start to write down some code. 

4:00pm now - spent 20 minutes to go over those 24 people scoring 60 maximum points, and I knew that those are very experienced ones, Julia spent time to loo at those who scored 3 points, 6 points, to 30 points. Those are players who are working hard as well.

Go back to study on topcoder webpage after googling disjoint set, make the algorithm general. How to approach? Article is here. 

Finished 15 minutes to read the disjoint set article first. Time is checked, 4:15pm.

Disjoint-set Data structure - topcoder tutorial

Read the article - link is here, and take some notes. 

Disjoint sets, dynamic disjoint sets,
Define two sets are disjoint - intersection is null
representative - Every disjoint set contains a representative

It is assumed that the representative of each group is the person with the biggest index in the article.
Every one has its own group
-> the group containing 1 and the group with 2 will become one group.
-> the representative of first group will become 2.

How to check if two persons are in the same group? Check the representative.

Define some operations:
Create-Set
Merge-Set
Find-set

Implementation with linked lists

Each element will be in a linked list and will contain to the next element in the set and another point to the representative of the set.

Read the graph representing the problem, catch up more later.

Read how to implement the Merge-Set(x,y) operations.

a weighted-union heuristic - complexity O(M + NlogN)
where M is the number of operations (Find-sets, Merge-sets, Create-sets), N is the number of operations Create-Sets.

Two heuristics -

Union by rank
Path compression

Time is checked again, 4:53pm.

Move on to next topic

Disjoint Set questions on Hackerrank

Link is here.

Disjoint Set tutorial on hackerearth 

The article link is here.

Being a hacker 

Wrote a brute force solution to work out on sample test case, but the code passed test case 1, failed 2, 3, and time out everywhere. Score 0. Time checked, 10:53pm.

Can hackerrank give me 0.001 points? I just need 0.0001 points.

Is that possible to give 0.25 points for passing test case 1? I wrote a brute force solution just to try to advance my ranking. My points are 36 points, ranking from 767 - 1307 all scoring 36 points. Never work so hard to advance 0.25 point, failed this time.
Here is the comment link. 

Follow up 

Code written in the contest is here. 

Study one of C# submission code. C# study code is here with sample test case. 
Continue to code review the algorithm, prepare to give a code review on stackexchange.com, here is the C# code.