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.
No comments:
Post a Comment