code review: Hackerrank kindergarten adventures

March 19, 2017

Problem statement

Code review is posted here.

C# code - still work on more test cases on API testing, Modify and Query.

Introduction

Julia starts to learn binary index tree and segment tree through hackerrank university codesprint #2 in November 2016, she tried a few times but failed each time. She knew that she is better to work on the algorithm "kintergarden adventure" and learn from the algorithm.

She also did post the question on segment tree algorithm on code review to ask help on Dec. 10, 2016, and then the question "kintergarden adventure" was closed. Through the incident, Julia knew that she was afraid to learn by herself.

Julia is very comfortable at data analysis, so in order to figure out the algorithm, Julia chose to have some test case study, put together some data, and then taught herself what to look for through those tables.

Test case study

For example, there are 20000 students in the circle, and the first student only need to 0 minute to finish drawing, so that if the teacher starts from any students from ID = 1 to 20000, the first student can complete the drawing. SegmentTree class Modify API has to take the task to mark those 20000 nodes as value 1, it is not scalable for 3 seconds time limit, so that we can use up to logN intervals to cover the range of [1, 20000].

To make it simple, we assume that the range's width is 1024 instead of 20000, and see how many steps we need to mark in tree[]. Not up to 1024, but in the level of logN = log1024 = 10.


Here is the SegmentTree class Modify API: To understand the test case, in order to modify 1024 nodes as 1, we only do it in less and equal to 10 times, here is the two images to explain the detail.

The two variables of left and right are iterated from beginning to end 10 times, each iteration two variables's values are recorded in the table.

Let us get our hands dirty on this test case, RunTestcaseModify3() line 12, tree.Modify(0,1024,1). We look into the function call.

First row of table, left = 20001, right = 21024, since Modify API is called and function arguments: start = 0, count = 1024, value = 1,
read Modify API code line 5 and line 6, left is calculated as 20001 and right is calculated as 21024.

and more detail is here:

Action items

Review code review Hackerrank Modular Range Queries
Read the tutorial of segment tree.
Learn binary index tree from topcoder

Inspiration

This is the first time Julia started to use Microsoft Excel to do some test case analysis to help her understand the segment tree algorithm design.

All it takes is for her to have some patience. She read those two tables built by Microsoft Excel, and then she asks herself what is missing, what problems she can tell from those data. After a few times search, she comes out ideas to move forward her study.

Segment Tree - kindergarten adventures algorithm - Make my mark

Dec. 14, 2016

Problem statement:
https://www.hackerrank.com/contests/university-codesprint/challenges/kindergarten-adventures

Introduction:
Kindergarten adventure algorithm is the algorithm on HackerRank university codespring contest in November, 2016, and it is medium level difficulty. Julia spent over one hour to think about the algorithm in the contest, but she did not come out the idea using binary indexed tree or segment tree to solve it. After the contest, she likes to master the algorithm.

The Previous two blogs about the algorithm and solutions:

HackerRank - university codesprint - kindergarten adventures (after the contest)

http://juliachencoding.blogspot.ca/2016/11/hackerrank-university-codesprint_16.html

Here is one C# solution she chose to study, here are her workout experience:
1. Put some analysis together,
2. Review code
3. Put together a new version
4. Share on stackexchange.com code review section.

https://gist.github.com/jianminchen/c3abd1d967c58132023b7235b69fdcdd

5. Post the question on the stackexchange.com as well.

Post the question on stackexchange.com code review:
http://codereview.stackexchange.com/questions/149613/hackerrank-university-codesprint-2016-kindergarten-adventures

6. StackExchange.come code review feedback:

put on hold as off-topic by Peilonrayz, forsvarir, BCdotWEB, Vogel612, t3chb0t 2 days ago

This question appears to be off-topic for this site. While what’s on- and off-topic is not always intuitive, you can learn more about it by reading the help center. The users who voted to close gave this specific reason:

• "Questions must involve real code that you own or maintain. Pseudocode, hypothetical code, or stub code should be replaced by a concrete implementation. Questions seeking an explanation of someone else's code are also off-topic." – Peilonrayz, forsvarir, BCdotWEB, Vogel612, t3chb0t

8. Julia knew that she has to work on one algorithm a time, and this algorithm takes time. She started her own practice, failed 3 times:

8.1. Wrote my own version of segment tree, first try: 2.18 (maximum score 30)
only pass 4 test cases.
https://gist.github.com/jianminchen/3fc3df275c903e94b780e1612f0171f6

8.2. Second practice, score 1.08 max-score: 30, pass test case 0 and 1.
https://gist.github.com/jianminchen/98f38cfb31bace070184b641c95d14b9

8.3. Third practice, score 0  max-score: 30, pass test case 0, 1
https://gist.github.com/jianminchen/1411dc08a2a2c059454f788add19bceb

It is a really good study case for understanding depth of problem solving. Timeout issue is critical, at the beginning of construction of segment tree, the time complexity should be O(n^2), not O(n), n is the people in the group, n < 100000.

Better score 0 to write your own code, comparing to copy other's code score 30. Do not underestimate your own practice, the mistakes made, time spent all counts to the good learning experience.  

8. Go back to the study code C#: 

https://gist.github.com/jianminchen/c3abd1d967c58132023b7235b69fdcdd

And google and try to find some article to help.
The solution is classical, some one already did research how to store the value in segment tree most efficient way, almost O(n) to build up a segment tree.

Find the article using similar idea: 

http://codeforces.com/blog/entry/18051?

Workout: 

1. Show some graph on analysis of solution provided:

2. Get out from the first breakdown on stackexchange.com code review: 
Have some sports therapy - 30 minutes 

Watched the video of Genie Bourchard interview twice while she did some stretch in the living room, for a sports workout. 
Eugenie Bouchard Live: 
https://www.youtube.com/watch?v=w02BSPblBEs&t=320s

(Eugenia is a young player, 20 years old when she was interviewed. She talked about in the interview Nick is her great coach, when she was 12 years, she was taught how to deal with mental issues in sports - stay at moment on the court, no matter what happens )

Do not be lazy. Work hard, fail a few times and then get better. Julia, if you are in uncomfortable zone, that is the learning zone. Do not miss the learning opportunities.

Fail to post, the algorithm written is not mine. Need to come out my own solution first, and then, get code review. Tried various solutions, failed all times. Get to know the algorithm better.

And then, Julia gave her 30 minutes therapy, chose one of top tennis players to motivate herself. Work on algorithm is not easy, to be competitive, Julia has to learn what to work on. No shortcut. Hands on experience, stay at moment. When practice, make as many mistakes as you can. If you can afford the time. 

Segment Tree - kindergarten adventures algorithm - code review

Dec. 10, 2016

Problem statement:

Introduction

Kindergarten adventure algorithm is the algorithm on HackerRank university codespring contest in November, 2016, and it is medium level difficulty. Julia spent over one hour to think about the algorithm in the contest, but she did not come out the idea using binary indexed tree or segment tree to solve it. Julia was very lucky to find a C# solution actually implemented using segment tree.

The Previous two blogs about the algorithm and solutions:

HackerRank - university codesprint - kindergarten adventures (after the contest)

Julia found out that her learning of binary indexed tree is missing most important part, the experience to play and learn from a simple concrete example; she read a lot about segment tree, or binary index tree, but she needs to have some time to play with an example, have some fun. The skills will come afterwards, she believes.

Here is one C# solution she chose to study, here are steps:
1. Put some analysis together,
2. Review code
3. Put together a new version
4. Share on stackexchange.com code review section.

C# code

Plan to work on the algorithm 2 hours. Dec. 10, 2016, 11:36am - 1:36pm

Put some references together for further study.

Workout

C# code - Julia tries to figure out how to build a segment tree through sample test
case:
3
1 0 0
The segment tree in an array: {0,0,2,2,1,1}

Segment Tree:

C# code

Julia's concerns about segment tree:

Questions:

1. Why does Modify function skip one and only add value on odd number?

Line 114 - line 125,

        public void Modify(int start, int count, int value)
        {
            int size = tree.Length / 2;
            int left = start + size;
            int right = start + count + size; // open border

            for (; left < right; left >>= 1, right >>= 1)
            {
                if (left  % 2  == 1) tree[left++]   += value;
                if (right % 2 == 1) tree[--right]  += value;
            }
        }

2. How does the range of start/ end to be determined on this simple test case: 1 0 0?

Line 87 - Line 93:
private static SegmentTree BuildTree(int n, int[] extraMinutes)
    {
        var tree = new SegmentTree(n);
        for (int i = 0; i < n; i++)
        {
            int curr = extraMinutes[i];
            int len  = extraMinutes.Length;

            if (curr >= len) continue;

            int start = (i + 1) % len;
            int end   = (i + extraMinutes.Length - curr) % len;

            if (start <= end)
                tree.Modify(start, end - start + 1, 1);
            else
            {
                tree.Modify(start, len - start, 1);
                tree.Modify(0,     end + 1,     1);
            }
        }

        return tree;
    }

Why start = (i+1) % len? Guessing,  i = 0, ID counts from 1 to 3, not starting from 0.
Why end  = (i + extraMinutes.Length - curr) % len;

3. Question:
Study Query API: Why skip the root node?
for loop, i > 0

Line 132 - Line 139:
public int Query(int index)
        {
            int res = 0;
            int i = index + tree.Length / 2;
            for (; i > 0; i >>= 1)
                res += tree[i];
            return res;
        }

Actionable Items

Julia, only way, better way to learn segment tree, binary index tree, is to work on an algorithm, and then, ask good questions to yourself, and then, post the question on the stackexchange.com as well.

Post the question on stackexchange.com code review:

Code review is here. The code review was closed.

It is not acceptable to ask help to understand other people's code. That is the rule from stackexchange.com. Do not be lazy. Work hard, fail a few times and then get better. Julia, if you are in uncomfortable zone, that is the learning zone. Do not miss the learning opportunities.

Fail to post, the algorithm written is not mine. Need to come out my own solution first, and then, get code review. Tried various solutions, failed all times. Get to know the algorithm better.

1. Wrote my own version of segment tree, first try: 2.18 (maximum score 30)
only pass 4 test cases.

C# practice 1

2. Second practice, score 1.08 max-score: 30, pass test case 0 and 1.

C# practice 2

3. Third practice, score 0  max-score: 30, pass test case 0, 1

C# practice 3

It is a really good study case for understanding depth of problem solving. Timeout issue is critical, at the beginning of construction of segment tree, the time complexity should be O(n^2), not O(n), n is the people in the group, n < 100000.

Better score 0 to write your own code, comparing to copy other's code score 30. But do not understand the design and algorithm. 

References

1. Read the lecture note to help:

Lecture note to study.

2. Read the article about segment tree.

Lintcode 79: longest common substring

July 26 2016

Work on lintcode: longest common substring.

Problem statement:

Given two strings, find the longest common substring.

Return the length of it.

Note

The characters in substring should occur continiously in original string. This is different with subsequnce.

Algorithm Study

Study the blog - longest common substring (60 minutes reading first time/ 20 minutes review every 6 months) written by a facebook engineer, Ider Zheng. Julia likes the article written in Chinese, it is a well-written and very good thinking process about the problem solving.

Julia likes to repeat the process here in her own words.

1. Brute force solution -> from O(n⁴) to O(n³), great analysis in the above blog:

Good thinking addes value to your coding practice:

Warmup with a brute force solution:

Time complexity - O(n⁴)

For example, a string s1 = "abcdefg",

One way to think about brute force:

The length of string is 7.

How many substring in s1? Guess?

Substring - start position and end position, two variables. Each one has O( n ) choices. Total is O(n²) choices.

More detail, start position can be any i from 0 to 6, and then end position starts from i to n-1. The variation formula, Sum = (n - 1) + ( n - 2) + ... + 1 = (n-1) n / 2, so the total is O(n²);

Try to reduce brute force variation from O(n²) to O(n), instead of letting start position and end position
both varies, just work on start position only.

Small improvement based on brute force solution

Time complexity - O(n³)

Second way to think about using brute force:
The start position of substring is from 0 to n-1, so considering the start position, start a new search.

So, the total of search is O(n).

 Longest common substring - start from start-position, and then  compare both of chars are equal, if yes, continue, record length and compare to maximum length, else then break the search.

1. C++ code:

Code is from the blog written by a facebook engineer.

The time complexity is O( n³ ). There is duplicated calculation.

Will write C# practice very soon.

Dynamic programming - optimal time complexity O(n²)

2. Use Dynamic programming, in the above blog, the analysis is very helpful.

Work on dynamic programming, improve time complexity from O(n⁴) or O(n³) to O(n²), using memorization, space O(n²), bottom up approach.

The idea is to find the formula of DP - dynamic programming.

table T(i, j) - common substrings, using end position as a variable.


one is in s1, ending at position s1[i];
one is in s2, ending at position s2[j].

We know that if T(i, j) >0, then, s1[i] = s2[j];
if(s1[i+1] == s2[j+1]), then, T[i+1, j+1] = T[i,j]+1,
otherwise, T[i+1,j+1] = 0.

Will think about to put together a graph here to explain the idea as well.

2. C++ code:


From blog: C++ code
DP solution, time complexity O(nm), space O(nm)


3. further improvement: C++ code
DP solution, time complexity O(nm), space O(nm) -> O(n+m) -> O(1)
because the recurrence formula tells us that the current position only relies on diagonal position - left-up corner ( i - 1, j - 1)
https://gist.github.com/jianminchen/0061dcf562bd0bdb091301241c38730f

From blog

Julia's practice:
1. brute force solution C#
A. first writing, static analysis catching 1 bug, left 2 bugs for debugging. (not so good!)

B. fix all bugs - final presentation: C#

2. Dynamic programming solution using C#:


Highlights of code writing and execution:

1. static analysis - find bugs
change made: line 56 - 61, if the longest common substring is with length 1 and also start from row 0 or col 0.

line 67 - 72

2. Test case failed on line longestCommonSubstring("abc1def","1ghijkl") - should be "1",

change made: move end1 variable to line 49, and set variable from line 56 - 61, line 67 - line 72

2nd version: add comments


3. DP solution with space reduction: O( nm ) -> O( n+m )  -> O( 1 )

practice later.

* Design issues:
         *
         * 4 variables - memo, longest, end1, searchFirstRowCol
         * 1. memorization using two dimension array - memo
         * 2. variable int longest - get maximum length
         * 3. variable int end1    - string s1 - end position - s1's substring end position
         * 4. variable bool searchFirstRowCol - check first row and first col to update maximum length

DP problems:

Follow up after 8 months

March 17, 2017

1. Read code review on longest common substring algorithm.
2. Read wiki article about "Algorithm Implementation/Strings/Longest common substring"
3. Blog formatting to make it more readable. 
4. Code review:

Ashton and String Hackerrank

Coding practice is like sports - I don't feel fear when I am on court. That's where I feel at home.

I don't feel fear when I am on court. That's where I feel at home #CreateYourMark #RG16 @adidastennis @adidasFR pic.twitter.com/ZVNcZvWZE0

— Kristina Mladenovic (@KikiMladenovic) May 20, 2016

Leetcode 269: Alien Dictionary

June 15, 2016

Leetcode 269 Alien dictionary

Choose to work on a graph problem - using Topological Sorting:

Study C++ solution:
http://www.cnblogs.com/jcliBlogger/p/4758761.html

Discussion about the problem description:
https://leetcode.com/discuss/53997/the-description-is-wrong

Study C++ solution:

https://leetcode.com/discuss/54024/straightforward-c-solution?show=54024#q54024


Java solution to study:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/269.alien-dictionary.java

http://www.cnblogs.com/yrbbest/p/5023584.html

Julia worked on C# code:
https://gist.github.com/jianminchen/07546625d828f63e762ba03b463fe8aa
line 75, 76, after queue.peek() is called, need to call dequeue. (dead loop)

https://gist.github.com/jianminchen/a49496ea21cadcbdda7c1669216c05a5

Add more comment, where to be careful, to avoid bugs:
https://gist.github.com/jianminchen/47f516b54686080c3a68bc8c3f1d04cb

More comment, variable name refactor:
https://gist.github.com/jianminchen/85129ed50ce597f896b0f0c5a2fa5586

Read blogs:
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

Comparison between 2 versions:
variable name change: graph -> dependencyList, more meaningful. The graph has nodes, dependency list, inDegree array.

Change function name: getCharSet -> getNodes

Love those comment, so helpful to get start to coding...

Left side first implementation:

for(int j=0; j < shortLength; j++)

{

...

break;

}

confusing, not very easy to follow. line 154 - line 176, 22 lines of code. The big scope to handle. 

Also, this for loop is nested loop, too many lines of code inside. 

Replacement of while loop is short, only 3 lines of code. 

graphSetup -> what we can tell here? ... later!

Question and answer:
1. Can you work on a simple example to explain the idea of your solution?

Here is the warm up for topological sorting using two strings {"wrt","wrf"}:

Review previous blog:

http://juliachencoding.blogspot.ca/2016/04/leetcode-208-course-schedule.html

Warmup practice:
statistics: 1 bug, more than 60 minute to write. Totally new program
https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733
a few changes to highlight:
1. line 24 - 26 add comment what to do about graph
2. line 49 - 65 motivation talk - help to design the function
    using the graph above {"wrt","wrf"}, help to write code
3. line 72 - 74 special case words length is 1
4. line 81 - line 85 use one pointer to slide forward <- more flat code
5. line 87 add comment - no edge -> very good comment
6. line 91 - 94 first writing with a bug - prev, curr, but prev twice

Here is the comparison file:
https://github.com/jianminchen/Leetcode_C-/blob/master/Leetcode269FirstAndSecondPractice.pdf

Statistics:
time spent: 3hours +

I don't feel fear when I am on court. That's where I feel at home #CreateYourMark #RG16 @adidastennis @adidasFR pic.twitter.com/ZVNcZvWZE0

— Kristina Mladenovic (@KikiMladenovic) May 20, 2016