Path Matching - week of code 33

June 17, 2017

Problem statement

Research and study plan 

It is the expert level algorithm. As a hackerrank player, Julia is still learning how to solve the expert level algorithm partially. What she likes to do is to dedicate a few hours, think about ideas, study related topic, and most important is to go over related algorithms in Leetcode, topcoder, hackerearth, and read some lecture notes.

After a few hours study, Julia starts to come out some idea to solve basic sample test cases first, leave timeout and performance issues as is until she comes out the great idea to solve the issue.

1. Leetcode 44 - wildcard matching - 20 - 30 minutes research and study, documented in the blog:
wildcard matching.

2. Review string search algorithm KMP, Rabin algorithm on topcoder. Link is here.

3. Review KMP and other string search algorithm on Julia's coding blog as well. Now it is 10:11am.

4. Review "the hidden message" algorithm on hackerrank contest. The blog is here.

5. Leetcode: Graph Valid Tree - the coding blog of grandyang is here.

Time is 9:07 pm, June 17, 2017
It is hard to figure out the idea to solve the path between two nodes. Julia likes to study some good algorithm.

She googled n nodes n - 1 edges meaning - no cycle in the graph, a tree?

6. Read lecture notes about union find data structure - lecture notes by Princeton is here. Now it is 9:55 pm.

Follow up after the contest

The code submitted in the contest is here. Score 0.47 out of maximum score 100.

Plan to study the Java code written by Salmur - score 100, link is here.

Plan to study the discussion provided by one of players. Link is here.

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. 

Hackerrank week of code 33

June 15, 2017

Week of code 33 on Hackerrank

It is so exciting to play hackerrank week of code 33. Julia likes to check her progress through the contest.

Here is the progress report on June 15, 2017, 10:08 pm.

Now it is 10:59 pm, Julia scored 60 maximum score on the algorithm "Palindromic table". Her ranking moved up to 431. 

There are 2 more expert level algorithms to go for the week of code 33. Now it is 11:15 pm, Julia checked the leader board in Canada. Here is the progress report:

Now it is Sunday, June 18, 2017, 8:15 am. Julia likes to ensure that she can get a gold medal, stay in the top 4%. So she plans to do more study and write some code for the algorithm. 

Here is the comparison to one of top players.