HackerRank: Bear Steady Gene (II)

March 4, 2016

  Problem statement:

https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene  

A gene is represented as a string of length n (where n is divisible by 4), composed of the letters A, C, T, and G. It is considered to be steady if each of the four letters occurs exactly n4 times. For example, GACT and AAGTGCCTare both steady genes.


Julia's 1st practice:

https://gist.github.com/jianminchen/80723bae951328a690bb

score 15 out of 50, there are 2 run time error, failed a few of test cases.

The algorithm ends up in time complexity O(n^2), close to brute force solution - O(n^2)

C# code implementation to study:

Readable code, with some analysis.

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

Work on two pointers, sliding window, so time complexity is O(2n) = O(n).

Let us go over two pointers algorithm here using example:
GAAATAAA,
A - count of A, denoted as cA = 6, n/4 = 2, so we have to change 4 of A to other thing.
A - 6 -2  = 4 , 4 of change
C - 0 - 2 = -2
T - 1 -2  = -1
G - 1-2  = -1
So, at least minimum is 4, but a substring containing 4 of A, shortest one is AAAA. But "AAAA" is not a substring of "GAAATAAA"

G  A A A T A A A
0
start
end
Let us find the substring starting from 0, but will include all 4 of A, and then, rest of string will not include any char of "ACGT" more than n/4.
GAAATA, string length is 6.
start - 0, index of 0
end - A, index of 5

continue to move start to next one, 1, then, G is moved out from substring, adjust count of chars.
AAATA can be the substring, so the length is min (6, 5) = 5. Do not need to move end pointer.

next step, start = 2, missing one of A, and then, end has to move to next one until the string fits into requirement.

Every thing should be covered in 20 minutes, problem reading, the design of algorithm, the coding.

So, Julia had second practice, and the code scores 50 out of 50 this time.

https://gist.github.com/jianminchen/61dfe437f82edb9793fc

Conclusion:
After coding, Julia understands the algorithm much better.

1. count of array for substring, cB=[4, -2, -1, -1], so in other words, substring has to contain at least 4 'A', C, G, T does not matter.

So, using CB array, sliding windows of substring GAAATA, each time, end index is moving forward, tracking the substring's char by taking off from CB; in other words, GAAATA, CB will be
[0, -2, -2, -2].

Now, it is easy to understand that GAAATA will be added to the solution set, the length is 6.
line 51, if (cBAllLessThan1(cB)) 
<-add substring to solution set, compare length<- easy to understand now.

2. the code in https://gist.github.com/jianminchen/fae9142eff9a6f9643fc has discussion:

switch(line[0]) {
	case 'A': A--; break;
	case 'C': C--; break;
	case 'G': G--; break;
	case 'T': T--; break;
	}

Julia removed those detail discussion, but her code takes more time. Because she created a bug in her writing. Debugging takes time.

3. Julia's practice in 2015, sliding windows, two pointers:
http://juliachencoding.blogspot.ca/search/label/slide%20window

April 27, 2016
change C# program to make variables more meaningful, matching the design:
code -> GENES <- global string array
function name matches design of two pointers moving.

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

searchStrArray -> searchStrNumber, more meaningful.
https://gist.github.com/jianminchen/b23c4f606a101b9aeec71eff3268db32

HackerRank: Bear and Steady Gene (I)

March 4, 2016

  Problem statement:
https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene

  Editorial:

Let's first think when Limak can choose some particular interval (substring). We should care about the remaining letters, both in the prefix and the suffix. If there are more than n/4remaining letters of one type then we can't get a steady string. Otherwise, we know exactly how many letters of each type are missing and we can fill the removed interval with these exact letters. So, the interval can be chosen only if the remaining part doesn't contain more than n/4letters of some type.

For each possible starting index of the interval let's find the nearest (leftmost) possible ending index. You can create four segment trees, one for each letter. Then, for fixed interval you can check in O(1)whether there are at most n/4 remaining letters of each type. So, for each starting index you can binary search the earliest good ending index. Segment trees and binary search give us O(nlog2n). Let's make it faster.

First thing is to get rid of segment trees. It's enough to store prefix (and maybe suffix) sum for each letter, so you don't need segment trees anymore. It's ok to get AC but you can change one more thing. As we move with the starting index to the right, the ending index also moves to the right (or it doesn't change). So, we can use the two pointers technique to get O(n) solution. You can check codes below for details.

Julia's practice:
https://gist.github.com/jianminchen/80723bae951328a690bb

score 15 out of 50, there are 2 run time error, failed a few of test cases. The implementation is no better than brute force solution.

C# code implementation to study:

https://gist.github.com/jianminchen/153eab0defae014842e8

Readable code, with some analysis.
https://gist.github.com/jianminchen/fae9142eff9a6f9643fc

Java code implementation to study:
https://gist.github.com/jianminchen/d52ced38de0bffa2d9e8

C++ code to study:
https://gist.github.com/jianminchen/d7370b7e73013ee708be

write this one as well <- Great code, very readable!
https://gist.github.com/jianminchen/c6b51207f9cc9b083573

https://gist.github.com/jianminchen/80638c0db328d0098f3b

Binary search algorithm: (Java)
https://gist.github.com/jianminchen/d01faa03ca9b06696db3

Comment:
The brute force solution will not pass the test cases. 

It takes a lot of time to read 108 people's code - all scores 50 / 50. It is fun to read all 108 solution scoring 50/50.

Julia, take time to play with this algorithm.


Nov. 28, 2016

Study the code:
https://gist.github.com/jianminchen/c4f1c84c984e58fdcdc467e6f28d84e3
code review:
1. line 26, int[] a = new int[1007];
1007 is not meaningful, we know the size should be bigger than 'Z', and we only need the array of size 4
2. variable i and index are not meaningful. There are two loops.
3. valid function from line 49 - line 58
   line 52 - 55 - four constant chars are used.


Review the code and make the change:
https://gist.github.com/jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b
1. line 26 - 36, add 4 test cases, with 4 postcondition assertions
2. function name is changed to minChange
3. line 61, array of size 4 is declared instead of 1007
4. function indexOf() is added
5. variable names are changed, left, right, two pointers, move forward only
6. add two explanation variable c1, c2 to advoid complicated expression.
7. valid function is declared using a for loop.

Based on the code review on this post:
http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853
answered by Eric Lippert

HackerRank: HourRank 6

March 2, 2016

Introduction 

  Problems statement: Lisa's work book.

  Julia spent more than 1 hour to work on first question on HackerRank: HourRank 6, Lisa's workbook.

  It's a one-hour rated contest with 3-4 algorithmic challenges. Are you fast and accurate enough to win it? 

  So, by any means, Julia finished the first algorithm, and passed all test cases. 20 minutes to read the question, and then, 20 minutes to write, and over 20 minutes to debug, fix bugs to pass basic test case. 


   Here is the code she wrote:

Julia's C# practice in the contest. 
  

   So, she read other people's code. Best performers in top 20 use less than 5 minutes. 

Code study 

  Julia read a few of great code to use loops. So, she now has more ideas to implement the algorithm. 

  Her favorite ones:

  No. 1 (#6):  

 Code study No. 1, code is here. 
       

 No. 2 (#12):

 Code study No. 2, code is here. 
   

 No. 3  Julia's favorite solution -

 Code study No. 3, code is here.
 

Actionable items

   1. Work on basics - for loops; Julia, learn from others - basic C programming, it is quick and fast. 

   2. C++, less time to write compared to C#. 

  3. A lot of room to improve, 
60 minutes -> 20 minutes, <- reading time from 20 -> 5 minutes. 
20 minutes to 10 minutes,  <- clean code, no bug. 
20 minutes to 5 minutes. 

   4. It is like the sports. Julia, you have to practice. 

Some workout:
No. 1 (#6):  
    Code study, link is here.
 

Add some comments to the solution:

No. 2 (#12)

Study code is here. 

Julia added some comment besides the code.   



No. 3

study code is here. 

Julia added some comment besides the code. 

Mock interview experience

March 1, 2016

  Julia likes to document her first mock interview using C# on March 28, 2016. She got this question to be interviewed: BST Successor Search.

  Given a node n in a binary search tree, explain and code the most efficient way to find the successor of n.

Analyze the run time complexity of your solution.

How did Julia work out the problem with the help from the interviewer? 

Julia was nervous, so she did not think too much. Ask to discuss the successor. What is the successor? 

Then, she was told that a tree

   4

3   5

4' successor is 5, and 3's successor is 4. 

Julia should work on some test cases, and make complete understanding of algorithm first. 

But, she did not. 

She was told to write some code about it. Julia then asked to start from root node, and then, was told that Node class:

Class Node{

   Node left; 

   Node right; 

   Node parent; 

   int value; 

}

So, the function has to take argument node n - any node in the tree, instead of root node. 

code with bugs - work on simple BST: 

 4

3   5

4' successor is 5, and 3's successor is 4. 

https://github.com/jianminchen/AlgorithmsPractice/blob/master/BSTSuccessor_Step1.cs

And then, here are the conversations:
Interviewer: There will be more than 1 cases failing;
show a tree
       4
   2
       3

  3's successor is 4, not null. 2 is left child of 4, and then 3 is right child of 2. Go up to parents.

Julia: So, if we work on the following tree, will all bugs be fixed? 

                    4

              2          6

            1   3      5    7

Interviewer: 3's successor is 4, and 4's successor is 5, not 6. 
Julia: Ok, let me add two more functions to help. 

For node 3, the successor of 3 is 4.  // to fix bug, add function checkRelationship while retrieving grand parents. 
For node 4, the successor of 4 is 6. // to fix bug, add function called getLeftMostNode()

https://github.com/jianminchen/AlgorithmsPractice/blob/master/BST_Successor_Step2.cs


The interviewer asked Julia cleaned up the code, removed unnecessary variables, put return statement in while loop. 

At the end, the interviewer told that Julia was the best one; he interviewed 7 other people, maybe using the same question. Julia was so excited, motivated after hearing the feedback. Julia, she did write very clear, readable code, with logic perfect through mock interview. 

And then, Julia was asked the run time analysis. The balanced search tree, the run time is O(logN), but if it is not balanced, can be up to N. 

But, lessons learned:
1. Always work on test cases, discuss algorithm, make sure both agrees, then, start to write code; 
2. Work on simple test case, and then, extend the algorithm to fit the complicate case. 
3. Start from simple case, write code to make it work on simple case. 
    And then, discuss bugs, and fix the bugs with more functions. 
    It took 28 minutes to finish most of coding. 
4. Julia was too nervous, she could not think about successor clearly at the beginning. So, she asked to have some discussion about successor. Interviewer showed her one simple example. 


    Surprisingly, write in two steps, make the coding so easy. 

Angular - put a web app together in short future

March 1, 2016

  So busy to study courses on pluralsight.com and code school, try to build a web app in short future. Here is the short video to get motivated to use Angular.

  https://channel9.msdn.com/Events/Visual-Studio/Connect-event-2015/051

  https://channel9.msdn.com/Events/ASPNET-Events/ASPNET-Fall-Sessions/Brad-Green-from-Google?ocid=player

Mental toughness training - small talk how to perform algorithm as well

Feb. 29, 2016

  Julia went through mental toughness training in her tennis practice by herself last 5 years. She has played over hundreds of single/ double tennis matches ever since. Every time, she failed over and over again on mental toughness checking - her mind just does its own trip - being distracted, thinks about the win/ loss, things happened at work/ church/ friends/ family, she reminded herself, recovered and focused on the current, back to sports, current game, current point - it is tough, that is the reason called mental toughness training. Do not even think about this game, this set, or last point, only this current moment.

  In more technical term, mental toughness is - Only think about what she can control, stand on the ground, current moment, thing is happening right now.

  Good thing is that she develops the great attitude to live at the moment, and kick some depression ass/ negative thoughts' ass, and then be a super happy and smart person again.

  How about algorithm problem solving skills? coding skills? One of her problems is to deal with algorithms problem solving in one hour. How does she stay in the current moment, spend one hour?

  She still feels frustrated after a week, but she takes time to think about it.

  Here are her action items:
  1. Try to solve easy problem always. 
  2. Have some training - fast coding, on hackerRank.

 

Pluralsight: AngularUI Fundamentals

Feb. 10, 2016

AngularUI Fundamentals

3 hours video lectures

http://stevemichelotti.com/new-pluralsight-course-yeoman-fundamentals/

reading:

https://github.com/angular-ui/ui-router/wiki