Thursday, May 25, 2017

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 


Question 69: Median of a stream (Julia's ranking:  10 out of 10  May 31, 2017)

Leetcode 295. Find median from data stream - discussion panel is here.

C# solution using SortedSet. The C# code to study is here.

C# solution using MinHeap/ MaxHeap - self defined. The study code is here.

Read blog about the discussion again - link is here - the blog on ardendertat.com



Question 85: binary tree is balanced? (Julia's ranking:  8 out of 10  May 31, 2017)


Algorithm 90: Given an array, check whether it contains a subset of numbers whose sum equals to 0

A little confused about solution discussed in the book, look up Google and then find this blog on geeksforgeeks:
Dyanmic programming / Set 25 ( Subset Sum Problem), recursive and also dynamic programmng solution.

Study leetcode 416: partition equal subset sum. The problem link is here.

Amazonian - USC alumni - Xie Tao - Leetcode profile is here.

Study the solution:
Java dynamic programming solution is here.

Study Leetcode 39: Combination Sum,
Julia's C# practice is here.

Leetcode 40 Combination Sum II.

Julia's C# practice is here.


Algorithm 93: Maximum in Queue

Leetcode 239 Sliding window maximum

Algorithm 98: Most profit from stock
June 8, 2017
Leetcode 121
Julia's C# practice is here. 

Leetcode 122
Julia's C# practice is here. 




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".

Follow up 


April 16, 2017
Mocking experience, reverse words in a string, C# code is here.

June 20, 2017
Mocking experience, reverse words in a string, C# code is here.

Julia learned the lesson how to work on linear scan array hard lesson through Leetcode contest in May, she spent over 40 minutes on one algorithm, and then she read the idea to spend 5 minutes less to write very clear solution. The blog is called Leetcode 605: Can plant flower.


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.

June 13, 2017

It is very good experience to write sudoku in mocking experience, this is the third time Julia worked on Sudoku for mocking experience.

Julia put the code into Visual Studio to compile and here is her C# practice code.

Here are two mistakes in writing through mocking experience:

One compiler error in mocking writing, line 61,
add type conversion by adding (char), and also (number + '0')

line 61  board[row, col] = (char)(number + '0'); // add '0'

One compiler error, duplicate variable inside for loop on line 82, change col to column; line 91, row is changed to rowIndex.

Try to pass online judge, and then find the bug on line 84, 93, 111. C# code is here.

line 84 if (board[row, column] - number == '0') // should be '0', not 0



Actionable Item



Julia still remembered that she got some great advice on her second mocking experience using Sudoku, and then she was coached by the peer to use DFS starting from (0, 0) and set the base case to row > 8.

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.

Build a ritual to do white board testing, and write down the test case next to each line of code.


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.

June 22, 2017

Julia's C# practice 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 mock 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 mock experience today, and then she likes to do some research, the topic is "Can mock make difference?"

Study 


Mock interview makes difference.

Things Julia learned through mock 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 mock interview. 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 mock 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 mock 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 mock experience, the experience taught her to be super patience.

Last 3 year she only did around 40 mock 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 mock 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 mock 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+ mock interview experience, 40+ mock interview experience, one algorithm 3+ mock interviews, 5+ mock interviews,

30+ mock experience:

40+ mock experience: You start to ask what if you are a professional interviewer, interview more than one thousand people already? What are you looking for through the candidates?

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

one algorithm the first mock -

one algorithm 1+ mock - 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+ mock - You cannot believe how busy you are. After 3+ mock on same algorithm, you look into related algorithms. For example, Leetcode 33, 153, 189. You reviewed the discussion on leetcode for different opinions.

one algorithm 5+ mock - No matter how busy you are, you will start to look into the algorithm, try to understand various solutions. Big surprise for Julia to learn Leetcode 10 recursion tree related issues.

70+ mock interview experience - Julia met a peer and the peer asked to work on the extended problem since the algorithm is easy and quick recursive function.

Leetcode weekly contest makes difference - Julia learned the performance lesson 5 minutes vs 48 minutes on easy algorithm, so she applied her learning quickly and shortened the time to 5 minutes writing in mock as well in June - Leetcode 151.

90+ mock interview experience - It is also a good idea to extend the problem for very competitive peer, change the algorithm if you think that peer will accept it. For example, inorder BST successor can be solved using/ without parent node pointer,  there is Leetcode algorithm Inorder Successor. A few of discussions are very detail on how to use DFS search to find the solution.

Always get prepared. Prepare extended question until the peer will fail, then you can measure how deep the strength the peer has.

100+ mock interview experience - It is the first time to learn how to give good advice on hard algorithm Leetcode 10 problem solving, try to explain recursion branches concept. Julia practised over five times Leetcode 10 algorithm.

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 k - 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.


Maximum Disjoint Subtree Product - World codesprint 10 (II)

May 3, 2017

Introduction


The algorithm is one of hard level in the hackerrank world codesprint 10. Julia put together a C# code after she chose to study one of C# submissions in the contest. She likes to ask code review on stackexchange.com.

The algorithm is a depth first search algorithm, after over a few hours study, the algorithm becomes easy to understand.

Here is the C# code almost ready for code review.


Code review 


Code review link is here.

Monday, May 1, 2017

Facebook product engineers

May 1, 2017


Watch the 30 minute video, product engineers from Safety Check, News Feed, and Videos. The link is here.

Array patches

May 1, 2017

Plan to study the algorithm called array patches. It is written in Chinese. Will find the similar algorithm written in English. The link is here.

Problem statement: Given an ascending sorted integer array nums and an integer n, add a few of elements so that any number in the range of [1,n] can be expressed as the sum of a few elements in the array, ask for minimum elements to add into the array.



Facebook - reflecting on 2016 and looking forward to the new year

May 1, 2017

Introduction


It is such a good video to watch, Julia watched two times. Each takes 16 minutes. The link is here.

It feels so good to spend one hour to study Facebook as a company, and Julia had to learn new things Facebook are developing today.

Video study 


Take some notes here.