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.