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.

Bonnie and Cylde - week of code 33

June 16, 2017

Introduction

It is the expert level algorithm and Julia likes to work on the algorithm. 

Expert Level

Julia chooses to work on the expert level algorithm, Bonnie and Cylde. She chooses to study graph algorithm for a few hours, and then tries to find a solution. 

First, she reads the topcoder graph blogs. Blog link is here. 

Next, she will search all graph algorithm in Leetcode marking hard level, she will quickly go over 5 - 10 of them. 

Third, undirected graph lecture notes - link is here. 

Fourth, detect cycle in directed graph, link is here. Detect cycle in undirected graph, link is here. 

Fifth step, go over graph algorithms on geeksforgeeks.org website. The link is here. 

One of graph algorithms, "Print all paths from a given source to a destination". The blog is here. 

"Competitive Programming" authored by - Graph

Union find algorithm on hackerearth - link is here. 

Progress Report

Now it is 8:44 am Saturday morning, Julia has to review her submission result. The interesting part of expert level algorithm is that Julia has to go over a lot of content about graph, a lot of reading, and then she decided to use one of algorithms to solve the problem. 

The idea to solve the problem was original wrong, and then she made a minor change to make sense on second sample test case. 

The another interesting fact to write code for expert level algorithm is that Julia does not have a lot of code to write. The idea is quiet simple, but a few test cases timeout. It is hard to find the right idea. Julia has to do time analysis for the algorithm and see which one can survive the time limit. 

Follow up after the contest

Julia submitted the code in the contest and score 25% of maximum score, 22.86 out of maximum score 80. Julia just used union find algorithm and then used another idea to apply union find second time to exclude one of two source nodes. Code is here. 

Culture Conference - Rookie 3 contest

May 7, 2017

Problem statement: Culture Conference

Introduction

It is very interesting contest experience. Julia did not write a lot of code in Rookie contest, first she decided to review Union find algorithm, studied one of C# solution first. But in less than one hour, she used the algorithm to score a full score 20 on a medium algorithm - Maximum tourism. And then she started to work on the hard algorithm called Culture conference with maximum score 55. Julia also did not have time to write code, she was busy with tennis sport 2 hours, and one hour mocking interview around 8 pm. So she decided to use same algorithm Union Find to calculate the minimum number to attend the conference, a minimum dominating set, she scored 3.5 and then made some improvement to score 5.5.

One algorithm Union find helped her to score more than 30 point on two algorithms in the contest.

Here is her submission report on the algorithm.

Code review 

C# code is here.

The function Julia worked on in the contest from line 248 to 269 is here. She tried to adjust the maximum saved people by thinking about one node with more than one child, how many can be saved to let the parent node to go to culture conference, that is children.Count - 1.

Code snippet is here:

Follow up 

May 5, 2017

After the contest, study code written in Cpp file. Code is here.

Review code and then write a C# code. Code is here.

Performance Talk - 5 points to 55 points

10:37pm May 5/2017

Performance on this algorithm is based on the points I got. I got 5 points,  5 / 55 points, it is almost 10%. It is the hard algorithm, but the solution is not that hard to figure out.

Julia has to look into the performance issue in the contest Rookie 3, and then write down some tips to improve. Simple and practical tips.

May 9, 2017

Download test case 2, and then test the C# code in the contest using test case 2, and then modified the code. It took hours to fix the issues related to union find algorithm. Code is here, still need more work. Union Find algorithm implemented only keeps every node's parent node to the disjoint set's root node. Its director supervisor is replaced with the root node. No way to get the correct answer.

May 10, 2017
Leave union find algorithm alone, add some data structure to check each node with subordinates and supervisor, similar to the study code. Therefore the algorithm can only handle those edges with burnout node with its parent, and also figure out how many people go to conference.

It is a good practice to add something to Union Find algorithm, therefore learn to solve a problem and also get chance to know more about Union Find algorithm.

Actionable Items:

Study lead board of Rookie3

Read the math Ph.D. student - a good programming on Rookie 3 - Kevin Vissuet is the profile. Resume is here to take a look.

Aaron Albin - Amazon employee

Kruskal's algorithm workout (I)

April 14, 2017

Introduction

It is a good workout to work on Kruskal's algorithm based on the geeksforgeeks.com article.  Julia likes to spend 2 - 3 hours to play with Kruskal's algorithm using C#. 

Later on, she likes to work on the algorithm on Hackerrank week code 31 - Spanning Tree Fraction. 

Kruskal's algorithm

Greedy algorithm to get minimum spanning tree using Kruskal's algorithm. 

Spent near 2 hours to work on the C# code. C# code is here. 

Union find tutorial

Oct. 18, 2016

Plan to spend 2+ hours to work on the union find tutorial.  

Union find
http://contest.cs.cmu.edu/295/tutorials/union-find.txt

Previous study on union-find algorithms:

1. http://juliachencoding.blogspot.ca/2016/07/union-find-algorithm-undirected-graph.html

2. http://juliachencoding.blogspot.ca/2016/07/hackerrank-world-codesprint-4-roads-in.html


or search "union find" through "search this blog" feature.

Union-Find Algorithm - an undirected graph algorithm

July 23, 2016

Julia just misses the fun time to play with HackerRank world codesprint #4 in June 2016, in order to prepare next HackerRank code sprint on July 24, 2016, she has to review undirected graph algorithm - Union-Find algorithm. She likes the challenge, but she has to discipline herself always work on the simplest algorithm first. Aim small target first, baby step; avoid dealing with complicate function in the design at the beginning.

Write her own C# code: 

http://www.geeksforgeeks.org/union-find/

August 3, 2016
1. Go over Union-find algorithm lecture notes:
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

2. 
http://blog.csdn.net/dm_vincent/article/details/7655764
http://blog.csdn.net/dm_vincent/article/details/7769159

HackerRank: World codesprint #4 - Roads in HackerLand - II - code study

July 20, 2016

First blog on this algorithm:

HackerRank: World codesprint #4 - Roads in HackerLand

http://juliachencoding.blogspot.ca/2016/06/hackerrank-world-codesprint-4-roads-in.html

Come back to work on this problem. Study editorial solution provided by HackerRank, and then,
review union find, minimum spanning tree algorithm with code first:

3 steps:
step 1: union find algorithm
step 2: minimum spanning tree
step 3: roads in hackerLand

 Blogs to read:
1.
https://en.wikipedia.org/wiki/Minimum_spanning_tree

2.
http://www.ics.uci.edu/~eppstein/161/960206.html

Work on union find algorithm first:  (step 1)
July 21, 2016

1. Union find algorithm - detect cycle

http://www.geeksforgeeks.org/union-find/

2. Union by rank and path compression

http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

Then, work on minimum spanning tree algorithm: (step II)

3.
http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

4.
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/


And then, study 10 code submission scoring 60/60 in Java, C++, C#. Practice one by one. (step III)

A better way to learn an algorithm - minimum spanning tree - work on a concrete example, make it fun learning experience.

1. Java implementation:
https://gist.github.com/jianminchen/20775a7ac1eeb83fa141e92633ea7d78

2. C++ 14
https://gist.github.com/jianminchen/28b5c3bf191a27250b67ce4e7656166b

3. C#
https://gist.github.com/jianminchen/7a21dfe2a62f1bcf4bc305480ef2f51e

4. C#
https://gist.github.com/jianminchen/8a15be7b83770d22647f34371fb48a97

5. C++
https://gist.github.com/jianminchen/5a3e680b86d2c5ffc0f090f29f074089


6. C++
https://gist.github.com/jianminchen/dcac67099aa7ddcb4497565f0732fe5e

7. C++
https://gist.github.com/jianminchen/10983fdcbbe15fef37bd73a60fe87430

8.

9.

10.

Follow up after 8 months

March 9, 2017
Read the tutotial first. And then write a C# solution, post a question on code review.