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

Blogs Reading: Algorithm problems

Feb. 28, 2016

Julia likes to use interview questions to broaden knowledge, make herself a good thinker. 

http://dandreamsofcoding.com/2014/03/18/dissecting-an-interview-question/
http://dandreamsofcoding.com/2015/01/09/dissecting-an-interview-question-math-is-hard/
http://dandreamsofcoding.com/2014/08/01/dissecting-an-interview-question-reconstructing-a-tree/

Action items:
Julia, you should write down some notes, and put your 2 cents in. Entertain the ideas from the author.

Randomly selected question: (spend 30 minutes to think, Feb. 26, 2016)
http://www.spoj.com/problems/BFBASE/

February 26, 2016
https://www.hackerearth.com/druva-sdet-hiring-challenge/problems/

https://www.hackerearth.com/algorithms-qualifiers-round-1/problems/

code challenge: count of substring

February 28, 2016

Problem statement

Problems solved in the progression of coding:
1. Runtime error - exceed time limit
   naive solution - compare each substring if it contains 00 or 11
2. Console.ReadLine only reads up to 256 chars, the input is up to 100000 chars.
3. Recursive calls - stack overflow - string length is up to 100000
4. Using iterative solution to replace recursive solution

First, wrote a solution in 20 minutes, but Time exceeding limit - TLE error.
Solution 1: C# code


Solution 2: C# code

So, write second version using recursive to avoid redundant calculation: stack overflow problem

Solution 3: C# code

Then, wrote third version with iterative solution:

Solution 4: C# code
(HackerRank embedded C# executable - wrong answer, but Visual express is ok! Cannot figure out! )


Spent more than 4 hours on this easy question. Totally invest 3 hours nonstop on Sunday afternoon on this problem solving.

What we say to encourage this behavior - have guts to fail. This is just the practice.

March 7, 2017

Need to review last practice and find out a solution.

HackerRank: Pangram

Feb. 28, 2016

  Work on the pangram problem on hackerRank. Julia spent 20 minutes to work on the solution.

  Problem statement: (Easy question)
  https://www.hackerrank.com/challenges/pangrams

  Also, read the topic:
 https://www.hackerrank.com/challenges/pangrams/topics

  Here is Julia's practice.
  https://github.com/jianminchen/HackRank/blob/master/pangram/Pangram.cs

 

HackerEarth: first algorithm practice - Milly Chocolate

Feb. 26, 2016

Spent more than 1 hour to work on an algorithm problem on HackerEarth.

Problem statement:
https://www.hackerearth.com/druva-sdet-hiring-challenge/algorithm/milly-and-chocolates-4/

Milly loves to eat chocolates. She buys only those food items which contain some amount or percentage of chocolate in it. She has purchased N such food items and now she is planning to make a new food item by her own. She will take equal proportions of all of these N food items and mix them. Now she is confused about the percentage of chocolate that this new food item will have. Since she is busy in eating the chocolates so you have to help her in this task.

Input

First line of the input will contain T (no. of test cases). Every test case will contain two lines. First line will contain N (no. of food items) and the second line will contain N space separated P_i values denoting the percentage of chocolate in i^th food item.

Output

For every test case, print the percentage of chocolate that will be present in the new food item.

Note : Your answer should be exactly up to 8 decimal places which means that if your answer is 2.357 then you have to print 2.35700000 or if your answer is 2.66666666 .... then you have to print 2.66666667

Constraints

1 <= T <= 5
1 <= N <= 5*10⁵
0 <= P_i <= 100

SAMPLE INPUT

1
3
80 30 90

SAMPLE OUTPUT

66.66666667

Time Limit: 1 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded if any testcase passes.

Allowed Languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Julia's practice:
1 second for each file, but, the time is over 1 second. Need to work on speed! (Julia likes the challenge! )

https://github.com/jianminchen/hackerEarth/blob/master/MillyandChocolates/MillyAndChocolate.cs

Julia read editorial of algorithm, and know the better solution:

https://www.hackerearth.com/problem/algorithm/milly-and-chocolates-4/editorial/
(will try her own version as well later. Definitely, the code will take less time to write! Good learning tool - Thanks, hackerEarth!)

So, to fix TLE error ( more than 1 second for each file), Julia wrote a bug free version:
https://github.com/jianminchen/hackerEarth/blob/master/MillyandChocolates/MillyAndChocolate_BugFix.cs

Read this web page:

https://www.hackerearth.com/@pranjuldb/activity/hackerearth/

Julia's hackerEarth profile:

https://www.hackerearth.com/@jianminchen.fl

React and Flux for Angular Developers

February 25, 2016

 Spent 1 hour to watch video on pluralsight.com.

 "React and Flux for Angular Developers" by

 Read something related to catch up ideas about coding using React.js.



 

Algorithm contests? Competitive programming?

Feb. 24, 2016

 Algorithm contests are great tools to use. It takes more critical thinking, and more attention to detail in order to gain points. Julia did two easy questions on two hackerRank contests last weekend, she could not perform on easy question in 20 minutes each. She actually spent over 60 minutes, hard to concentrate, felt stressed. So, she did some research and look into articles talking about programming contests and how she can improve in short time: 

 3 popular contests sites:
 1. HackerRank
 2. TopCoder 
 3. CodeJam

Her favorite article detailed on this - Preparing for a technical interview with programming contests:
https://www.facebook.com/notes/10151298476823920

• You’ll learn how to critically analyze your work. Because you don’t get credit for solving a problem until the code you write can generate the correct results for a large input set (and you don’t know what that input set looks like), you’re forced to think about things such as time complexity, memory usage, and nasty corner cases. Importantly, most of this work happens outside the context of a debugger. Debuggers are invaluable tools for figuring out why a given piece of code is buggy, but it’s better if you can write bug-free code in the first place. In an interview situation, candidates who can’t statically analyze their code generally have trouble showing their solution is correct (or figuring out why it’s not).

https://medium.com/@dpup/whiteboarding-4df873dbba2e#.ps92c99lb
https://code.google.com/codejam/contests.html
https://code.google.com/codejam/contest/6224486/dashboard#s=a&a=0 
http://blog.hackerrank.com/3-ways-crush-technical-interview/
https://www.quora.com/How-has-competitive-programming-helped-you-get-a-job
http://www.redgreencode.com/12-reasons-to-study-competitive-programming/
https://www.quora.com/What-is-the-best-strategy-to-improve-my-skills-in-competitive-programming-in-2-3-months

https://www.quora.com/How-did-Anudeep-Nekkanti-become-so-good-at-competitive-programming

Things to do in next month:
Work on contests every week, 2 - 4 hours. Try to aim for 20 hours experience first.

Mock interview experience (I)

February 23, 2016
   
 Julia never had chance to give other people code interview before, and then, she will have one. Excited! Finally, she got her first experience.

 Algorithm for the interview being an interviewer:

 Find The Duplicates

Given two arrays of US social security numbers: Arr1 and Arr2 of lengths n and m respectively, how can you most efficiently compute an array of all persons included on both arrays?

Solve and analyze the complexity for 2 cases:
1. m ≈ n - lengths are approximately the same
2. m ≫ n - one is much longer than the other

 Julia worked on the question by herself first, around 20 minutes (no coding) before she reads :

1. Brute force solution, time complexity: O(nm), go through two loops, in other words, go through Arr1, and for each element in Arr1, check if it is in Arr2. 

2. Can we do better than O(nm)? Of course. 

case 1: m ≈ n - lengths are approximately the same

  sort Arr1, it takes time O(nlogn); 

  and then, for each node in Arr2, find it is duplicated one in Arr1. Use binary search, each search takes O(logn), m elements, so time complexity is O(mlogn)

  So, time complexity in total: O(nlogn) + O(mlogn) ≈ O(nlogn), which is better than brute force one: O(nm) time complexity

  <-  Julia, you missed another important step: Ask if the arrays are sorted or not? 

  <-  Julia, if two arrays are sorted, what is the optimal time complexity? 
        Linear time <-  O(n+m) <- you missed the opportunity to ask yourself the question. 
  <-   Julia, algorithm time complexity - How to say that? Level 1 (sorted array time complexity), level 2, asking level 2 in detail (assuming that two arrays are sorted, now what? linear vs nLogm vs n^2). 

HackerRank - New School - JavaScript

February 21, 2016

Just sign up JavaScript week 2. It is a new year - 2016, make JavaScript programming language my favorite language. Spend time to play with code challenge on JavaScript.

Read more about JavaScript and get prepared.

To entertain - learning more about JavaScript:
http://rauschma.2ality.com/publications.html

Speaking JavaScript:  (read online)
http://speakingjs.com/es5/index.html

HackerRank - New School - Nice code sprint on algorithm challenges

Feb. 21, 2016

Sign up for another test:

Juniper coding challenge
  https://www.hackerrank.com/juniper-codesprint

Work on 4 questions:
https://www.hackerrank.com/contests/juniper-codesprint/challenges/leonardo-and-substring

The blog documented her experience:
http://juliachencoding.blogspot.ca/2016/02/code-challenge-count-of-substring.html

HackerRank - New School - Algorithm: Fix the cycles

Feb. 21, 2016

Another 2 hours on hackerRank:

Fix the cycles:
Problem Statement:
https://github.com/jianminchen/HackRank/blob/master/fixTheCycles/fix-the-cycles-English.jpg

Solution:
There are 4 cycles which share same edge: D->A, so if set D->A big enough then any cycle can be positive.

4 cycles:
A B C D  A
A C D A
A B D A
A C D A

Simple solution.
30 minutes to read - take too long!
10 minutes to write code,

https://github.com/jianminchen/HackRank/blob/master/fixTheCycles/FixCycles.cs

Short term target of training on hackerRank:
Easy question,
reading time: 10 minutes,
code time: 10 minutes.
Know how to fix bugs, make more points

New School - HackerRank - algorithm: Beautiful Pairs

February 21, 2016

HackerRank is Julia's new school -  her new lover.  But problem statement is too long to read, and the test cases are not very clear.

Julia starts a new journey with HackerRank, she likes the algorithm problem solving. She spent 2 hours on Sunday morning to work on an easy problem in a "101 Hack Feb 2016".

Here is the question:

Beautiful pairs

Problem Statement 
 

Here is her answer with a bug - failed 2 of 6 test cases:
   

Performance review:

  40 minutes - calm down, read problem statement - she has to understand the problem first.

  Failed 2 cases - that is the value of HackerRank  - good practice.

Lesson learned:
  20 minutes coding,
  20 minutes bug fix: Array size: 1000->1001 to remove run time error,
  the score: from 3.8 to 15.80.
  Wrong answer for 2 test cases.

 Here is the perfect version - fixed the bug.
 

Conclusion:

Each school is different, HackerRank is cool! Julia, just be humble. Make mistakes, always work on easy question, work on the first one in next 5-10 practice. One question a time.

Julia, you have to go through hackerRank contests, go through training - the article detailed on this:

• You’ll learn how to critically analyze your work. Because you don’t get credit for solving a problem until the code you write can generate the correct results for a large input set (and you don’t know what that input set looks like), you’re forced to think about things such as time complexity, memory usage, and nasty corner cases. Importantly, most of this work happens outside the context of a debugger. Debuggers are invaluable tools for figuring out why a given piece of code is buggy, but it’s better if you can write bug-free code in the first place. In an interview situation, candidates who can’t statically analyze their code generally have trouble showing their solution is correct (or figuring out why it’s not).

https://medium.com/@dpup/whiteboarding-4df873dbba2e#.ps92c99lb
https://code.google.com/codejam/contests.html
https://code.google.com/codejam/contest/6224486/dashboard#s=a&a=0

Be a better programmer to grow in your current job -

http://blog.hackerrank.com/3-ways-crush-technical-interview/
http://dandreamsofcoding.com/2014/03/18/dissecting-an-interview-question/
http://dandreamsofcoding.com/2015/01/09/dissecting-an-interview-question-math-is-hard/
http://dandreamsofcoding.com/2014/08/01/dissecting-an-interview-question-reconstructing-a-tree/

Leetcode 312: Burst Balloons

February 17, 2016 

Spent 10 minutes to work on an example, int[] A = {1,2,3,4,5}, and see how to work out maximum coins? 

Need to figure out Dynamic Programming formula, how to get the analysis done in a reasonable way? The problem is rated as medium, hard. So, take time to figure out. Since most of questions are easy to medium, let Julia put some creative, passion and other important things into the analysis, get more confident on hard questions.  

Feb. 18, 2016 continue to work on the analysis
One phrase Julia likes is "Things have to do is called stress, but thing love to do is called passion". Make this analysis is Julia's first passion practice - how to approach the problem? 

Try to work on brute force solution first. 
work on example, int[] A = {1, 2, 3, 4, 5}
First one to burst, 5 choices:any one of them, so 
case 1: burst 1, left: {2, 3, 4, 5}
        2: burst 2, left: {1, 3, 4, 5}
        3: burst 3, left: {1, 2, 4, 5}
        4: burst 4, left: {1, 2, 3, 5}
        5: burst 5, left: {1, 2, 3, 4}

And choose max value from the above 5 case. Each case is a subproblem, find max value from array size of 4. <- not exactly <- ? Julia, miss something important here 

Use start, end index of array, and max value is denoted as P(start, end)
so, P(0, 4) can be divided into 5 cases:
case 1: burst 1, left: P(1,4), how to calculate the value, A[0], A[1], P(1,4), value = A[0]*A[1] + P(1,4)
case 2: burst 2, left: P(0,0), P(2, 4), value = P(0,0) + A[0]*A[1]*A[2] + P(2,4)
...
case 5: burst 5, left: P(0,3), value = P(0,3) + A[3]*A[4], 

So, the max value is P(0,4), the value is max value of subproblems. Formula: 

 max{P(0,k-1) + product(k) + P(k+1,n)}, k = 0,1,.., n

Now, the dynamic programming formula is constructed. 

So, write the design of DP - memorization, P(start, end) - declare two dimension array vector[n][n] 

Feb. 19, 2016 
Still need to work on implementation, go for DP - how to build loops?
Go for recursive solution - 
Go for Divide and Conquer solution - 

Here is the blog she starts to read.

  http://bookshadow.com/leetcode/

  https://www.hrwhisper.me/leetcode-algorithm-solution/

  http://www.cnblogs.com/grandyang/p/4606334.html

  http://www.cnblogs.com/EdwardLiu/tag/Leetcode/

  http://www.jiuzhang.com/problem/

Similar problem like Floyd shortest distance.

Pluralsight: Responsive In-Browser Web Page Design with HTML and CSS

February 16, 2016

So good to come cross this course, and then spend 3 hours to catch up responsive design in CSS. Save me a lot of time to catch up CSS/ responsive design.

Pluralsight:

Responsive In-Browser Web Page Design with HTML and CSS

https://app.pluralsight.com/library/courses/responsive-browser-web-page-design-html-css-2262/table-of-contents

A lot of thing to read:
https://css-tricks.com/scale-svg/  (Feb. 21, 2016)