HackerRank - week code 28 - The value of friendship

January 14, 2017

The value of friendship - problem statement

In the contest

Read the discussion, and prepare to write some code.

Test case: 1 5 3 1 2 3 4 4 

What about 1 5 3 1 2 3 4 4 5 Would the answer be 16?

Discussion is here.

Test case - 16


One more discussion is here.

example:

Disjoint set

Review the content on wiki.

Julia spent a few hours to read discussion, and did some research to see how people in top-ranking of content discuss and share their experience. Anything she needs to catch up.

She studied the profile:

Another one shared the advice of using disjoint set, here is the comparison to his contest:

After the contest

Need to practice a few of them.
Study a few submissions in C#, first one is here.

Code review one of C# submission, and work on a test case - a graph with five nodes, 4 connected friendship,   1-2-3  4-5,   also 1 is friend of 3. 4 friendships, 1 - 2, 2 - 3, 1 - 3, 4 -5.

2+ hours study and debug, code review, continuously made improvements
C# code comparison:  Original is here, and Julia made a new one.

Highlights of change:
1. Change variable names - make it more meaningful.
2. Add one extra variable name in the class GraphNode.
3. Add one sample test case, and use the test case to help understand the code.
    Add comment for each function, help user to understand the algorithm.
                 

Status Report

Julia has to work on graph's algorithm in 2017, she understood the algorithm in the contest, but she did not have very strong confidence how to write a very clear, short, concise code in 1-2 hours. There are so many ideas in the submissions, a lot of them are with very short and clear, readable code.

Need to catch up and work hard on the algorithm.

Stackexchange.com code review is here.

Study leaderboard:
1. Eric Sheng
http://ericsheng.com/
printing ascending ascii code.
2. Computer faculty, facebook engineer - click here.
3. PH.D., click here.
4. engineer, coursera achievements, click here.
coursera certificate of algorithm? Look into later.
5. A lot of competition, SQL server program manager before, click here.
6. Look for intern, a lot of competition activities in programming, click here.
7. coursera course, master student, click here.
8. FSU financial math Ph.D., click here.
9. Banking industry experience, J2EE, click here.
10. Alibaba, click here.
11. ASU math phd., ranking around 400, click hackerrank, here.
12. A researcher, click here.
13. over 20 medals, graduate student, Microsoft, click here.
14. CA state programming contest, ranking around 500, HP engineer
15. undergraduate, google intern, ranking around 653,
16. rank 900 - a bachelor student - click here.

Continued Study:

1. More code review by Julia, Julia likes to find out code with good style, 22 C# submission with maximum score, all of players are in ranking top 500, Julia will have a good time learn graph algorithm this time.

Julia learns to write one by one.

Good variable names, click here.
DisjointSet class, click here.

One of code review, click here. (It took hours to rewrite, study first and then try to think about better way to represent.)

Code with unit test cases, study first (ID: yambe2002, ranking: 111/10432), link is here. Code review, link is here.

Julia learned a few things in S.O.L.I.D. principles through code review wiki post, and then she likes to do some code review using some of principles. Code is here.

Hackerrank week code 28 - Suffix Rotation

January 14, 2017

Introduction
Life is not easy to compete the week code on Hackerrank, now Julia's ranking is following behind around 2900 out of 9985 at 11:54am, 1/14/2016. In order to get into the top 25%, she has to continue to work on the problem solving. It will be a lot of fun, a lot of mistakes, and trial and errors.

Have some images to show the progress first, comparison to one in the ranking of 2000:

Comparison to one in the ranking of 1000:

The Great XOR

Julia just found out through the above graph, she had some issues with the algorithm The Great XOR. Spent 5 minutes to look into detail. She did not have any test case failure when she worked on the algorithm, the hackerrank has issues to run so slow, only at the end of day, all test cases will be run. She lost almost 10 points on the algorithm.

Usually, Julia likes to focus on easy and medium level algorithms, now in order to get a bronze medal, she has to learn to work on hard, advanced and expert algorithms, and try to do some research, read the discussion, and come out a simple idea to make extra points.

Lucky Number Eight
Julia did remember the algorithm was scored 18 instead of 10.80, now there are over 5 test case timeout. Six more test cases are added and she failed all of test cases because of timeout.

Comparison to rank 515

Instead, Julia can choose to walk around the outdoor, and get some physical exercise done first.


Study, research, code 

Suffix Rotation - problem statement

1. Work on a test case:
string abc, there are 6 variations:
abc-> no rotation, answer is 0
acb-> abc,  1 rotation
bac->acb->abc,   2 rotations, second rotation starting from c
bca->cab->abc,  1 rotation, but circular rotation 2 times
cab->abc, 1 rotation
cba->bac->acb->abc, 2 rotations

2. Work on a test case with multiple instances of char:
string abcbb, what is difference?
abbbc,
if we use counting sort, we can determine the char by counting the number, and then calculate difference.
abbbc
c should be in position of 2, starting from index = 0, but actually it is in position of 4
rotation twice move 4 to 2, and also one of b is in position of 4, it should be in 2, also moved forward.

3. Work on a test case, abcdb,
so c should be in position 4, but it is in 2; 4 - 2 = 2, 1 rotation,

Try to use recursion solution to gain a few points first. And get some ideas about the issues.

Test Case: "cababc"

After more than 3 hours coding, at 10:13pm, Julia studied the discussion related to the test case, Julia found out that there are more than one solution, but need to find minimum move.

string cababc, using her naive solution, it will take 3 moves:
cababc ->
ababcc ->
aabccb ->
aabbcc

but the minimum move only needs 2 moves:
first 'a' is to use the second 'a' in the string "cababc", after first rotation, the string will be "abccab", and the second move is to use second b in the string "abccab", then final string "aabbcc".

How to get the minimum move? Use brute force, then calculate each option for any char from a to z.

Try to find something to think about:
cababc->   ababcc
                  abccab

From two strings to choose a small one, how to choose?
abccab  -> aabbcc
ababcc  -> aabccb

Google Search: suffix rotation minimum

ACM ICPC 2003 - the algorithm discussion is here.

One more reading is here.

Review Suffix Array and Longest Common Prefix

Study code review

Ashton and String Hackerrank

my favorite algorithm teacher - JS1

Actionable Items:

Work on the minimum value by simply comparison. Try to get at least 1 point first.

1. check into to document latest progress:
1/15/2017 11:05am
Using my code in C# to test the cases seen in the discussion - link is here.

test case 1: hackerrank - 6
test case 2: suffixrotation - 9

Using queue, and calculate all the possible selections. 

But my C# submission still scores 0, pass test case 0, and time out 1 and 2, and runtime error test case 3 on 1.97s. 

Rotation definition - misunderstanding 

2. Need to look into the rotation definition, see if it is making sense or not. 

Choose index bigger than prior move. 
but, at the index, perform circular rotation in either direction. 
So, work on the example, abcdefjghi, at index 6, with char j, can rotate clock wise or anti-clockwise. 

jghi -> anti-clockwise -> ijgh -> hijg ->..
jghi -> clockwise ->  ghij -> hijg ->..

So, work on the example: cababc
first work on index 0, work on second a, 
                                                      clockwise, abccab
                                                      anti-clockwise, abaccb
                                   work on first a, 
                                                      clockwise, ababca
                                                      anti-clockwise, accbab

and then, work on second char - index = 1, there are 4 choices. 

Because Julia's C# code has wrong answer, probably it is because of her rotation misunderstanding, missing two cases. 

Good workout and great learning 

Suffix Rotation C# practice - score 0, but perfect learning experience. Julia learns the importance to challenge herself to work on hard algorithm, come out the solution to work ok with sample test cases. She spent more than 5 hours to work on the problem on Saturday January 14, 2016 and two more hours on January 15, 2016. 

Have a very excellent experience to work on string manipulation, queue, and also read all discussions to get basic test cases with expected results. 

Make some points on hard algorithm in future week code contest. It seems that week of code is most popular contest on HackerRank, and the difficulty level is up-to-most-top-standard. 

After contest 

code study - link is here. 
Code review - rewrite the C# code, study and debug, code is here. 

More study on the code, and 2nd version before code review, code is here.
3rd version, code is here.

Status report

Julia finds out that there are so many solutions to study, and she does not have a lot of time to catch up so many things. Just go one by one.

She will work hard on the algorithm, through the contest, she understood that it is most important to stay humble, and she is thankfulness to enjoy the practice. Just learn one thing a time.

HackerRank - week of code 28

January 12, 2016

Introduction
Julia did some research by reading the article written by Dr. Patrick Cohn about tennis match performance and training, the article "Tennis Psychology: Practice Confidence vs. Match Confidence", she learned a few things. Here are her favorite quotes:

-----  great thoughts about tennis sports  - coding should also be the same  ---------

Let’s start by answering a basic question: What does it mean to play with trust? When you play with trust, you allow yourself to play freely – you have faith in your practice. You don’t grind on your technique or over coach yourself in matches because you are confident that you can rely on your practice. You just react to the ball, knowing your training will carry you.

Through practice and repetition – a lot of it – your body learns how to hit shots effortlessly, instinctively. Meaning with enough repetition and practice, you can hit shots without thinking about how to hit shots. You should think of competition as a “closed book test” to use a schoolwork analogy. You’ve studied (practiced) for the test. In competition, it’s time to trust what you studied. 

How does your trust break down all of a sudden when you play in a match? Many mental game or tennis issues can affect your level of trust in matches. A lack of confidence and cause your trust to not show up. Indecision is another barrier to trust. Fear of failure can kill the soundest strokes. Perfectionism can cause you to focus too much on perfect strokes and not enough on strategy and playing smart shots.

What can players do to improve their trust in matches?
Trust starts with having a balance in your practice routines. Practicing the right way will help you improve your trust in matches. The key is to practice like you compete.


-----   end of article excerpts ---

Go over again and again - four times!

Julia has faith in her practice! 
Julia has faith in her practice!! 
Julia has faith in her practice!!! 
Practice is getting better. 

So, Julia learns a few things here: 
notes will be written here later. 

She understands that it is very important for her to put herself on stress training daily, therefore, she did work on the week of code 28 so patiently, specially on the algorithm "Lucky Number Eight". She still likes to write a recursion function and review her favorite study blog written in less than 2 months - Nov. 24, 2016.

Contest workout

So far, she ranked 1480 out of 9215 on January 12, 2017, 11:23pm

One of Google employee cui aoxiang - performance unbelievable. She just kept finding new faces from Google, facebook, and also extraordinary performance. Next time, study her code and post some thoughts here.

Another good player from google. Click here.