Wednesday, November 30, 2016

How to work at Google: Example Coding/Engineering Interview

Nov. 30, 2016

Google interview talk:

How to Work at Google: Example Coding/Engineering Interview

https://www.youtube.com/watch?v=XKu_SEDAykw

Will take some notes very soon.

Google interview talk including system design

Nov. 30, 2016

Google interview talks are excellent.

1. Passing the Google interview as a software engineer


Fog Creek Software twitter account

Nov. 30, 2016

Julia plans to read articles through the twitter account of fox creek software:

https://twitter.com/FogCreek

Write down articles she read through the above twitter account:

1. https://business.stackoverflow.com/blog/how-to-optimize-your-candidate-experience-for-remote-developers

Will read more articles.

1. 11 minutes talk, transcript available.
http://blog.fogcreek.com/n-ways-to-be-a-better-developer-interview-with-lorna-mitchell/

2. https://blog.fogcreek.com/how-we-use-fogbugz-for-recruiting/

codereview.stackexchange.com - Julia's new school (II)

Nov. 30, 2016

Introduction:
Julia was so excited to read so many experts's well-written answers first time, on live sites. She just could not believe that she enjoys reading so much.

Julia only can read one post a time. Also, Julia likes to write down what she likes to work on after reading those posts.

Detail:
Find 10 favorite reading on code review:
Search keyword, HackerRank, and choose tab - votes

http://codereview.stackexchange.com/search?tab=votes&q=HackerRank

1.   http://codereview.stackexchange.com/questions/139896/determining-if-the-kangaroos-will-land-in-the-same-position

The answer Julia really likes to read again and again:
http://codereview.stackexchange.com/a/139898/123986

Will come back to write more.

2. Design talk, junior level coding skills -> great ideas to improve
http://codereview.stackexchange.com/questions/36482/rpsls-game-in-c


3. Follow the advice as well -
http://codereview.stackexchange.com/questions/11233/responsive-adaptive-website-code

4. Interview task - SOLID Priciples and TDD (Dec. 4, 2016)
http://codereview.stackexchange.com/questions/41834/interview-task-solid-principle-and-tdd/41843#41843

5. ChrisWue - what questions are answered.
http://codereview.stackexchange.com/users/30346/chriswue


6. Play with code, and write two versions: OO version, old school version as well.
http://codereview.stackexchange.com/questions/36395/rock-paper-scissors-lizard-spock-challenge/36402#36402

7. Julia just loves to read:
http://codereview.stackexchange.com/questions/107581/check-if-more-engineers-are-happy-than-not-happy/107594#107594

How to become a great front-end engineer

Nov. 30, 2016

Introduction


Julia starts to learn everything in order to be a front-end engineer, she started to learn CSS a few years ago, in 2013. And then, she spent over 10 months to learn JavaScript, in 2014, and continued on many topics. And then, she worked very hard to work on computer foundation, Leetcode algorithms, HackerRank, from 2015 to 2016. She needs to learn to write solid code.

Also, she needs to find time to go over so many courses on front-end on pluralsight.com, she learned a few things in 2016 about web usability, and on CSS, html5, bootstrap, Angular JS etc.

Article to read


How to become a great front-end engineer

Arguments Julia likes to evaluate:

1. "The longer I work on the web, the more I realize that what separates the good people from the really good people isn’t what they know; it’s how they think."

2. "Read other people’s code"
Solving problems on your own is a great way to learn, but if that’s all you ever do, you’ll plateau pretty quickly.

3. Work with people smarter than you

4. Reinvent the wheel 
But in this article I’m talking about how to go from good to great


5. Write about what you learn

 The best reason is it forces you to understand the topic better. Even if no one ever reads what you write, the process of doing it is more than worth it.


Blog reading


1. https://philipwalton.com/articles/

2. https://twitter.com/FogCreek



Tuesday, November 29, 2016

HackRank - New Year Present - ACM ICPC Practice Contest 2016

Nov. 29, 2016

Problem statement:

https://www.hackerrank.com/contests/acm-icpc-practice-contest/challenges/newyear-present

Julia spent Sunday Nov. 27, 2016 morning to work on the algorithm near 2 hours, she could not make any points on the algorithm. The contest stated at 6:30am, but she did not start until 9:30am. A few things she has to work on:

1. The math she worked on needs to be reviewed carefully.
2. She should focus on getting the math analysis correct first.
3. She played with code and then got more concrete ideas what she should work on.

3 submissions she did:

1.
https://gist.github.com/jianminchen/bcee26d0f395cd6dee04b3d53184c2a4

2.
https://gist.github.com/jianminchen/4685370ce58987054c0336b9f1dfdcfd

3.
https://gist.github.com/jianminchen/e64d46ac00f157e4871f7f27b0798131


Actionable Items:

Julia, go ahead to work on other algorithms on the contest. Make "New Year Present" work first.

ACM ICPC only has 5 hours, but 8 questions. So, each algorithm at most 40 minutes. There are 3 people in a team. Not one person's game.

The algorithm should be very elegant, classical algorithm.

Julia, if the combination is not simple enough, you probably cannot make it; better to read other algorithms and get informed about the contest instead.

Blog reading:
1. https://philipwalton.com/articles/how-to-become-a-great-front-end-engineer/

2. https://css-tricks.com/interviewing-front-end-engineer-san-francisco/

3. https://medium.com/@YogevSitton/the-ultimate-reading-list-for-developers-e96c832d9687#.gaawpaf01


Monday, November 28, 2016

Research: Write coding blog vs contribution to stackoverflow?

Nov. 28, 2016

Julia likes to share her experience on writing coding blog vs contribution to stackoverflow. Both areas she is new.

Facts:
1. coding blog, less than 2 years; starting from June 2015
2. stackoverflow, less than 1 month; she did add her profile in Nov. 2016.

To write a coding blog is a lonely journey, she tried to figure out how others are doing, and how others are busy working on to progress to be top-talented.

Julia did work on several issues efficiently through coding blog:

1. Keep track of what she did work on before; document the time she worked;
2. Google blogger has very good features, very easy to do blog search, labels are very helpful;
3. Julia started to find more ideas to get more organized, work on the algorithm continuously through days, weeks, months.
4. Julia had good time to read her own coding blog, on her cellular phone, desktop, and everywhere.

It is like tennis sports, it is better to have a lot of hitting partners, and learn from team work, communications.

Julia did not get any coding review through blog comment. So, it is true that not so many people work on coding blog these days. One of reasons Julia works on is to develop her writing talent.

Share a quote to encourage herself to work hard - find it first!

Will come back to add more thoughts on the topic.

Actionable Items:
1. Study the post:
http://codereview.stackexchange.com/questions/116469/print-the-n-longest-lines-in-a-file

2. Study how she does to get such good performance:
http://codereview.stackexchange.com/users/36120/emily-l



- Julia likes to calm down quickly when she gets nervous. When she has a negative self-talk, she will remind herself - "Everyone faces challenges on court and I'm no different." Replace with positive self-talk.

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 acc2
  • 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

Sunday, November 27, 2016

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

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

Saturday, November 26, 2016

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.




Friday, November 25, 2016

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.

Thursday, November 24, 2016

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)
-> 

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:

Part 1: 
Teach how to think about recursion 

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 

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

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. 

Wednesday, November 23, 2016

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.


Tuesday, November 22, 2016

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.

Monday, November 21, 2016

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. 


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. 

Sunday, November 20, 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.


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. 

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

Recursion series:
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 - 

1 million nodes - balanced tree - 20 recursive depth - 210 = 1024, so 1 million is around 220

"anonymous locals" - 

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

the temporary variables are spelled out 
each recursion happens on its own line

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.