Hackerrank RookieRank 2 - prefix neigbhors (II)

Feb. 12, 2017

Problem statement

After the contest, Julia likes to study a few of solutions in C#, Java and other languages.

Code study of submissions

C# code

C# code.

Have some difficulty to understand the algorithm behind Index.Add method. Need to figure out later. Add some test cases to C# code, debug and understand the code one line by one line.

Study a few things about C# coding style, pascal case, set, get, and then using GroupBy, OrderBy, Aggregate, Stack, HashSet, Dictionary.

Second Study 

C# code study II

C# code is here. 

Third Study 

Java implementation

Problems

The most readable code is here with trie implementation. Julia chose one solution from near 100 solutions, this one is easy to follow. Will rewrite the C# solution based on this Java implementation.

Actionable Items

1. Instead of studying other people's code, Julia decided to look into test case 11 and figured out why her submission failed the test case. 

2. Read editorial notes from hackerrank, understand the idea, google search them:

This problem can be solved using Trie and DP. Create a trie from the given set of strings. Find the prefix neighbor of each string. Now create a graph such that each string is a node and there exist a bidirectional edge between two nodes only if they are prefix neighbors. Now find the maximum weighted independent set.

Statistics

Difficulty: Medium

Time Complexity:

O(N*max_length_of_string)

Required Knowledge: Trie

Publish Date: Mar 25 2016

Read the wiki article - Independent set ( graph theory)

GeeksforGeek problem - Largest independent set problem. 

3. Julia did not know the importance of problem solving in the contest and after the contest from Feb. 11 - 13, 2017. She tried to understand the other people's submission after the contest, and she had difficult time. She needs to understand the algorithm first, just follows the notes: find the maximum weighted independent set

4. Spent over 2 hours to rewrite the C# code, and post a question on stackexchange.com.  

Problem solving - community help

Feb. 25, 2017 5:27pm

With the help from Peter Taylor through his code view, Julia learned so much about the problem solving skills. She answered code reviews one by one, and then felt so comfortable with the algorithm problem solving. The code review experience is top-rated performance. 

Share some comments here:

Advice #6, KISS, why? what is wrong to insert them all into one trie? This is a good question. I tried to use the above code, but use one trie instead of going through A to Z one by one, run the code on hackerrank, error from test case 6 to 19; And then, I tried not to sort by the length of string, error from test case 6 to 19. – Jianmin Chen Feb 15 at 5:06   

Very good review, I did spend over a few hours in the contest and also a few hours after the contest. I like the last review "KISS, why?" most, remind me 5 whys for root cause analysis. Bravo! – Jianmin Chen Feb 15 at 5:11  

Hackerrank RookieRank 2 - prefix neighbors (I)

Feb. 12, 2017

Problem statement

Julia spent a day to work on the algorithm in the contest, Feb. 11, 2017. She reviewed her previous practice on trie, and then solved the algorithm to gain 14 out of maximum 50 points.

Her C# code is to create a trie to go over all strings, and then set each string to an array with size 11. Since the string's length is less and equal to 11, go over each length from 11 to 1, and then add those nodes to selected subset, set prefix neighbor node to exclude.

Actionable Items:

In the contest, Feb. 11, 2017, Julia spent over 3 hours to study the algorithm, over 2 hours to work on her trie implementation C# code in Sept. 7, 2016, make it more readable.

And then, Julia also spent over 3 hours to work on C# code to solve prefix neighbor algorithm. This is the perfect practice Julia learned to solve. It is out of her comfortable zone, and then she started to think on her feet and figured out something working.

More concerns about time spent, Julia should spend time wisely.

Hackerrank Rookierank 2 contest

Feb. 11, 2017

Introduction

Julia got excited. She still has 20 hours to go, and she only needs to work on last algorithm with medium level. She likes to document her practice starting from 12:42pm, how does she do to study, research, and catch up, and make some points from maximum 50 points.

Let us review what she has done so far, compared to the top 1 ranking player.

Some facts to share:
1. The last algorithm can be implemented in 20 minutes by the top performer.
2. The KnightL on a Chessboard is implemented by the top performer in 34 minutes; Compared to the best one, Julia spent 160 minutes.

Practice in the contest

Julia likes to work on the algorithm Prefix Neighbors, try to make things simple as possible. She started from 12:25, and then spent 3 hours to work on the algorithm.

Progress report 

12:25 - 3:22pm - Feb. 11, 2017

Discussion about sorting strings, radix sorting is a good idea to try. More detail, I think that string sorting is using radix sorting. The test case 4 A ABC AC ACD is sorted by 26 O(N), N <= 11.

Passed first 10 test cases

Worked on the coding from 7:00pm - 12:00pm, and then fixed bugs until 2:26am. Gave up. Learn a ton of patience, develop some skills. 

Here is the comparison: 

Coding is like tennis sport

Julia likes to work hard on the algorithm problem solving. So, she plans to take a break 1 - 2 hours first and then continue to work on the algorithm. 

Have 30 minutes workout to relax first, 90 minutes shopping trip. Saturday is the fun day. 

Try to remember the whole paragraph: 
frustrating sport, 
no way around the hard work, 
embrace it, 
put int the hours to improve somethings, 
a lot of sacrifice and effort, 
sometimes little reward, 
but you have to know that, if you put in the right effort, the reward will come.