Sunday, May 28, 2017

Numeric string - world codesprint 11

May 28, 2017

Problem statement is here.

Code submission in the contest is here, score full score 30 points.

Saturday, May 27, 2017

The best mask - world codesprint 11

May 27, 2017

Introduction


Problem statement is here.

It is 9:30 pm, Julia worked on the algorithm starting from 7:00 pm, and then after 2 hours 30 minutes, she finally made some progress. Here is the report:


Good food, a blog, one hour nap, 


As a hackerrank player, Julia got home 3:00 pm, she spent 45 minutes to write a blog about mocking experience to entertain herself first; She took a nap from 5:00 - 6:00 because she felt tired after working on algorithm "city construction"; She entertained herself with a friend with dinner, and talked about her mocking experience and hackerrank contest.

Julia tried to bring herself to a zone before she starts to code again. And then she studied more about "city construction" medium algorithm. She knew that she should be able to write something for the algorithm before 12:00 pm.


Compare to a peer


One thing Julia likes to do is to check ranking by country: Canada. She likes to compare one of top players, and here is the comparison. The time is running out, Julia like to choose some algorithms to work on in next 3 - 4 hours.

Understand hard level



Gave up at 10:37pm. Try to give at least 2 hours to solve "city construction". The algorithm is asking number of ones in the binary expression of x is minimum. Julia worked on the problem like "number in the binary expression of x is minimum".

Julia tried the idea to solve the problem, but her solution scored 11 points. She gave up the effort and will work on it after the contest.

Follow up 


May 28, 2017  1:44 pm
After the contest, post the code submitted in the contest. Score 31 out of maximum score 75. Will look into the correct solution later.

A cheerful heart is good medicine

May 27, 2017

Introduction 


Proverbs 17:22, Julia's favorite verse. "A cheerful heart is good medicine, but a crushed spirit dries up the bones". Every time Julia is too busy to work on something, and then she likes the feeling of a cheerful heart. She shares a story of a cheerful heart, and ends her weekend with some good story.

The mocking experience is related to people skills and Julia started to learn how to make most from it. She has limited resource and limited budget to try new things. She chose free mocking experience, she never tried any paid mocking experience, but she did feel that she has to make mocking experience very good learning activities.

4 Sum


People with top talent to attend mocking usually are very young and just start his/ her career, and one time Julia felt that the hints were too strong in the first 5 minutes, she had to take the hint given by peer. The algorithm is 4 sum, Leetcode 18.

Edit Distance


Julia learned so many lessons from her own mistakes. She could not figure out dynamic programming Edit Distance in her first round mocking in 2017. Overall, she almost failed at least 20% - 30% in her first round. She just failed poorly on spiral matrix and then she saw some one failed as an interviewer, she observed the failure but she appreciated the chance to be part of to solve a problem.

Every peer get stumbles in mocking experience, she reminds herself not long ago she had same experience. Julia felt so connected through mocking experience.

She suddenly found out that she never met and talked to so many engineers in the world, but she did in one weekend. As a programmer, she felt a little proud of learning to review peer's code and also recommend a book "The Art of Readable Code".

Last long weekend, she managed to finish 11 mocking experience. So she almost finished her second round. The fact is that second round is learning round. Test your own code, not using compiler, use your own whiteboard techniques.

Reverse string 


The fact is that she met strong peers who shared her importance to learn and write good clean code, specially recursive, DFS, and also the peer still practices. The meeting is short but she feels that the study group formed through the discussion is also very rewarding experience, she would be a nice algorithm teacher one day if she continues.

It is fun to play with a peer. One day, Julia  met a peer again and she was too busy to follow the peer's idea to solve the problem, but she knew that the peer was working hard and the idea needs to be tuned. Julia likes to gain some skills to be a professional interviewer one day, so she learned quickly to say sorry, not followed closely with the ideas in the code. Good heart leads to a new world, the peer told her that there is something new and different, she was well received with a tip.

"Every player knows how to play tennis". That is the famous tennis professional player's quote. Only those survive with strong mind set, and determination, and the hard work training, practice.

Related to tennis sports, Julia learns to treat peers equally and be supportive in mocking experiences.

Julia missed how a professional mocking experience will look like. She booked one mocking and surprisingly she got one in less than one week.

Study and talk 


Julia wrote a blog about the study "Does mocking make difference", and then she moved herself to next stage in her practice, know a professional interviewer with thousand experience, and also learn to mark herself with a mark, May 27, 2017, she got a mark which is called passing the bar - 2.5. 

Good heart leads to a new world. Julia likes to show people that she has determination to gain skills in algorithm and data structure, and is working hard on the improvement. Still exploring...

Julia understood that those contest practice with medium levels are very helpful, she prepared herself, she felt that the depth first search, recursive function call is so important to learn.

She forgets to write a base case in DFS algorithm, still she needs to the hint to go over the test case and then find out that she lets the loop forever because of that.




City Construction - world codesprint 11

May 27, 2017

Introduction


Now it is 3:08pm, 18 hours left for the contest. Julia was busy this morning. She had her first mocking experience with a new company called refdash.com. She could not believe that after 40 mocking experience, she started to enjoy solving algorithm and data structure problems and survived first algorithm.

After 10:00 am - 11:30 am mocking experience, she went back to the .NET user group and had a lunch, attended one hour session for a talk. She quit early because she likes to get some learning experience through those four algorithms. One medium level, one hard level, two expert levels algorithms in world codesprint 11.

Julia likes to play contest and she just could not believe that she could not take whole afternoon to sit in lectures. She likes to play competition, and get challenged on algorithms. Julia is an active learner, she likes to try new things, build something using her crafting skills, specially algorithm problems.

Coding in the contest 


Code from 10:00 pm to 3:00 am, score 0 even though the algorithm passed a few of test cases Julia set up, also sample test case. Great learning opportunity after the contest. 

Here is the progress report. 


Follow up after the contest


May 28, 2017 1:38 pm
Code submitted in the contest is here. Score 0. Will find out why test case 1 fails, there are 10,000 roads. Timeout is the issue.

The union find algorithm is the classical algorithm, which can be applied to this "City construction" algorithm. 

Friday, May 26, 2017

Simple File Commands - world codesprint 11

May 26, 2017

Introduction


It is 11:51 pm. Julia likes to check her progress of the contest. She likes to work on every algorithm, and take the chance to learn something, specially hard and expert level algorithms.



Status report 

Follow up after the contest


May 28, 2017
Code submitted in the contest is here, score 20 out of maximum score 40. 

Thursday, May 25, 2017

Data Structures & Algorithms with JavaScript - Michael McMillan

May 25, 2017

Introduction


It is the best time of the year to learn JavaScript. Julia chooses to read the book and learn more about JavaScript. She likes to think problem solving using JavaScript in the future, so it is better to start to build hours to practice, read the book 30 minutes a time.

Book reading 

Coding Interviews - Harry He

May 25, 2017

Introduction


It is such a great book and Julia read the book back in 2015. Now it is the time to review the book again.

Book reading 



Wednesday, May 24, 2017

Leetcode 48: Image Rotate

May 24, 2017

Plan to work on image rotate.

The idea is to visit nodes in the matrix using the order of top row, right column, bottom row and then left column. So the rotate 90 degree clockwise is to shift the array to left.

C# practice is here.

The idea is to first reverse up to down, then swap the symmetry.

C# practice is here.


Leetcode 151: reverse words in a string

May 24, 2017

Problem statement is here.

C# practice is here. Need to work on failed test cases, multiple space, "a   b" should be reversed to "b   a".

Tuesday, May 23, 2017

Leetcode 37: Sudoku Solver

May 23, 2017

Introduction


Sudoku solver is the most classical algorithm to apply Depth First Search (DFS) using recursion and also use back tracking as well. Julia had a very good experience in May 22, 2017, she had chance to learn to write a short version of depth first search coached by her mocking peer.

Most important design is about base case. To make the implementation as simple as possible, DFS algorithm can start from the matrix left top corner, and then scan from left to right, top to bottom, if the row is bigger than 8, then it finds a solution.


Algorithm Study 



Problem statement is here.

The C# code practice is here.

Algorithm talk 

May 25, 2017

It is also very good experience to use Sudoku Solver algorithm to conduct mocking experience. Julia did her first mocking experience using the algorithm as an interviewer.



Leetcode 54: Spiral Matrix

May 23, 2017

Introduction


It is a good habit to review the code and then run a few test case to verify the code. Once you finish the white board testing, you tell that you are ready and code is complete. As a software programmer, it is not too late to start to build a habit, examine the code with coding style, run white board testing, and think about possible bugs. Have a high standard, push yourself.

Code design talk


C# code submission is here. Leetcode discussion link is here. Plan to ask a question on codereview.stackexchange.com.

Monday, May 22, 2017

Bronze medal celebration - week code 32 on hackerrank

May 22, 2017

Introduction


It is a small contest but Julia learned how to advance her algorithm research and problem solving skills. Julia still has to learn how to identify advanced algorithm as a classical algorithm in the contest, and then improve her performance from less than 10% to more. No matter how good you are as a programmer, if you cannot relate to the specific advanced algorithm or data structure, the timeout will cause you lose 90% score.

Julia dedicated her effort to work on last two algorithms in the week code 32, she was busy with near 10 mocking experience May 20 - 21 weekend, and then she only had chance to work on those two algorithms. She did not spend time to work on two medium algorithm at all. 

The score is so low, but the bronze medal is the celebration of her brave to solve hard and expert level algorithm, prepare herself to advance her study to two more advanced algorithms - one is called network flow and the another one is called treap tree.


Actionable Items


Study discussion, link is here.

Leetcode 114: Flatten Binary Tree to Linked List

May 22, 2017

Plan to study the algorithm Leetcode 114 Flatten Binary Tree to Linked List. Watch the video lectured by Yu Zhou, the link is here.

cc189: 4.2 Minimal Tree

May 22, 2017

Plan to study the video Minimal Tree lectured by Yu Zhu in Chinese.

Treap algorithm

May 22, 2017

Plan to study treap algorithm. Here is the algorithm on geeksforgeeks.com.

Julia played the contest of week code 32, she had a lot of fun to play with the algorithm special substring. After the contest, she learned that the algorithm can be solved using treap algorithm.


Leetcode 39: Combination Sum

May 22, 2017

Plan to study the video about Leetcode 39: combination sum. Here is the video link by Yu Zhou.

Leetcode 47 Permutation II

May 22, 2017

Study the video by Yu Zhou, the link is here.


Leetcode 78: Subsets

May 22, 2017

Introduction

It is so much fun to play hackerrank contest, Julia has to learn how to do a quick research how to identify what kind of advanced algorithm for those hard or expert level algorithm. It is so frustrated to see the score 7 out of 90 on special substrings algorithm.

To get back to normal daily grind, Julia chooses to follow the video from Yu Zhou, learn one algorithm a time, here is the video link on youtube.com.

Leetcode 78 Subsets



The element of style

May 22, 2017

Plan to read the book reading: The element of style.

It is a good idea to read a short book and then learn something about English writing. It is inspired by the article Elements of JavaScript style written by  Eric Elliot.




Ford-Fulkerson Algorithm for Maximum Flow problem

May 22, 2017

Introduction


It is time to learn a new algorithm called Ford-Fulkerson for maximum flow problem. Here is the one article to study on geeksforgeeks.com.

The link is here.

Julia worked on week contest 32, and there is the algorithm she chose to work on called Boxes and Balls. She learned after the contest that the algorithm should be solved using network flow knowledge.

Algorithm study 

Max flow problem introduction on geeksforgeeks.com is here.

The art of programming contest

May 22, 2017

Plan to read the book "The art of programming contest". Julia read the discussion of special substrings algorithm in the week code 32 contest, here is the discussion link. Read the discussion:

"I studied Programming Challenges 3, Programming Contests, Hitchhiker's Guide to Competitive Programming and the Art of Programming Contests. I know what the most frequent algorithms is."



Write down a note to finish 30 minutes reading each time here.

1. May 22, 2017  12:04 pm - 12:34 pm

Chapter 2 Game Plan for a contest

Sunday, May 21, 2017

Special substring - week of code 32

May 21, 2017

Introduction



Special substring is the last algorithm in the week of code 32, and it's max score 81, success rate 9.03%, difficult level is expert, and it ends in 14 hours. Now it is 9:52 am. Julia has to work on the algorithm before 12:00 pm before her first mocking experience starts. She booked herself 5 mocking experience today, and in-between she likes to work on those 3 algorithms in the week of code 32, two other medium algorithms as well.

The problem statement is here.

Coding in the contest 


2:43 pm, first submission, score 16.70. Have timeout issue, wrong answers for the first 20 test cases. 


Ranking study 


It is a good idea to do comparison, and then determine where to gain more points in less time, and also learn and have some fun.

Timeout problem solving 


3:22 pm
Work on timeout issue, pass test case 9, score 20.06


One more progress


3:37 pm, fix the timeout issue, now score 23


Discussion panel 




Read the discussion:

I studied Programming Challenges 3, Programming Contests, Hitchhiker's Guide to Competitive Programming and the Art of Programming Contests. I know what the most frequent algorithms is.

Follow up 


May 22, 2017
code submission is here in the contest, score 6 out of 90. 

Can mocking make difference?

May 21, 2017

Introduction


It is a good habit to do some small topic research and then figure out what to look into. Julia did 4 mocking experience today, and then she likes to do some research, the topic is "Can mocking make difference?"

Study 


Mocking makes difference.

Things Julia learned through mocking experience. Every peer has different talent,  different learning style, Julia learns to speak slowly, clearly, make good points, and then present best talent to the peer. And also Julia learns to review the code carefully as a peer, give hints less or more.

1. Use headset to talk, a few people complained about echo sound.
2. Do not be hacker in mocking. I have to take the hint, follow the hint.
3. Need to work on the attitude. Set up camera properly, and also give people good impression. Practice makes perfect.
4. Julia enjoyed to learn C++, Ruby and Python through mocking experience.
5. Julia learns the importance to practice algorithm and data structure. Peers share their insights.

It is the great to learn algorithms through the mocking experience. Now Julia is easy to figure out how people get stuck on one algorithm, one specific issue. She can relate her performance to one of peers, and she knows that her next performance level and how great it should be. She can easily relate to one of her peers and then work hard to improve. She can manage her own thoughts and expectation of her own performance realistically.

Learning algorithm is easy to reach a plateau no matter what you take, by learning from practice, a book, a contest, a code review on the stackexchange.com. But learning from the  peer, it is like having a coach sometimes, the discussion part is also exciting sometimes.

Met peers from New York, Indiana, country of Ireland, Taiwan. Two new graduates and one experienced "It is always in day 1".

Recursive Syndrome


Julia experienced two times recursive syndrome in real experience spanning from 2015 to 2017. She asked herself why, between those 3 years she practiced so many algorithms, why she still failed on the basics, not asking the choice of iterative or recursive, not knowing depth first search (DFS) algorithm can be implemented using recursive intuitively.

She learned through near 30 mocking experience, the experience taught her to be super patience.

Last 3 year she only did around 40 mocking experience, but 30 of them she did in last 2 months. She first time experience how good she can do to compare with others, if she does not practice at all. To be a learner she has to step out from comfortable zone, meet and talk about algorithms with peers.

Besides algorithm problem solving, there are other traits and characters to help people identify who you are, the way you present, the attitude, if you have high standard for your own code. Have you worked on the basics, coding style, and apply test case in daily programming or not. 30 minutes is a great window for the peer to observe you.

If you are really smart and have a good match with both good performance, then you will find that you two will end up having some time to chat something more interesting, the book you like to recommend, the place you live and sharing of career growth, and other things.

What if 


One day Julia will get used to mocking experience, and accumulate over 100 times experience; What she will still excite to go for 101?

Before Julia does not care how others are achieved so much, now she knows that people are working hard and keep quiet, and practice again and again until he/ she feels comfortable with the trials.

Julia knows that each company what kind of level programmers are working there and how she should work on to be competitive, catch up.

Specially Julia thought about young graduate from university bachelor or master degree program, without much experience, what makes them so competitive? The top ranking computer science university, the degree, or high performance in the study of university degree?


Learn to play



It is very good topic to study how to work smart with other people. Through mocking experience, Julia learns to improve her speaking English.


Julia has to speak slowly, and also get used to share what she learns. She likes to see if the voice training drill can help her, it is not easy to reduce the accent, improve the pronunciation.

The same idea is in James 1:19,  "let every person be quick to hear, slow to speak." Just speak slowly.

Actionable Items



Mark 30+ mocking experience, 40+ mocking experience, one algorithm 3+ mocking, 5+ mocking,

30+ mocking experience:

40+ mocking experience:

Assuming that you have chance to meet people with the range of performance from top 70% to 30%. But with 40+ mocking experience, you may have a surprise with top talent and top performance.

one algorithm the first mocking -

one algorithm 1+ mocking - you start to pay attention more on algorithm itself, you do not care about the ratings you get, you know that you just worked on the algorithm. You love to learn, that is the reason you like to use the algorithm again and again, see how peer learn and solve the algorithm with/ without your contributions.

one algorithm 3+ mocking -
one algorithm 5+ mocking -




Saturday, May 20, 2017

Balls and Boxes - balls and boxes

May 20, 2017

Introduction


It is a busy Saturday morning, Julia setup two mocking experience 10:00 am and 12:00 am, and then another one is 4 pm, last one is 8 pm. So in-between she likes to work on week of code 32. Now she has 40 minutes to work on the algorithm, from 3:10 pm - 3:50 pm.

Problem statement of Balls and Boxes is here.

Algorithm 


Progress report - 5/21/2017  12:28 am 

After hours of writing the code, from 9:00 pm to 12:28 am, over 3 hours work, first success submission scored 38 points with only first 4 test cases, failed #2 test case. There are 5 more test cases are not tested.

The score will go down more because there are more failure test cases. Right now, the maximum score is lowered to 57 from 70 since the algorithm has the full score the first day, and then go down next day to 63, go down to 57 the third day.



And the ranking on lead board moved forward from 3000+ to 1022. Let us compare to a Googler: 


Julia looked into the success rate first, and then she decided to work on this hard algorithm. The whole day Julia was busy with mocking interview, 4 mocking experience. She was glad that her effort  on balls and boxes improved her ranking over 1000 once.

Julia reviewed her code and then she tried to fix the test case 2. So she likes to journal some writing on the paper about her thinking process and then share it after the contest.

Learn through the thinking process. Write down all test cases tested in the contest.

May 21, 2017 9:58 am


Follow up 


May 22, 2017
Code written in the contest is here. Score 6 out of 70.

Friday, May 19, 2017

Book reading: The art of readable code

May 19, 2017


Introduction


As a hackerrank contest player, Julia likes to do some research on how to improve her performance. She was surprised that she could not figure out easy algorithm on Hackerrank last year, and then she posted questions on codereview.stackexchange.com, and then she quickly followed the advice. She felt more confident on easy algorithm on hackerrank contest. Here is one of questions she asked on a easy algorithm called Spiral Message.

For medium level algorithm, Julia stumbled badly on Rookie3 maximum score algorithm. She tried to look up the lead board and then tried to find out a good solution to work on her skills, and then she figured out that it is better to work on the basics. She remembered that she read a book to teach how to set up a good test case, and she likes to enhance her skills to use test case for the algorithm analysis.

The book is called "The art of readable code", chapter 14: testing and readability.

Leetcode 480: sliding window median

May 19, 2017


Work on the algorithm Leetcode 480: sliding window median, the blog is here. Leetcode weekly contest 14.

Tuesday, May 16, 2017

Leetcode 582: Kill Process

May 16, 2017

Problem statement is here.

Introduction 


It is a binary tree data structure, and it needs to use BFS/ DFS search to find all children.


Problem solving 


C# practice is here.

Leetcode discussion link is here.  Learn to get involved in Leetcode community. Share the code first.

Study code is here. One more C# practice.

Watch Googler - Yu Zhou - Leetcode videos on youtube.com.

Will write down C# practice using Yu Zhou's idea in the the video - link is here.

C# code is here.

Actionable Item


Work on the algorithm Leetcode 480: sliding window median, the blog is here. Leetcode weekly contest 14.

Leetcode 581: Shortest unsorted continuous array

May 16, 2017

Introduction



Julia likes to be a good problem solver, one thing she starts to do in this May is to solve algorithm problems every day. If she solves 2 algorithm problems a day, then one month she can finish 60 of them.

One of ideas is to work on past over 32 Leetcode weekly contest, and try to solve weekly contest algorithms. Each contest has 4 algorithms, so there are over 100 algorithm.

Top performers can solve 4 algorithms in a hour, based on the lead board of Leetcode weekly contest. But Julia sets the target to solve first easy algorithm in half hour, and then second algorithm in medium level one hour.

Problem Solving 


Problem statement is here. The algorithm is easy level. The target is to solve it in 30 minutes.

It took more than 30 minutes to come out the sorting idea, and just compare to sorted array.

C# practice is here.

Leetcode discussion link is here.

Sunday, May 14, 2017

Testable JavaScript

May 14, 2017

Introduction


As a hackerrank contest player, Julia likes to do some research on how to improve her performance. She was surprised that she could not figure out easy algorithm on Hackerrank last year, and then she posted questions on codereview.stackexchange.com, and then she quickly followed the advice. She felt more confident on easy algorithm on hackerrank contest. Here is one of questions she asked on a easy algorithm called Spiral Message.

For medium level algorithm, Julia stumbled badly on Rookie3 maximum score algorithm. She tried to look up the lead board and then tried to find out a good solution to work on her skills, and then she figured out that it is better to work on the basics. She remembered that she read a book to teach how to set up a good test case, and she likes to enhance her skills to use test case for the algorithm analysis.

The book is called "The art of readable code", chapter 14: testing and readability.

It is always a good idea to read book written by google programmers, specially short books like 200 pages.


Testable JavaScript




It is a good idea to read the book called "Testable JavaScript" again in 2017.

Choose a good fight, instead of fighting against the hackerrank contest lead board, Julia likes to follow the author, Mark Ethan Trostler, a googler by reading the book again.

The ideal case is that Julia will design the algorithm using a new school technique, by working smart on testable idea. Really focus on a small unit test case, instead of focusing on recurrence formula, analysis of the algorithm. Will try to read the book again in 2017 and see if there are some valuable ideas in the book.


Show how hard Julia tries to study the book and gather all topics she should learn again.



Book reading 



May 14, 2017 3:20 pm - 4:29 pm
Read the book from page 1 - 13, page 35 / 273, chapter one.

Chapter 2. Complexity 


Code size


Notes:

comand query separation - commands are setters and queries are getters.

internal and external names of docRoot versus realRoot


A better solution is to use private properties with public getters and setters.

Try to read JavaScript code and understand the discussion - maybe I should put the code in html page next time.
Try to complete chapter 2 reading first.

JSLint



Cyclomatic Complexity 



independent paths

jsmeter - a command-line tool


Read the article about Complexity metrics - link is here.

multiple exits -


bad fix probability

Actionable Items



Elements of JavaScript style - article link is here. Chinese translated version is here.

12 books every JavaScript developer should read - article link is here.

Read the book "The art of readable code" again. First reading is in 2014, Oct. 31, 2014.
Chapter 8: Break down giant expression - favorite example:

 Two ranges does not overlap

Saturday, May 13, 2017

Graph or permutations with constraints?

May 13, 2017

Plan to read this algorithm called "Graph or permutations with constraints?". The coding blog link is here.

Friday, May 12, 2017

Maximum Score - Rookie 3 (II)

May 12, 2017

Introduction 


It is a good idea to continue to work on maximum score algorithm, and also ask a question on code review. Learning memoization and bit mask is not an easy task, also Julia likes to learn the time complexity analysis algorithm better through the study.

Julia wrote a blog to document her learning experience on the algorithm, from the contest performance to after-contest catching up.


Code review preparation 



C# code in the contest is here. Score 3.5 of 35 points. 

May 12, 2017 11:16 pm 

Code review of C# code in the contest, and then move the memoization out-of-for-loop, scored 10.50 of 35 points. C# code is here.


Memoization Analysis Challenge


Instead of going over the recurrence formula, Julia likes to use an example to explain what can be in memoization. And what is her mistake in the contest? What is the reason causing the false analysis?

Suppose that the array has two numbers, int[] numbers = new int[]{1, 2}. The problem is to find the maximum sum such that the order of two numbers to put into scoring make the value maximum.

What is the subproblem of max score?

Guess what is the subproblem


May 13, 2017 11:03pm

First, add sum of the array. The array new int[]{1, 2}'s sum is 3.

To choose the last number, two options, either 1 or 2. If the last number is 1, array's index is 0, then the 0th score is (3 - 1) % 1 = 0. Next number is 2, sum is 0, and then the 1th score is 0 % 2 = 0. The sum of score values (0th, 1th) is 0.

In other case, if the last number is 2, array's index is 1, then the score is (3 - 2) % 2 = 1. Next number is 1, sum is 0, and then 0 % 1 = 0. The sum of score values is 1.

From the above two cases, the maximum score is 1 by taking 2 as last number and then taking 1 as the first number. Just remind friendly that the order is opposite from end to start.

The maximum value is to choose maximum value from a set with two values.

The memoization process is to record to Dictionary<string, int> calculated.
["0", 1]
["1", 0]
["", 1]


One more test case 


Suppose that the array has two numbers, int[] numbers = new int[]{1, 2, 1}.

Calculated variable as Dictionary<string, int> has the following:
[0 1, 0]
[0 2, 0]
[0, 1]
[1 2, 0]
[1, 0]
[2, 1]
[,1]

Debug the code, and check how many times the dictionary is looked up. 3 times.
key = "0 1", "0 2", "1 2".

Draw a recursion tree for this simple test case. Here is the graph:

Argument: If you can work on this simple test case and also work out the recursion tree correctly, then I believe that you can solve the problem using memoization and recursive, DP solution correctly as well.


Common advice




Do not memo one more item in one recursive call; Stay outside the for loop; Memo before return statement.

Julia, if you are very good at unit testing, and work on simple and very good test case in the design of algorithm, your performance on Hackerrank can improve at least 20%.

Make it all


It is the first challenge Julia worked on since last January on hackerrank, on the topic of bit mask, dp, memoization, subset. So she likes to make the algorithm everything. Learn one algorithm a time. Do not rush.

Julia likes to review a list of things on the algorithm. Bit mask, memoization, time complexity analysis.

Use bit mask, the code passes all test cases. 
C# practice code is here.


Hackerrank Editorial Notes


In order to write a good question on code review, Julia also have to write down some notes from editorial notes from hackerrank on the maximum score algorithm.

Here is the link of editorial notes.

Julia's note:
time complexity: O(2n * n)

Recursion tree - a major flaw, same recursive call many times; It results in exponential running time.


Actionable Items


Read book "Testable JavaScript" and then figure out a few things I can do in order to have a good sense of setting up test cases to help Hackerrank contest.

The algorithm is also on code review.stackexchange.com, the link is here.


Algorithm drill

May 12, 2017

Introduction


It is better to discipline yourself as a software programmer. How to do that in busy schedule, specially in Saturday and Sunday? Julia likes to choose old Leetcode weekly contest or Hackerrank hour rank to practice, so she can spend 60 to 90 minutes to work on a few algorithms, she plans to have some practice this Saturday.

Ideas 


Put yourself constantly in the pressure, that is the way you grow. Make it a daily grind, 1 or 2 algorithm, if you are very talent, top 10% in the world, you should be able to solve 4 algorithms in one hour. Here is the leetcode week 32 contest ranking. 90 minutes, 4 algorithm, top 72 players score full score 26 in 90 minutes. 

Leetcode 575: Distribute Candies

May 12, 2017

Introduction


Distribute candies is the first algorithm in Leetcode Weekly Code 31, Julia likes to work on one algorithm today to calm down. She misses the fun to write an algorithm right now, 9:43 pm, so she
chose last Saturday weekly contest to practice.


Distribute Candies 


Time is checked. It is 10:19pm. The C# practice code is here

Thursday, May 11, 2017

Selected algorithms on GeeksforGeeks

May 11, 2017

Plan to read some algorithms on this blog - Aashish Barnwal.


Dynamic Programming and Bit Masking

May 11, 2017

Introduction


As a hackerrank contest player, Julia has hard time to manage her performance and expectation on Maximum Score algorithm. She failed to score on Maximum Score algorithm, only scored 3.5 out of 30, 10% or so.

It is better to learn a new topic called Dynamic Programming and Bit Masking. A good player should also be a good learner. Talk about failure is easy, but find a good topic to study and write down some good notes, it takes some determination.

Life is a little boring as a programmer if every contest on hackerrank comes so easy and score 50% up so easily. It is part of journey to excellence, every 10% experience counts a good practice.

Reading an article is never so enjoyable since Julia depends on the study; one day she will document one algorithm she easily scores full score, and tonight study makes her a good thinker in bit masking.

Bit masking, Julia likes to mask things using bit manipulation. It is not that hard, Julia taught Microprocessor lab a few times from 2001 to 2004, every time she had to learn again.

Dynamic Programming and Bit Masking 



 Hackerearth.com dynamic programming and bit masking, article link is here.

Fun with bits - topcoder article study

May 11, 2017

Introduction


It is so interesting experience to play rookie 3 contest. Julia spent a lot of days after the contest to play with one algorithm called Maximum score. She wrote a blog documented her experience, and then she likes to study a topic - use bits of an integer to represent a set. The topic is about a set, and also using bit manipulation.

Fun with bits


Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union         
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

Tuesday, May 9, 2017

Bipartite graph small talk

Introduction


It is so enjoyable to learn a new algorithm every day. Also, it is also a good practice to write a small algorithm to solve a problem everyday.

Plan to read wiki article bipartite graph first, and then work on a geeksforgeeks algorithm.

The article link is here. And the geeksforgeeks.com article is "check a graph is bipartite".

Bipartite graph 


First C# practice code is here. There is a bug on line 55, 56, LinkedList RemoveFirst api should be called, otherwise the while loop will loop forever.

Second C# practice code is here. The test case in Main function is a loop with 4 nodes, so it is bipartite graph. Return true.


Add more test cases later.

Actionable Item



Read the moderator Aashish Barnwal of the geeksforgeeks.com

Read "How is it to be interviewed at Microsoft?" on quora. Link is here.

Geeks article about interview, link is here

interview cake - Julia's new school

May 9, 2017

Introduction


It is a wise decision to work on interview cake and learn how the website is designed to help programmers improve technical strength. Julia knew the website starting from February 2017.

Today, Julia read weekly email from interview cake and then spent 10 minutes to go over this link - Word Cloud Data.

Study 

Monday, May 8, 2017

Catalan number wiki article

May 8, 2017

Introduction


It is very interesting to study catalan number again. This time Julia likes to go over the wiki article and then try to get better understanding the algorithm.

Tonight she had mocking experience to learn an algorithm - find maximum number of path from bottom-left corner to top-right corner, and do not cross the diagonal line. In other words, always stay underneath the diagonal line. She learned that the algorithm is similar to Catalan number.

Catalan number 



Sunday, May 7, 2017

Recursive function design talk

May 7, 2017

Introduction


It is the 21th mocking experience this Sunday evening. Julia thought about writing about a blog about 21 mocking experience, what she has learned so far. And then she talked to herself it is better to do one thing at a time. Just talk about one mocking experience a time.

It is the middle of year, May. Julia likes to get started to work on some website project, study some pluralsight.com courses, and then practice some website technology.


Recursive function design talk 


Transcript is here

A few issues need to be addressed.
1. cheapestCost in the function name is not accurate, it should be minimalCost.
2. I should ask a lot of questions when designing the function, do I need to store all the paths? Do I need to keep track of each value on the path? Do I need only the value from the root node to the current node? Need to clarify the question.
3. The recursive function can be designed in different wasy, right now Julia chooses to use "ref minimalCost" in the function argument, but people may not have the idea to solve the algorithm.
What is the alternative way to write?

Actionable Items


Read something interesting:

Read one of article - link is here.

International Olympiad Informatics - wiki article is here

Culture Conference - Rookie 3 contest

May 7, 2017

Problem statement: Culture Conference

Introduction


It is very interesting contest experience. Julia did not write a lot of code in Rookie contest, first she decided to review Union find algorithm, studied one of C# solution first. But in less than one hour, she used the algorithm to score a full score 20 on a medium algorithm - Maximum tourism. And then she started to work on the hard algorithm called Culture conference with maximum score 55. Julia also did not have time to write code, she was busy with tennis sport 2 hours, and one hour mocking interview around 8 pm. So she decided to use same algorithm Union Find to calculate the minimum number to attend the conference, a minimum dominating set, she scored 3.5 and then made some improvement to score 5.5.

One algorithm Union find helped her to score more than 30 point on two algorithms in the contest.

Here is her submission report on the algorithm.


Code review 


C# code is here.

The function Julia worked on in the contest from line 248 to 269 is here. She tried to adjust the maximum saved people by thinking about one node with more than one child, how many can be saved to let the parent node to go to culture conference, that is children.Count - 1.

Code snippet is here:

Follow up 


May 5, 2017

After the contest, study code written in Cpp file. Code is here.
Review code and then write a C# code. Code is here.

Performance Talk - 5 points to 55 points

10:37pm May 5/2017

Performance on this algorithm is based on the points I got. I got 5 points,  5 / 55 points, it is almost 10%. It is the hard algorithm, but the solution is not that hard to figure out.

Julia has to look into the performance issue in the contest Rookie 3, and then write down some tips to improve. Simple and practical tips.

May 9, 2017

Download test case 2, and then test the C# code in the contest using test case 2, and then modified the code. It took hours to fix the issues related to union find algorithm. Code is here, still need more work. Union Find algorithm implemented only keeps every node's parent node to the disjoint set's root node. Its director supervisor is replaced with the root node. No way to get the correct answer.

May 10, 2017
Leave union find algorithm alone, add some data structure to check each node with subordinates and supervisor, similar to the study code. Therefore the algorithm can only handle those edges with burnout node with its parent, and also figure out how many people go to conference.

It is a good practice to add something to Union Find algorithm, therefore learn to solve a problem and also get chance to know more about Union Find algorithm.


Actionable Items:



Study lead board of Rookie3

Read the math Ph.D. student - a good programming on Rookie 3 - Kevin Vissuet is the profile. Resume is here to take a look.

Aaron Albin - Amazon employee

Rookie 3 on Hackerrank

May 7, 2017

Introduction


It is great morning of the Sunday, Julia woke up around 7 am and she decided to get up at 8:00 am and worked another hour for Rookie3 since the contest ends at 9 am PST. Last night she was so tired 10 minutes before 12 am, she knew that she had to go to sleep, stopped to work on Rookie3 algorithm called Culture Difference. She made 5.5 points out of 55.

Julia tried to get smart on the contest, she went out for a tennis sports around 1:00 pm last Saturday, and then come back to work on the contest around 5 pm. And then she took one hour break from 8:00 pm - 9:00 pm, and came back to work on after 9:00 pm - 12:00 pm. She learned to take more breaks and also took care of contest activities.


She could not believe that she stumbled on the algorithm Max Score and could not score more than 3.5 out 30. She just reminded herself to keep learning recursive if that is only thing she could figure out to solve the problem.

Contest review 



Here is the contest progress report at 8:53 am May 7, 2017, 7 minutes before the end. 


Culture Conference Algorithm


It is a long journey from 59.00 points to 140 points. Learn one theory behind the algorithm in the contest a time, now it is a domination set show time.

Julia did not know one of the algorithms is using minimum dominating set based on the editorial note. The dominating set was such a hot topic back to her Ph.D. study, but she never had a chance to write any graph algorithm to practice by herself. Here is the journal paper written by professor Jie Wu and Fei Dai. This is a better link to read the paper quickly.

Julia went to bed still thinking about the algorithm "Culture Conference" around 12:00 am, and woke up around 7 am and still thought about ideas to try to gain a few more points on the algorithm.

This is a really testimony of good relationship between hackerrank contest and academic research. But Julia did not know what she tried to work on is a dominating set, she tried to google but had no good keyword to search in the contest. She took a few graduate courses on network protocols in her Ph.D. study from professor Jie Wu back to year 2001, but she did not have the chance to practice one algorithm by her own. This contest made her Ph.D. study complete!




Saturday, May 6, 2017

Max Score - RookieRank 3

May 6, 2017


Plan to work on the algorithm: Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.

Follow up 


May 7, 2017 9:20am

C# code in the contest is here, scored 3.5 out of 35.

Follow up 


Study the discussion about the solution, the link is here.

1. The following implementation uses memoization, backtracking, and backward processing:

C# practice code is here which passes all test cases.

2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is here.

3. Bit mask - pass all test cases
C# practice code is here.

Bit manipulation 4 things to review

1. Get integer 2i:
//use left shift i times,
bitToCheck = 1 <<  i

2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck

3. Get ith bit:
bitmask |= bitToCheck,

4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck


4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is here.
string.Join(",", bitmask) takes too much time.

Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].

5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.

Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.

Algorithm analysis


It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.

The maximum score of k problem can be solved by choosing any number as the last kth number, and then work on the maximum score of - 1 problem. Use bitmask as key to do memoization.


Actionable Items


Review previous practice, and find some cases to use bitmask.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union        
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

2. Hackerearth.com dynamic programming and bit masking, article link is here.

Friday, May 5, 2017

Union Find Algorithm - one hour workout

May 5, 2017

Introduction


It is a good idea to have my own union find C# class and also put some test cases together for future use.

Here is the article to talk about union find in details on hackerearth.com.

Here is the blog to document the study on the topic.

Here is the blog to document more than one hour study on union find algorithm in world codesprint 10 contest.

Union Find Coding


It is in incognito mode, Julia did not share any code because she played the Rookie3 contest.

Follow up 



May 7, 2017 9:27am

Julia spent hours to test the union find algorithm, and planned to apply the algorithm to solve one of Rookie3 contest algorithms. She just applied the test case in less than one hour and solved the algorithm on Rookie3, score 25 point very easily. She did not have chance to look into the detail of the algorithm. 

May 10, 2017

Code review C# solution, and C# code is here

The path compression is implemented in the above algorithm. Every node's parent node is set to the root node of tree.



Maximal tourism - rookieRank 3

May 5, 2017

Introduction


Problem statement is here. Plan to work on the problem.

Code study 


Follow up 

May 7, 2017 9:22 am

Code submission in the contest is here. Score fulls score. 

Julia did not write any code, she reviewed union find algorithm and tried to get some experience of union find C# code, she just used the algorithm to test her union find code as the second test case.






Thursday, May 4, 2017

Algorithm learning small talk

May 4, 2017

Introduction


It is very interesting to read the article called "when pressure and off-court life overcome talent and results". The article link is here.

It is more exciting to practice coding and attend contest in the weekends. Julia enjoys the contest and also likes to push herself to join the community and share what she can do. Here is the blog to show her ask code review on a hard level algorithm in Hackerrank world codesprint 10 recently.

Julia had a mocking experience tonight, she had a big surprise about learning a dynamic programming algorithm.

The problem is a very ordinary solution using dynamic programming, recursive solution.

The deletion distance of two strings is the minimum number of characters you need to delete in the two strings in order to get the same string. For instance, the deletion distance between "meat" and "mit" is 3:
  • By deleting 'e' and 'a' in "meat", and 'i' in "mit", we get the string "mt" in both cases.
  • We cannot get the same string from both strings by deleting 2 letters or fewer.

Less means more 


How to analyse the above algorithm? 

Use frog and dog as an example, we have two words, we like to linear scan two strings from left to right, all starts from the beginning. First chars of two strings are 'f' and 'd'. If they are equal, then both pointers go to next one. Otherwise, we have to move one of pointers. Both cases should be counted. In other words, 'd' is deleted, then continue to work on two strings: "og" and "frog"; or 'f' is deleted, then continue to work on two string: "dog" and "rog". 

So far, the analysis is perfect. We cannot sort the string, because the order is important and has to be kept. The count of char does not help much. The brute force solution is not good since it will be O(n2), actually it is hard to find a brute force solution.

In other words, recursive function can be written in the following recurrence formula:

CalculateDeletionDistance(s1, s2) = CalculateDeletionDistance(s1.substring(1, length1 - 1), s2.substring(1, length2 - 1)) if s1[0] == s2[0];

Make it short, CalculateDeletionDistance is shorted as CDD, s11 is the substring of s1, s21 is the substring of s2.

CDD(s1, s2) = CDD(s11, s21) if s1[0] == s2[0],
CDD(s1, s2) = 1 + Math.Min(CDD(s1, s21), CDD(s11, s2)) if s1[0] != s2[0]

Basically the recursive function is depth first search, base case should be calculated the deletion distance. And then in order to save time, it is better using bottom-up solution, called dynamic programming method.

Edit Distance Algorithm


Previous practice on Leetcode 72 is here. Spend 20 minutes to review lecture note from standford again. Also plan to spend 30 minutes to review Leetcode discussion, link is here.

Julia was wondering if the dynamic programming is also solvable using DFS algorithm.

Actionable Items


Plan to read the article on topcoder: Dynamic Programming - From novice to expert, the link is here.

Read the facebook engineering manager - Yi Huang's linkedin profile.

Take some notes from the recommendation:

Understand to build a hobby - writing code, solve problems on topcoders:

"Numerous times we turn to each other to discuss algorithm and optimization problems and every time I am impressed how insightful Yi can be. Yi has won countless programming awards and takes coding as a serious hobby. Yi has great enthusiasm in algorithm optimization. His hobby is to log into topcoder and attack one problem after another. He also has the great ability to apply research knowledge to actual programming. He is one of the few guys that will always think of how to turn research results into reality."



Wednesday, May 3, 2017

Communication drills

May 3, 2017

Introduction


It is very interesting to work on communication skills. Julia started to follow tennis professional player interviews, Julia likes Sharapova's perfect English, but she also started to like players with French accent, Spanish and German's accent.

One thing Julia likes to learn is to get more ideas about thinking process of professional tennis players. Every player uses those terms about controllable, mental game, and shares their mind and problem solving process through tough matches.

Communication drills


Her most favorite talk on May 3, 2017 is here.

Djokvic

Defending champion Djokvic Seeking Freshing Start in Madrid 2017. 5 minutes video is here.

Notes: changing coaching team, love tennis sports, competition or practice.
Mental? Ten years behind me, so much success, gain a lot of experience. Use those experience for practice, future matches, confidence is tricky thing, long time to build it, quick to lose it. You have doubt, and you have to deal with it. How to approach that? Not change a lot.

Ambitious person, go back to basics, analyze the game, believe the result will follow.

ATP world Tour Stars React to Djokovic Coaching Decision - link is here. 3 minutes video

Mladenovic

Mladenovic Press Conference After Match vs Sharapova - Stuttgart 2017, 13 minutes video.


Siegemund

Siegemund Press Conference After Final vs Mladenovic - Stuttgart 2017, 5 minutes video.


Julia saw Siegemund practice in China Open, Beijing 2016 October. She knew that the professional player was so focus in the practice court, and also very sociable with fans after the practice.

Take notes:
Find ways to solve the problem, think small units to do.