HackerRank - Bear and Steady Gene (VI)

Nov. 28, 2016

Julia noticed that those two blogs are most viewed:
http://juliachencoding.blogspot.ca/2016/03/hackerrank-bear-and-steady-gene_5.html

707 views

http://juliachencoding.blogspot.ca/2016/03/hackerrank-bear-and-steady-gene_13.html
699 views

So, Julia decided to review the algorithm, and she learned something new.

Summary of workout:
1. Find the most simple solution to study - two pointers, sliding window technique;
2. Write a C# version - understand the algorithm
3. Code review, and write a new version
4. Submit a code review request - her first coder review on stackexchange.com, and get some feedback.

Details:

1. Study the C++ code:
https://gist.github.com/jianminchen/c6b51207f9cc9b083573
Time complexity of algorithm: O(n)
typical two pointer technique, left/ right pointer, both at most travels forward once. 

Timeout issue - O(n^2) brute force solution 

2. Write a C# version: 
https://gist.github.com/jianminchen/c4f1c84c984e58fdcdc467e6f28d84e3

code review:
1. line 26, int[] a = new int[1007];
1007 is not meaningful, we know the size should be bigger than 'Z', and we only need the array of size 4
2. variable i and index are not meaningful. There are two loops.
3. valid function from line 49 - line 58
   line 52 - 55 - four constant chars are used.


3. Review the code and make the change:
https://gist.github.com/jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b

1. line 26 - 36, add 4 test cases, with 4 postcondition assertions
2. function name is changed to minChange
3. line 61, array of size 4 is declared instead of 1007
4. function indexOf() is added
5. variable names are changed, left, right, two pointers, move forward only
6. add two explanation variable c1, c2 to advoid complicated expression.
7. valid function is declared using a for loop.

Based on the code review on this post:
http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853
answered by Eric Lippert

4. Submit the code review on stackexchange.com code review, here is the link:

http://codereview.stackexchange.com/questions/148407/hackerrank-bear-and-steady-gene

Review got from the site:

• In C#, method names should be PascalCased, not camelCased.
• In minChange, you should use meaningful variable names for a, c, c2
• In minChange, you can set var ans = int.MaxValue, unless there is a compelling reason avoid using Int32 when you can use int, same with Int16 vs short or Int64 vs long.
• In indexOf, you can use a const string code = "ACGT"; instead. This gives some compiler optimizations.
• In valid, (and minChange) you should use meaningful parameter names, n and a don't have any contextual meaning.

Actionable Items: 

Julia likes to do some research, why it takes her over 6 years to start to work on stackoverflow, actively join the community, become one of them. 

Some facts she put together here:

1. Julia noticed on Nov. 28, 2016 that on stackexchange.com code review section, the experienced professional responded to her first post in less than one hour; (a fact)

2. The advice she got is free, she does not need to pay; all she has to do is to share her question and her research; And the comments are very good; She also enjoys the sharing her workout. 

3. Julia tries to get help from other professionals, she was too naive to check statistics of coding blog, but no one could give her any input. Finally, she figured out that she has to get smart, reach out stackexchange.com/ code review, ask help, show what she has completed. 

4. Congratulate Julia to know how to connect with other peers efficiently, her first post on stackoverflow.com - her first 10 points of reputation. 

5. Julia did some study on stackoverflow - how to ask a good question, and she knows that the question does not belong to her, it belongs to the community. That is the reason she can get help quickly. (her research on stackoverflow over 10 hours in Nov. 2016)

6. Write down her own understanding - research more later: Coding blog vs. stackoverflow contributions

Follow up 

June 6, 2017
Work on Leetcode 187 Repeated DNA Sequence

Stackoverflow - code review research

Nov. 27, 2016

  Try to post the first code review on code review on stack exchange, code review section.

When I try to put the title:
Leetcode 329 Longest Increasing Path in a matrix - DFS, memorization

Here are information coming out.

  Questions that may already have your answer

3

DFS algorithm too slow 1

2

Find shortest paths in a matrix using Dijkstra's algorithm 1

1

LeetCode Minimum Path Sum algorithm 1

6

Longest Increasing Subsequence 2

6

Python implementation of the longest increasing subsequence 4

2

Picking seats in a matrix

Review the above entries.

So many to read and so good the experience is. Cannot wait to spend time on those posts. Julia knows that it is time to make changes, her research usual touched the surface only.

For example, with stackexchange code review, her research from Nov. 30 posting the question to a perfect solution (Dec. 2, 2016) on Java TreeSet class floor method and its analog in C# ends up working code - SortedSet GetViewBetween, score maximum score. It takes less than 3 days to find a practical solution, with two experts' help.

Blog reading:
Bear and steady gene - C# algorithm:
https://gist.github.com/jianminchen/153eab0defae014842e8

Tennis sports and interviews

Nov. 26, 2016

Julia likes to play competitions on HackerRank in 2016, whenever she has problems, dealing with strategies, emotions, specially not good performance, she turns to tennis sports, and starts to study more tennis players, coaches; and try to find some great ideas.

This Saturday, she went through a few tennis interviews, and she learned something new. She likes to write down some notes:

1. Most favorite one - Nick Bollettieri - 84 years old, tennis coach,
(birth certificate has problem, should be 48 years old, not 84 years old. Age is just a number.)

https://www.youtube.com/watch?v=vQPo2firzjU&t=331s

Put next point, last point away, be able to control the emotions.

Coaching philosophy:
Be Conservative and Predictable. Be very gentle on first few minutes, you never know what happens to the player.
Work with young kids.
You cannot predict what will happen.
Genie Bouchard,
Talk about taking advantage of health, brought her to see young kids with cancer in hospital.
Respect the opponent, respect the crowd, children are watching you.
What is most important point? Next point.
Put forward, move forward.
Great acting man, are you in control?
Mind catches his talent, he can be a dangerous player.

Nick Bollettieri, Tennis Legend: Talks at GS Session Highlights (Goldman Sachs)
https://www.youtube.com/watch?v=UUxrQs0vzgk

Be able to read people;
Stop law school, back to tennis coaching. Coach almost 10 top one players.
Refuse to lose;
To be a winner, 24 hours job.
Talent, hard work, sweat?
What do you think it makes a good coach?
1. Listen
2. Do not say I cannot do it.
3. Success comes after team work.
Share up-time, share down-time.

80 years old, gave the speech:
1. Make every people feel respected; treat door man, garbage collector very well.
2. Can do attitude

2. Nick Kyrgios - young, 20 years old in 2015,

https://www.youtube.com/watch?v=NR-DwUwcpcs

Relax, will not get too angry;
Do everything you can, you can control.
Talked about home sick, his dad came to live with him on the tournaments, cooked for him.

3. Milos Raonic

4. Lucie Safarova - rising star

https://www.youtube.com/watch?v=KZ1i9Q6nt-U

5. Timea Bacsinszky
https://www.youtube.com/watch?v=fRnWJVXgNtk

She talked about her study on hotel management, and did some work on the kitchen at work. But she came back to tennis sports.

HackerRank - women's codesprint - Prim XOR - after contest practice

Nov. 25, 2016

Julia spent over one hour to read the problem statement in the contest, but she could not do good research to find out the ideas to solve the problem.

Problem Statement:  medium algorithm, maximum score: 50
https://www.hackerrank.com/contests/womens-codesprint-2/challenges/prime-xor

She likes to practice the algorithm very soon.

Stack Exchange: Code Review - Julia's new school

Nov. 24, 2016

Julia started her first day to look into stack exchange: code review, and then, she joined one of discussion - quicksort, she was amazed how she learned quickly in the place.

Her first reading starts from here:

http://codereview.stackexchange.com/questions/5648/any-way-to-make-this-recursive-function-better-faster/5661?newreg=7b2fea2453a54c15bc466355fea0891d

Learn from expert on code review:

http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853

http://codereview.stackexchange.com/a/142853/123986

Julia also wrote a blog about quick sort in 2016:

http://juliachencoding.blogspot.ca/2016/02/quick-sort-practice-makes-difference.html

Julia's favorite reading:
 http://codereview.stackexchange.com/questions/77782/quick-sort-implementation?rq=1

Study stackoverflow profile:
http://codereview.stackexchange.com/users/507/loki-astari

Actionable Items:

Read more live discussion on stackoverflow code review sections, at least find 5 top talents in C++, and find 10 advises from them in a week.

1. First one: Loki astari

Study stackoverflow profile:
http://codereview.stackexchange.com/users/507/loki-astari

Julia's favorite learning on Nov. 25, 2016:

-- start learning: 

http://codereview.stackexchange.com/a/77821/123986

 - 

Compilers Job

Don't do work the compiler can do for you:

int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};

The compiler is better than you at it anyway and it will prevent errors. Here you have said the number of elements is 8. As a human I can't see that at a glance I could count them to verify but as a human I am lazy and going to assume you got it correct. If you did not get it correct then we will have problems.
So let the compiler work it out.

int arr[] = {110, 5, 10,3 ,22, 100, 1, 23};

Now if the array changes size you only have to change one thing (the data). Rather than two things (data and size).
 -- end of learning  --

Coding Style - Great advice on coding/ design, a hackerRank question:

http://codereview.stackexchange.com/questions/140825/keeping-track-of-the-tennis-score/140827#140827

Book reading: Java Puzzles

Nov. 24, 2016

Here is C# reading list:

http://www.informit.com/articles/article.aspx?p=1769249

One of books is Julia's new favorite, she read first 3 puzzles, she loves them. So, she starts to read the book one puzzle at a time.

Java Puzzlers by Joshua Bloch and Neal Gafter


More reading:

http://codereview.stackexchange.com/questions/5648/any-way-to-make-this-recursive-function-better-faster/5661?newreg=7b2fea2453a54c15bc466355fea0891d

Leetcode 300: longest increasing subsequence

Nov. 24, 2016

Motivated by the article reading:
https://blogs.msdn.microsoft.com/ericlippert/2004/07/21/recursion-and-dynamic-programming/

Julia likes to practice this Leetcode 300, and then look into various solution using dynamic programming.

First, write a C# program using recursive, memorization solution, using code in the above blog.

HackerRank - woman codesprint#2 stone division - recursive design study (series 5 of 5)

Nov. 24, 2016

Being a software programmer, Julia learned the lesson through this medium algorithm - stone division; she stumbled on it, struggled to make it work over 5 hours, she knew that she had to make changes.  

She likes to do some research on recursive common mistakes, and then, further topic on recursive design concerns. After a few hours study based on Google search "recursive common mistakes", she felt that the study is still too weak. She likes to find some one with very strong technical background in industry, share ideas. So, with her research on stackoverflow recently, she started to look into who made contribution on stackoverflow on this topic. She found a lot to read. 

Here is her research to find her something to read on this topic: 

stackoverflow->
http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work?noredirect=1&lq=1
->
http://stackoverflow.com/users/88656/eric-lippert  (People reached: 10.8 million)
-> 

https://blogs.msdn.microsoft.com/ericlippert/2004/07/21/recursion-and-dynamic-programming/
->
https://blogs.msdn.microsoft.com/ericlippert/2004/05/20/results-of-the-fibonacci-challenge-are-in/
-> teach recursive
https://blogs.msdn.microsoft.com/ericlippert/2004/05/19/how-not-to-teach-recursion/

She found a top programmer, who designed C# in Microsoft and then work for facebook, and also she found the first article so helpful. 

Julia likes the style of writing and she quickly identified that the article has a great teaching style.  

https://blogs.msdn.microsoft.com/ericlippert/2004/07/21/recursion-and-dynamic-programming/

(Compared to Julia's sharing, two articles: first, she worked on leetcode algorithm, Leetcode 300: longest common subsequence, she blogged about it. second, she wrote on the dynamic programming, Lintcode 79: longest common substring, she also worked on it in 2016. )

Recursion series, more reading:

Julia's notes: 

Part 0:

https://blogs.msdn.microsoft.com/ericlippert/2005/07/25/recursion-part-zero/

Part 1: 

Teach how to think about recursion 

https://blogs.msdn.microsoft.com/ericlippert/2005/07/27/recursion-part-one-recursive-data-structures-and-functions/

recursive way to think about a list emphasizes the similarity of a fragment of the list to the whole list. 

recursively define a list as either

1. the empty list with zero items on it, or

2. an item followed by a list

appear to be a circular definition, but it is really not. 'Spiral' definition

All recursive functions follow the same basic pattern: 

Am I in the base case? If so, return the easy solution. 

Otherwise, figure out some way to make the problem closer to the base case and solve that problem. 

bottom out - base case 

A binary tree is either:

an empty tree, or 

a value associated with two binary search trees, called the left and right child trees. 

inductive hypothesis - 

Part two: unrolling a recursive function with an explicit stack 

https://blogs.msdn.microsoft.com/ericlippert/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack/

1 million nodes - balanced tree - 20 recursive depth - 2^10 = 1024, so 1 million is around 2^20

"anonymous locals" - 

callee's frame   -  caller's frame  - current activation frame 

the temporary variables are spelled out 

each recursion happens on its own line

Part three: build a dispatch engine

https://blogs.msdn.microsoft.com/ericlippert/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack/

January 13, 2017

Julia worked hard on the blog study, and then, she found out the code review on stackexchange.com, and then she started to post questions on algorithms, and get connected to the community. And this is a break-through, finally Julia stepped out her lonely zone - blogging, practicing, contest, and get really connected to people with same spirit - volunteer and also community builders. 

Feb. 23, 2017

Read the article about Google interview, and then read the comment from an ex-googler: 

With all that said, I haven't found any degree (at least from any school I've interviewed applicants for) to be a reliable signal for programming. Even if they went to a really good school, there's a good chance that they spent all their time learning network protocols and low-level mechanisms, and will happily write up a sliding-window implementation for me, but will stare at me blankly when I ask for a simple recursive algorithm. It's just tough to find people that spent time studying and practicing general-purpose computer science.

So, Julia reviewed the algorithm and wrote a more readable C# version to post a question on stackexchange.com. 

HackerRank - Woman codesprint#2 stone division - recursive intensive training (series 3 of 5)

Nov. 23, 2016

Julia failed on one medium algorithm - recursive function in the contest. So, she likes to get some training on the skill. 

 A few reasons she failed:
 1. Extra work - Recursive function involves building a string first. 
 2. Time consuming   - use StringBuilder, backtracking
 3. Failed to pass second test case; idea is not correct. 

Previous work intensive on recursive function:

Last time Julia learned recursive work intensively through HackerRank Linked List:

started from May 8 to , over 10 blogs about linked list:
http://juliachencoding.blogspot.ca/2016/05/hackerrank-linked-list-find-merge-point.html

http://juliachencoding.blogspot.ca/2016/05/hackerrank-insert-node-in-double-linked.html

Julia just marked all 13 linked list practice with label: linked list.

Use linked list in blog search to find all 13 of them.

UVa online judge and a solution blog

Nov. 22, 2016

Plan to work on the UVa online judge and read the solution blog, and see if Julia enjoys the solution. 

Blog reading:
UVa website
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

Solution website: facebook tool engineer - ICPC winner in 2011 - 2012
http://www.questtosolve.com/browse.php

A few notes about how to start this blog with all solutions:

Julia worked on the HackerRank, and then, she followed one of player on twitter less than a week ago, who has an experience on ACM ICPC competition; and then, on Nov 22, 2016, Twitter sent an email about suggestion based on the connection: Wesley may @wjomlex, she followed, and then, she found the blog:

http://www.questtosolve.com/browse.php

Actionable items:

Work on 1 - 3 medium level algorithm by myself, and then, read the solutions. Tell at least 1 - 3 differences compared to HackerRank medium algorithm.

Minimum Cost - HackerRank woman codesprint #2 - Summary (Series 10 of 10)

Nov. 21, 2016

Here are the summary of HackerRank woman codesprint #2 minimum cost 10 blogs. The main goal is to improve performance, best performer can work on the algorithm in less than 10 minutes/ 30 lines of code. It takes a lot of insights to work smart and avoid time-consuming ideas.

Each blog serves one individual purpose for Julia's practice with an ordinary algorithm, medium level difficult, entry-level one.

Blog 1 - performance in the contest
http://juliachencoding.blogspot.ca/2016/11/womans-codesprint-2-minimum-loss-in.html

Blog 2 - study after the contest
http://juliachencoding.blogspot.ca/2016/11/womans-codesprint-2-minimum-loss-after.html

Blog 3 - Java TreeSet class - implementation in Java
http://juliachencoding.blogspot.ca/2016/11/java-treeset-study-minimum-loss.html

Blog 4 - C++ Set class - implementation in C++
http://juliachencoding.blogspot.ca/2016/11/c-14-set-class-study-minimum-loss.html

Blog 5 - C# SortedSet, SortedDictionary - implementation in C#
http://juliachencoding.blogspot.ca/2016/11/c-sorteddictionary-minimum-cost.html

Blog 6 - failed code study
http://juliachencoding.blogspot.ca/2016/11/minimum-cost-study-failed-code-partial.html

Blog 7 - Simplicity comparison, performance presentation
http://juliachencoding.blogspot.ca/2016/11/minimum-cost-comparison-of-simplicity-c.html

Blog 8 - Binary Search Tree algorithm, classical solution - Julia's favorite
http://juliachencoding.blogspot.ca/2016/11/binary-search-tree-algorithm-supports.html

Blog 9 - To be determined.
http://juliachencoding.blogspot.ca/2016/11/minimum-cost-hackerrank-woman.html

Blog 10 - inspiration by verse from tennis world champion - Roger Federal

When you're good at something, make that everything. 

"When you're good at something, make that everything" - Roger Federer #tennis pic.twitter.com/9orryZK9w9

— Tennis Coaching™️ (@tennisdothow) October 8, 2016

Minimum Cost - HackerRank woman codesprint #2 - Summary (Series 9 of 10)

Nov. 21, 2016

Plan to come out the idea for the slot - series of No. 9 of 10.

Roger Federal used to inspire Julia a lot with the verse. "Make your strength to everything."

Julia only survived on the contest of woman codesprint #2 with first one medium algorithm, from 3 medium, 2 hard algorithm, total 5 algorithm. So, she decided to make this medium algorithm to everything, blog the practice with a series of 10 blogs.

Ideas can be any one of them:
 1. Find things to work on through studying submission, performance discussion, statistics of most popular solutions among C++, Java 8. 2.

 2. Just warm up the algorithm with 1 -5 practices, different ideas.

 Will come back soon. Julia's most favorite verse to motivate herself to serve better through blogging. Every effort makes different. Every blog counts to progress, no matter how small it is.

Life is like a game of tennis, the player who serves well seldom loses. 

"Life is like a game of #tennis, the player who serves well seldom loses" #TennisQuotes pic.twitter.com/CICYQYeMfg

— Tennis Coaching™️ (@tennisdothow) October 9, 2016

HackerRank stone division - recursive design study (series 4 of 5)

Nov. 23, 2016

Introduction

It is time to get some training on recursive function. Learn a few terms related to recursive function first, Julia can describe what problems she had in the contest. She had problem to come out a simple recursive function, after so many years hard working as a scholar and full time programming experience.

She missed the important part to work on, recursive step, build a recurrence formula.  

C# solution - copy the code from editorial notes: score 50 - maximum score, pass all test cases

In the above C# solution, line 80:

ans = Math.Max(ans, 1 + ( (pile/runner) * rec(runner) ) );

Study Recursive Function
Julia googles searched the recursive function, and then she found 3 things to work on. And then, she noticed that her study lacks depth of industry experience. She found an engineer on stackoverflow.com, and then she spent a few hours to read his blog. Great teaching about recursive. 

Google Search: recursive function common mistakes

Choose some content to read:

1. university lecture notes - umd.edu
2. IBM article
3. lecture notes - MIT
4. recursive function blogs

Here are the details. 

1. university lecture notes - umd.edu:

Write down keywords:

c - core dump 

c - compact code - recursive solution 

h - How to think recursively?

s - stack space - recursive vs iterative 

     O(n)  vs  O(1)

    stack size - several megabytes - 1000 recursive calls 

t - tail-recursive function 

Google those keywords, and get more readings.

2. IBM article 

Notes:

Inductive definition 

inductively-defined 

Bug source: state changes

Ideas to avoid bugs:

    No variable does double-duty

    Be certain that all variables hit the state they are supposed to be in when the loop restarts. 

One rule: 

Assign a value to a variable only once and NEVER MODIFY IT!

1. Reusing a variable 

2. Conditional modification of a variable 

3. Loop variables

Base case proof. 

Inductive step proof. 

3. Lecture notes - MIT

Two common mistakes:

1.     The base case is missing entirely. or the problem needs more than one base case but not all the base cases are covered. 

2.     The recursive step doesn't reduce to a smaller subproblem, so the recursion doesn't converge. 

base cases

recursive steps

decompose a recursive problem into recursive steps and base cases

when and how to use helper methods in recursion

understand the advantages and disadvantages of recursion vs. iteration 

Structure of recursive implementations

- base case

- recursive step

A direct recursive implementation 

Don't expose the helper method to your clients

Temporary state 

Evolution of the computation

Recurrence relation 

Helper methods

Choose the right recursive subproblem

4. Eric Lippert's blog about recursive function

More reading:

stackoverflow->
recursive question/ answer by Eric Lippert
->       Eric Lippert

->  recursive blog

->  fibonacci challenge blog

-> teach recursive - how not to teach recursion

Recursion series:

Part 0:

Part 1: 

Teach how to think about recursion 

Julia's notes

recursive way to think about a list emphasize the similarity of a fragment of the list to the whole list. 

recursively define a list as either

1. the empty list with zero items on it, or

2. an item followed by a list

appear to be a circular definition, but it is really not. 'Spiral' definition

All recursive functions follow the same basic pattern: 

Am I in the base case? If so, return the easy solution. 

Otherwise, figure out some way to make the problem closer to the base case and solve that problem. 

bottom out - base case 

A binary tree is either:

an empty tree, or 

a value associated with two binary search trees, called the left and right child trees. 

inductive hypothesis - 

Part two: unrolling a recursive function with an explicit stack 

1 million nodes - balanced tree - 20 recursive depth - 2¹⁰ = 1024, so 1 million is around 2²⁰

"anonymous locals" - 

callee's frame   -  caller's frame  - current activation frame 

the temporary variables are spelled out 

each recursion happens on its own line

Part three: build a dispatch engine

Follow up after 3 months

Feb 23, 2017

Because of this study, Julia looked into stackoverflow.com, and then she found the code review on stackexchange.com. She did great job to help herself, from a failure to solve a recursive function to study recursive function, know one person/ a blog/ code review site, she is no longer a lone coder. She asked a lot of questions and tried to answer a few questions. She tasted the success of solving problem with other's help. 

HackerRank stone division - after the contest (series 2 of 5)

Nov. 20, 2016

Introduction
HackerRank - woman codesprint #2 - stone division

Julia learned one algorithm a time after the contest. Every time she fails to solve an algorithm in the contest, it is her favorite learning time.

Spend 20 minutes to study Editorial Notes about the solution first.

 1. Julia's C# solution followed the study: 
After one hour study of the code converted in C#, Julia found out that she overcooked the solution, got too far to do the work instead of being lazy letting recursive function play the role.

First time again in a few month after she worked on linked list, she found out that she had to learn the tip again to fully take advantage of recursive function, give the confidence to allow recursive function to take care of business.

2. Let us learn the recursive again, let it do the beautiful work. And Julia take a break.

C# solution - copy the code from editorial notes: score 50 - maximum score, pass all test cases
https://gist.github.com/jianminchen/85980e8f52c701027fbf25a8f2293e96

Play with code, remove memorization, score 16/50, fail test case 11 and up
https://gist.github.com/jianminchen/de08d6a479e059b4238bec1d23ab6e12

Continue with a blog about recursion study.