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. 

Leetcode 310: Minimum Height Trees

   Leetcode 310: Minimum Height Trees

   https://leetcode.com/problems/minimum-height-trees/#

    read the blog:

    http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/

    https://leetcode.com/discuss/71656/c-solution-o-n-time-o-n-space

    http://likemyblogger.blogspot.ca/2015/11/leetcode-310-minimum-height-trees.html

  http://buttercola.blogspot.ca/2016/01/leetcode-minimum-height-trees.html

  To be continued.

Algorithm: Possible Triangle

February 8, 2016

Possible triangle
http://www.geeksforgeeks.org/find-number-of-triangles-possible/

http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

Argue about how to reduce time complexity from O(N^3) to O(N^2), how exactly i, j, k three variable, k is only from 0 to n-1 once for each i, nothing to do with j. So, it is time for i - from 1 to N, and time for j from 1 to N two loops, and then for i - N, and k from 1 to N ( skip j - big point! Cannot figure out easily. )

To be continued. 

Algorithm: Write a function to detect if the string has the unique character

February 8, 2016

So excited to have chance to write code for a new algorithm. 

Write a function to detect if the string has the unique character. 

Read the blog: 

http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking

this blog provides good answers for the question of unique character:

Notice that this method doesn't allocate an array of booleans. Instead, it opts for a clever trick. Since there are only 26 different characters possible and there are 32 bits in an int, the solution creates an int variable where each bit of the variable corresponds to one of the characters in the string. Instead of reading and writing an array, the solution reads and writes the bits of the number.

Julia's comment: first blog about bit manipulation - surprising, after the reading, it is much easy to understand the code: 
Two bit operation: 
1<< val 
 |=  

It is always helpful to write a few of small function:

int toInt(char c)
{
    return c-'a'; 
}

int OneShiftLeftNbits(int val)
{
   return 1 << val;
}

int checkNthBit(int val)
{
     // ...
}

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

http://javahungry.blogspot.com/2014/11/string-has-all-unique-characters-java-example.html

To be continued.

Leetcode 295: Find median from data stream

February 8, 2016

It is always very important to write some code and then get the experience to master a new algorithm. 

Leetcode 295: Find medium median from data stream 

Segmentfault.com article about median algorithm 

- great algorithm discussion about median algorithm design using two heaps - one max heap, one min heap, in Chinese language. 

Julia gist about code

Leetcode 295 solution blog by buttercola


Julia, read Java priorityQueue class and get some ideas about the class design:

programcreek.com priority queue class example

stackoverflow - how do I use a priority queue in java


understand priority queue first, read the lecture notes:

WSU.edu heap lecture notes

To be continued. 

Follow up after 12 months

April 3, 2017

Work on heap as a data structure.

Leetcode 331: Verify Preorder serialization of a Binary Tree

 Feb. 8, 2016

Serialization of a binary tree, great algorithm to review.

331. Verify Preorder serialization of a Binary Tree

One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where# represents a null node.

idea: Use stack


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/

 To be continued. 

Leetcode 329: Longest increasing path in matrix

February 8, 2016

problem statement:

Given an integer matrix, find the length of the longest increasing path.From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

329. Longest Increasing Path in a matrix

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

idea: go through each node in the matrix, BFS search, and get minimum one;

read blog:
http://bookshadow.com/weblog/2016/01/20/leetcode-longest-increasing-path-matrix/

June 20, 2016

1st practice using C#: 

https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4
blog:
http://juliachencoding.blogspot.ca/2016/06/leetcode-329-longest-increasing-path-in.html

Leetcode 328: Odd Even Linked List (Easy)

February 8, 2016

328. Odd Even Linked List (Easy)
Julia's comment: think about O(N) space solution first (using array, and then, easy to go through), and then, work on O(1) space solution, the following blog helps:
http://www.cnblogs.com/EdwardLiu/p/5138199.html

To be continued.