From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one.
2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会.
She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going.
Hard work beats talent when talent fails to work hard.
Showing posts with label minimum spanning tree. Show all posts
Showing posts with label minimum spanning tree. Show all posts
It is my favorite
algorithm called union find algorithm. It can be Kruskal algorithm. I did have
a lot of practice recently. It is so good to come back to work on the algorithm
again.
Algorithm study
Plan to review the algorithm by studying the blog.
Please use the code for Union find algorithm Island count II for the template, and apply the same technique on this algorithm. Here is the link.
Quick union algorithm
I like to review the practice on quick union algorithm. Here is the link:
Quick find algorithm
I reviewed the quick find algorithm more than one month ago. Here is the link:
A mock interview discussion
I remembered that the peer gave me the question and test my disjoint set data structure. I chose to use depth first search and then had some idea to use hashset only data structure. Here is the discussion.
It is a minimum spanning tree algorithm. But there is additional work to remove max cost edge in the tree. Julia started to work on the algorithm last 30 minutes, she spent 10 minutes to go over the problem statement and then figured out the whole requirement. She only had 20 minutes, she fumbled, and she looked at the leaderboard, checked players from Google's performance, she likes to write a simple code to score partial points to make her a medal player.
Too short time, it just reminds her that she needs to work on and review what she works on. She just needs to look into past work and then find a solution to score the points.
An algorithm makes her Sunday morning so challenging.
Algorithm
Previous practice on Kruskal's algorithm is here. Julia spent wrong on the name, she spelled Krusal. In order to pay respect the scientist, Julia decided to review his wiki page and get more detail on his work.
Read wiki page as well. Plan to spend one hour to read this Sunday morning.
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
John lives in HackerLand, a country with cities and bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., raised to some exponent). It's possible for John to reach any city from any other city.
Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.
Max Score: 60
Difficulty: Moderate
Submissions: 1319
The problem is a graph problem, so here is her analysis:
Spent over 1 hour to try to figure out the graph problem, what is my best bet to solve the problem.
Find simple problems to work on first:
Algorithm 1. Any two directed connected nodes, find shortest distance:
distance (n1, n3) = 10, go through node 1 -> node 2 -> node 3, instead of directly connected edge - 32
2. Any two nodes in the graph, find the shortest distance:
based on graph in the step 3, find a route from one node to another node, using BFS or DFS, for example, node 1 to node 4, node 1 -> node 2 -> node 4.
min distance (node1, node4)
Spend a lot of time here to try to design the algorithm:
1. using DFS/recursive/memorization solution:
evaluate the solution, problems in the design cannot be solved:
problem and its subproblems are overlapping.
min distance (node2, node4)
Not working
2. using BFS/queue, the design concerns:
1. Avoid loops
2. Stop early -
3. using DFS/stack, the design concerns:
Also, each edge's length is power of 2, different length.
1. Step 1-> Step 2:
Try to work on this graph, for each directed connected graph, use BFS algorithm, try to find a shorter route. For example,
So, the edge(1, 3) can be marked removable, this direct route will never be travelled.
Work out the above case:
start from node 1, add node 1 to the queue, and then, go through the queue, remove node from queue, add all neighbors to the queue, if it is not visited previously, and if it is the node 3, then only allow twice , as long as the sum is less than edge(1,3) = 32, continue; Make a single linked list, n2.prev = n1, n3.prev = n2,
2. To work on graph in step 3,
For each node in the graph, for example, n1, using DFS or BFS to find a route to node j, j<>i.
So, with those removed edges, only one route will be found through any two nodes, i<>j.
To be continued.
Follow up
April 26, 2017
Need to write down C# version to solve this minimum spanning tree algorithm.
