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)

Sunday: Reading time (3)

February 13, 2016

  Being a software programmer, Julia likes to improve her English along the way. She started to bring writing into her daily life, write a small topic making sense everyday. She enjoyed reading the blogs today:

http://randsinrepose.com/archives/weblog-writing/
http://www.amazon.com/gp/product/0596155409?ie=UTF8&tag=beigee-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0596155409
http://randsinrepose.com/archives/what-to-do-when-youre-screwed/


  Here is the video she watched:
  Robert Johnson's Top Rules For Success (African billionaire - own TV  network)
https://www.youtube.com/watch?v=HaUe-YGAK_E

1. Build relationships
People like to do business they like
2. Get the capital you need
3. Keep Revenues up, costs down
4. Make Friends Before You Need Them
5. Stop Consuming, Start saving
Debt: you consume more than you are worth.
Postpone unnecessary, impulsive spending
6. Stand for something
7. Get to scale
8. #Believe in yourself 
People follow leader, people invest on leaders
Sense of confidence, sense of leadership
9. Make hard choices
People cannot afford the bill in restaurant, keep ordering, or until he can run away avoiding the bill. 
10. Partner with suppliers
Trade equity with services.

Mark Cuban: Only Morons Start a Business on a Loan

https://www.youtube.com/watch?v=KYneLGRTgy8

Mark Cuban's Advice to High Schoolers and College Grads

https://www.youtube.com/watch?v=UgdNTzul27k
For high school graduate, do not pay overpriced education to get into debts over 40,000.
For graduate, you may not get best job. You paid money to learn. Now it is your chance to get paid to learn.
You do not need perfect job, you can make some money, also you can learn, add to your profile of knowledge and add to your foundation. As much as we want, know exactly, what mission of our life is, chosen profession going to be in 20 years, You are get paid to learn, and learn more about yourself, and business, and see what it takes.

Mark Cuban: The best advice I never got

https://www.youtube.com/watch?v=XuCCBiYLoDw

Mark Cuban's 12 Rules for Startups

https://www.youtube.com/watch?v=camXWnD4QcI
1. Don't start a company unless it's an obsession or something you love
2. If you have an exit strategy, it's not an obsession.
3. Hire people who  you think will love working there.
4. Sales will cure all.
Know how your company will make money and how you will actually make sales.
5. Know your core competencies and focus on being great at them. Pay up for people in your core competencies. Get the best.
6. An espresso machine? Are you kidding me? Coffee is for closers. There are 24 hours in a day, and if people like their jobs, they'll find ways to use as much of it as possible to do their jobs. 
7. No private offices
Open office spaces keep everyone in tune with what's going on and keep the energy up. 
8. About technology
9. Keep the organization
If you have managers reporting to managers in a startup, you will fail. 
10. Never buy swag. 
A sure sign of failure for a startup is when someone sends out logo-embroidered polo shirts. 
11. Never hire a PR firm 
Whenever you see any information related to your field, get the email of the person publishing it and send them a message introducing yourself and the company. They'll welcome hearing from the founder instead of some PR flack. 
12. Make the job fun for employees. 
Keep a pulse on the stress levels and accomplishments of your people and reward them. 

The 7 Sleep habits of Successful Enterpreneurs
Sleep affects moods, increases risk of psychiatric disorders and depression, cardiovascular disease and lowers immune system health. 
1. Avoid alcohol before bedtime
2. Turn off electronics before bedtime. 
3. Write your worries away. 
4. Create the perfect ambience. 
5. Exercise (release serotonin, dopamine to brain)
6. Avoid sugar before bedtime, but select protein and fat
7. Wake up to the light. 

Larry Page Q&A Zeitgeist Americas 2012 (38 minutes)

https://www.youtube.com/watch?v=4Mzlp6mIaC4&feature=youtu.be
Google map, no-one driving car, Android device, tradition education, youtube, etc.

Mark Cuban at USC | Full Interview | 2015

https://www.youtube.com/watch?v=fs9Gr8Gj6Cg

Give out advice: Remember 3 things, key to success:

1. Find something you love to do, good at it.
2. Put yourself in other people's shoes. Think about for other people.
3. The way to succeed is to remove the stress around you. Those people start to work with you, and then you just do the work.

Video watching: The Future of Analytics

Feb. 10, 2016

Spent one hour to browse through the linkedin profiles, and then, she came cross the profile of Joseph Sirosh - Corporate Vice President, Data Group at Microsoft (https://www.linkedin.com/in/joseph-sirosh-39803b1), and learned a few things through the search. Watch this presentation:

The Future of Analytics
Speaker: Joseph Sirosh
https://channel9.msdn.com/events/Cortana-Analytics-Suite/CA-Suite-Workshop-10-11SEP15/The-Future-of-Analytics

Julia likes the presentation, the metaphor used in the talk: about 30 years ago, tailor to customize the clothes for each one; now, mass manufacturer for all body shapes. So, data analytics now is like 30 year clothing industry, but in the future, it is not a big deal.

http://www.pcworld.com/article/3006609/why-microsofts-data-chief-thinks-current-machine-learning-tools-are-like-tailored-shirts.html

And she likes the music in last 2 minutes in the above presentation. Remind her the favorite song:
Genie Bouchard 2014 Montage
https://www.youtube.com/watch?v=JZJ8K5857dk

Leetcode: Longest increasing subsequence

February 8, 2016

Leetcode: Longest increasing subsequence

http://blog.csdn.net/kenden23/article/details/17632821

spend 10 minutes to read the blog:

http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73075

http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

Previous blog:

http://juliachencoding.blogspot.ca/2015/06/dynamic-programming-longest-increasing.html

Write some C# code for this algorithm later.

http://buttercola.blogspot.ca/2015/12/leetcode-longest-increasing-subsequence.html

NLogn solution, better than DP solution, Recursive solution

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Set Goals:

1. Know how to solve it using recursive solution first;

2. And then, understand DP solution, how to build the formula, avoid duplication;

3. And then, know where to find optimal solution here, O(nlogn),

Julia, write some code - That is most important!

To be continued.

February 11, 2016

     More important, work on brute force solution first, and then, come out ideas to improve. Coding is next stage. 

Julia likes to work on the algorithm by herself, not depending on her experience/ memory of solved problems. So, she tried in 20 minutes to come out the idea:

Write down her analysis steps roughly:

1. Think how to use brute force solution first, 

For array 0-n, brute force solution, how many choice for length 1 subsequence - choose 1 from n,

length i subsequence - choose i from n, and then, in total, it is 2^n calculation

2. next, she thought about and had difficulty to write down and developed the idea, in 10 minutes, she decided to work on an example to help, easily she did figure out one algorithm besides brute force:
Given an array, size of 7, int[] A = {1, 8, 3, 2, 5, 4, 7}

for subarray of size 6,  1, 3, 5 - longest increasing subsequence, maximum 3, so longest one for size of 7 is 1, 3, 5, 7

But, if the array is changed to: 1, 8, 3, 2, 8, 4, 7, and then, maximum subseqence of subarray (size of 6) has two choices:

        1, 3, 8  <-    because 7 <8,  no increment

but, 1, 2, 4  <-    because 7 > 4, increment 1,  so longest subsequence is 4, so need to maintain all the sequences with length 3

And then, try to record the number of each element in the array - maximum value ends to i

1    8   3   2  8  4  7

1    2   2   2  3  3  4  <--  so, when you work on 7, you can check value ends on 3 first, to see if it can make 4, otherwise, go for 3, decrease one by one. extra space is O(N)

one more example:

2    8   3   1  8  4  7

1    2   2   1  3  3  4  <--  so, when you work on 7, you can only check value ends on 3, extra space is O(N)

Julia, that is the way you should work on the algorithm. There are thousands of problems, you cannot spend time on each one of them, you have to learn how to solve a new problem by yourself. And later, write down your improvement on the original thoughts. 

     Think about space to store the value - array, extra map for key - value list. To simplify, just go through the array from 0 to i-1, and then, compare A[i] to A[j] (j from 0 to i-1), if it is bigger, then compute maximum value. O(N^2) time complexity. 

February 12, 2016
Work on the DP solution formula - how to calculate the value based on previous one

Formula of DP: 

And then, one more advance to optimal solution (read the blog and get the idea:
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/):
For each sequence ends at same distance, for example, 2, you only need to keep the minimum one for future to compare, 

Here is the detail:

2    8   3   1  8  4  7

1    2   2   1  3  3  4  

Length =1
2
1

Length = 2

2 8
2 3

what if only keep 2 3, 

Length = 3

2 3 8 
2 3 4


so, for every length, keep the minimum value sequence, save space, reduce time complexity. 

How much advance in time complexity for this work? 

Julia, you are very close to the optimal solution! 

    

Leetcode 316: Remove duplicate letters

    Leetcode: Remove duplicate letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Blogs to read: 

http://bookshadow.com/weblog/2015/12/09/leetcode-remove-duplicate-letters/
3 solutions are discussed in the following blog:

https://www.hrwhisper.me/leetcode-remove-duplicate-letters/

https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

     http://buttercola.blogspot.ca/2016/01/leetcode-remove-duplicate-letters.html

     To be continued.