Monday, February 8, 2016

Leetcode 310: Minimum Height Trees

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


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/

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.

Leetcode : Wiggle Sort

February 8, 2016 

 Wiggle Sort 

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.

https://segmentfault.com/a/1190000003783283
public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况:奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }

To be continued.

Leetcode 319: Bulb Switch

February 8, 2016 

319 Bulb Switch 
http://www.cnblogs.com/grandyang/p/5100098.html

Analysis from the above blog:
那么我们来看这道题吧,还是先枚举个小例子来分析下,比如只有5个灯泡的情况,'X'表示亮,‘√’表示灭,如下所示:
初始状态:    X    X    X    X    X
第一次:      √    √    √    √    √
第二次:      √     X    √    X    √
第三次:      √     X    X    X    √
第四次:      √     X    X    √    √
第五次:      √     X    X    √    X
那么最后我们发现五次遍历后,只有1号和4号锁是亮的,而且很巧的是它们都是平方数,是巧合吗,还是其中有什么玄机。我们仔细想想,对于第n个灯泡,只有当次数是n的因子的之后,才能改变灯泡的状态,即n能被当前次数整除,比如当n为36时,它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同,括号中前面的数改变了灯泡状态,后面的数又变回去了,等于锁的状态没有发生变化,只有最后那个(6,6),在次数6的时候改变了一次状态,没有对应其它的状态能将其变回去了,所以锁就一直是打开状态的。所以所有平方数都有这么一个相等的因数对,即所有平方数的灯泡都将会是打开的状态。
那么问题就简化为了求1到n之间完全平方数的个数,我们可以用force brute来比较从1开始的完全平方数和n的大小

To be continued. 

Leetcode 322: Coin Change

February 8, 2016

Julia likes to build a good fun memory about dynamic programming design, coding experience. Let this one - coin change build up good memory about Dynamic Programming. 


322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html

这道题只让我们求出最小的那种,对于求极值问题,我们还是主要考虑动态规划Dynamic Programming来做,我们维护一个一维动态数组dp,其中dp[i]表示钱数为i时的最小硬币数的找零,递推式为:
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
其中coins[j]为第j个硬币,而i - coins[j]为钱数i减去其中一个硬币的值,剩余的钱数在dp数组中找到值,然后加1和当前dp数组中的值做比较,取较小的那个更新dp数组
To be continued. 

Sunday, February 7, 2016

Leetcode 318: Maximum Product of Word Length

February 7, 2016

There are a several of stages to go through on Leetcode 318 problem solving today. 

10 minutes to read question and think about solution, confused about requirement(以为包括子字符串) ->
20 minutes to read blogs to understand solutions -> 
10 minutes to know the detail to implement (1) -> 
20 minutes to implement without bugs (2) -> 
10 minutes to implement with more clear code with bugs (3) -> 
10 minutes debug to read code again, debugging to pinpoint bug -> 
60 minutes to work on a better idea - optimal idea (5) -> 
work on exceeded time issues (20 minutes, instead of 60+ minutes) (6)

Action items:
1. Always work on coding, using Visual Studio. Try to improve coding. 

Leetcode 318: Maximum Product of Word Length 
Given a string array words, find the maximum value of length(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/ 

Solution 1:
直接看看每个字符串都包括了哪个字符,然后一一枚举是否有交集:
  • 有交集,则乘积为0
  • 无交集,乘积为 words[i].length() * words[j].length()
Julia's practice: 

Solution 2:
其实因为全部都是小写的字母,用int 就可以存储每一位的信息。这就是位运算
  • elements[i] |= 1 << (words[i][j] – ‘a’);   //把words[i][j] 在26字母中的出现的次序变为1
  •  elements[i] & elements[j]    // 判断是否有交集只需要两个数 按位 与 (AND)运算即可
read the blog to understand bit operation, take some time to refresh the memory:
http://www.cnblogs.com/onlyac/p/5155881.html


在一个字符串组成的数组words中,找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母,在这里字符串由小写字母a-z组成的。
对于这道题目我们统计下words[i]的小写字母a-z是否存在,然后枚举words[i]和words[j],找出max{Length(words[i]) * Length(words[j]) }。

小写字母a-z是26位,一般统计是否存在我们要申请一个bool flg[26]这样的数组,但是我们在这里用int代替,int是32位可以替代flg数组,用 与(&),或(1),以及向左移位(<<)就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111,“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000,这样两个进行与(&)得到0, 如果有相同的字母则不是0。
Here is julia's practice:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_B.cs

Read the webpage about precedence and order of evaluation:
https://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx

Solution 3:
Just for fun, write another version of bit manipulation implementation, but Julia created 3 bugs in the row before she writes a correct version.
Instead of using two words do not contain same char,
if ((s1 & s2) == 0) return true;

she tried to write a version to check any char from a to z, one by one check version:
https://github.com/jianminchen/Leetcode_C-/blob/master/318MaximumProductOfWordLength_C.cs

Design takes practice. She thought about and then wrote, and then failed 3 times!


Sunday - Reading time (2)

February 7, 2016

Favorite time to read, learn and understand business world. Have some coaches. Today, Julia writes down another 10 rules to success, Marcus Lemonis.

Marcus Lemonis
https://www.youtube.com/watch?v=Ty0L1rkjl5w

1. Make business plan
get a piece of paper, write down the idea, and get feedback:
Here is my product and service.
Here is how I attack the market.
Here is how I beat the competition.
Here is how I learn from my competitors.
Here is I take from my customers.
Here is the people I need to surround myself with.
Answer those questions.

2. Have enough working capital

3. Create a to do list for tomorrow
Good habit to follow -
Write down a list to complete at night, and complete it before noon. Afternoon, maybe, a wild wild west.
What you have to do, house keeping.

4. Take care of your employees
Take care of your employees - they will put customers first.

5. Have the knowledge
Follow the passion. Work for other for a while. Better have a partner.

6. Constantly reinvent yourself
Bold step, no matter how old you are. As an entrepreneur.
End up like Sears, not existing any more. Not evolving, will die.

7. Always stay one step ahead

8. Stick to the grind
Business owner, team member.

9. Push through the fear of failure
Fear of failure - cannot ignore them, admit my vulnerability when he turns old around 40s years old.

10. Stand out

Sunday - Reading time - Career Advice

February 7, 2016

 Working on Leetcode algorithm, Julia took so many breaks when she worked on 5 Leetcode questions on Feb. 6 evening, she found out that she needs to build up mental toughness on the problem solving - using algorithm/ data structure. She wonders why she needs to read something not meaningful while solving those problems, why the algorithm cannot be nature in her life.

 So, she turns to advice from her favorite politician, Mitt Romney's top 10 rules for success, a Havard graduate's advice this Sunday.

 https://en.wikipedia.org/wiki/Mitt_Romney

 1. Have clear objectives -
Write down clear objectives.
What is my objective to work on Leetcode algorithms?
   1. Constant Reinvent herself - as a software programmer.
   2.
   3.

2. Stop thinking, start doing

3. Failures are inevitable

4. Have a life coach

5. Do what you enjoy
  More detail: English major -> business school -> Law degree (Havard law school)
  Do what you enjoy -> not lead more money 

6. Launch out into the deep 
  Master teaches Peter how to fish (Luke 5:4 “Put out into deep water, and let down the nets for a catch.” )
  Metaphor for the life, do not live in shallow, live in deep. Educate you, service others

7. Keep your life in perspective
    Perspective is good friend. Find ways in perspective.
    Do not study on Sunday. Personal time.
    Do not work at home. Devote time to the family. Really focus on the importance things of life.

8. Devote time for family

9. Do your present job well
    Secret to the advancement.
 
10. Your choices shape the lives of other people

And then, spent half hour to read the article. Great time to read. Julia found out that so many interesting things to read in the article, she started to find the joy of life - reading, expand the knowledge, and know the world: education, father and son, and career advice from the father, and many more.

https://en.wikipedia.org/wiki/Mitt_Romney



Friday, February 5, 2016

Do not complain - a tip worthy to share

February 5, 2016

  Chinese new year is coming in 2 days. And then, spent a few hours to watch videos about Canadian immigrant story.

  "Do not complain",  the video about Robert Herjavec, a Canadian story, an immigrant story.
https://www.youtube.com/watch?v=u5uD62Plakg
https://www.youtube.com/watch?v=-s9qJ7ATP7w
https://www.youtube.com/watch?v=sYprh2qkeDY

1. Be great on one thing
2. Never complain (Never complain, no one cares.
short story: Appreciate the opportunity. The father was laid off from sweeping the floor job, did not take unemployment pay when Robert tried to fill the form for his dad, his father did not want anything from the Canada which gives him opportunity. 20 dollars his dad came to Canada with wife and son, taking a boat with a suitcase)
3. Just keep going
4. Create value for your customers
5. Become the person others want to know
6. Listen to yourself
7. Leave your emotions out of it
8. Be able to adapt
9. Find what makes you tick
10. You are in control of everything

Robert Herjavec: The will to win
https://www.youtube.com/watch?v=7GxQ9KoaUJ0

Do not classify people loser. People give up, being a loser. Being a winner is easy, being a loser, keep going. Everything can go, go wrong for me.

Mental strength. Train for marathon for 20 days. The way you gain confidence, you just do it.

Just do it. You gain confidence by your experience.
If you are successful, money will follow.

Be efficient. Adaptability. If you are dropped in jungle, you will survive.

With kindness - kills the competition
https://www.youtube.com/watch?v=M9Mf2s4OJSU

Love tech industry - every 3 years it reinvents itself.
What is the purpose of business? Create customer, create value for them.  ( Julia's still thinking about it)

Leave emotion out of it. Be angry, make bad decisions.
Listening - what people try to say to you.

Let go - success is not good at everything. Find thing you are good at. Let go others. The world will reward you with very narrow knowledge.

Be world class on one thing. Do not worry about your weakness.

The minute you find that you are successful, it is the end of it. Keep going. Be master everything you choose, react with.

Conclusion:
Do not complain how time-consuming to improve skills by working on Leetcode algorithms.
Try to stay calm when performing algorithms. Do not give in nervousness.
Be mental toughness on problem solving. Always focus on current problem. Not worry about next one, or other thing. Try to do small, simple, stupid things first, see if it leads an idea or solution, and then, try to improve, and optimize it if need.