Sunday - Algorithm day (4) - 25 algorithms study

Feb. 13, 2016

  Algorithm Sunday, work on it, not just Google. Think by yourself first, work hard on it first.

1. Maximum number of overlapping intervals

For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5).

Recall Leetcode merge interval

Good solutions maybe: Using two arrays, one is to sort interval by start, another is by end.

2. Merge two sorted linked lists

Recursive solution

Itearativesolution 1

Iteration solution 2

Julia's practice:

Recursivesolution

3. LRU Cache Miss

Read blogs about LRU first:

program creek 

Leetcode discussion

This blog is excellent. Julia will write the implementation in C#.

Jeffwan

acmerblog

jiuzhang

4. Leetcode 64: Minimum Path Sum

http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/

5. Disk scheduling algorithm: Round Robin

6. K closest point

Read blogs on this website:

blog 

Julia could not believe that she always reads excellent code, and then, also great stories how technologies are different.

shepherdyuan blog 1

shepherdyuan blog 2

7. Rearrange array - 区分正负数

 8. Window sum 

countinversions 

9. Rearrange array in alternating positive negative items with O(1) extra space

shepherdyuan 

idea: 如果用O(1)的话那需要有一个pointer指向第一个错误的数字，比如偶数index的正数和奇数index的负数。然后碰到当前的数如果符号和错误的那个数不一样，那就rotate那段sub array。

10. Iterative binary tree traversal

11. Binary tree insert/search/update

12. Trie - Java Implementation

13. Moore's voting algorithm

14. First Missing Positive

O(n)的解法，很巧妙，利用数组的特性，暂且称之为“派送法”哈哈，派送A[i]到A[A[i]-1]。

Decimal representation 

15. Implement list, stack and map

16. HeapSort

Read 10 minutes lecture notes. 

17. Sorting algorithms

about partition, quick sorting:

Julia'sblog and her quick sorting partition explanation with a test case.

quicksort algorithm practice

18. Merge Intervals

上来给一串start time － end time，格式是Apr 2010 － Mar 2011这种，要求计算出这些时间的总跨度，重叠的跨度不重复计算。举例：["Apr 2010 - Dec 2010", "Aug 2010 - Dec 2010", "Jan 2011 - Mar 2011"]这一个string数组，结果为（12-4+3-1）＝10个月。一出这题有点蒙，感觉代码量很大，时间又不多了，只能硬着头皮上。写完string->time的解析函数之后，发现其实就是一道mergeinterval的题.

19. 写一个函数，给一个node，代表一个人，返回他linkedin 或者facebook network

BFS - graph traversal 

如果一个用户 用这个api，那个node 的朋友很多，million to billion 级别，那么response感觉很慢怎么办? 

20. validBST

如果有duplicate 而且 duplicate return false 的时候会 failed 一个corner case

21. Given a tree, find the smallest subtree that contains all of the tree's deepest nodes.
                  a
               /  |  \
             b   c   d
           /   \       |
         e      f      g
       /       /  \
      h      i     j

depth of tree: 4
deepest nodes:[h,i,j]
least common ancestor of [h,i,j]:
return: b

leetcode上面哪个lowest common ancestor of binary tree

22. insert node in circular list, 

23. LRU miss count

输入 maxSize， input int array 

输出是miss cout

example：   size = 4， input array   【1，2，3，4，5，4，1】

1 miss

2 miss

3 miss

4 miss

5 miss  替换 1

4 hit    把4提前到第一位

1 miss  替换 2

大概就是这样。。。

February 2, 2016

Read blogs:

blog 1

blog 2 

February 2, 2016

http://blog.csdn.net/rollycoris/article/category/5884445

http://blog.csdn.net/rollycoris/article/category/5884447

Julia's practice

24.

8 个 cell  

example：【0，1，1，1，1，1，1，0】

规律每天变化：两边相同--》0， 两边不同--》1

输入：8个cell，  天数n

问n天后cell长啥样

ps：两端cell两边假设const = 0；

小example：

day0:  (0)0,1,1,1(0)

day1:  (0)1,1,0,1(0)

day2:  (0)1,1,0,0(0)

25. Longest path from root to leaf in binary tree

Diameter

Feb. 17, 2016

Check out topcoder training about testing cases, maybe, use it for a while for practice.

a top coder's blog

https://www.zhihu.com/question/40463511

Leetcode 1, 15, 16: Two sum, 3 sum, 3 sum closest

January 24, 2016

Review Leetcode solution, Two sum, 3 sum, 3 sum closest.

http://codesniper.blogspot.ca/2014/12/two-sum-leetcode_31.html
http://codesniper.blogspot.ca/2015/01/3sum-leetcode.html

http://codesniper.blogspot.ca/2015/01/3sum-closest-leetcode.html

May 17, 2016

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write C# practice on Leetcode 16 - 3 sum closest solution:
https://gist.github.com/jianminchen/d23598296e7ba665b6d45ae4acfeb600

First practice on Leetcode 16 - 3 sum closest solution on
https://github.com/jianminchen/Leetcode_C-/blob/master/3sumCloset.cs

Question and Answer:
1. What do you learn through the practice this time?
Julia learns the importance to do static analysis on the code. Do not rush, make sure every variable/ name is making sense, every line of code is best she can present, every executable path should be examined. Talk about the work as well.

Leetcode 17: Letter Combinations of a phone number (DFS)

January 24, 2016
 
17 Letter Combinations of a phone number (DFS)

Julia likes to focus on basic things about algorithms, she tries to focus on recursive function design, BFS, DFS, backtracking. Here is her favorite DFS algorithm, she tries to build more fun memory about DFS algorithm, every time she works on DFS algorithm, she is so happy and eager to share her 2 cents, learned from Leetcode blogs - all her favorite blogs.

http://www.cnblogs.com/grandyang/p/4452220.html
Analysis from the above blog:
这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合，相类似的题目有 Path Sum II 二叉树路径之和之二，Subsets II 子集合之二，Permutations 全排列，Permutations II 全排列之二，Combinations 组合项， Combination Sum 组合之和和 Combination Sum II 组合之和之二等等。我们用递归Recursion来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，然后我们还需要一个变量level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似，

Her practice is too weak in 2015.
https://github.com/jianminchen/Leetcode_C-/blob/master/LetterCombinationOfAPhoneNumber.cs

Missing in the last practice:
1. Use iterative solution, but lack of analysis - (comment area, hard to review)
2. Should focus on DFS solution, basic things.

New practice in January 2016:
1. using recursive to solve the problem, it is fast and quick way to solve it in 10 minutes.
2. Only need to write a few lines of code.
3. Need to design recursive function.
4. Need to do backtracking,
5, Need to do char, string, int a few types, and also do type conversion.

Julia's practice, it took her 27 minutes to write down, compile, and have some comment written.
https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。
http://bangbingsyb.blogspot.ca/2014/11/leetcode-letter-combinations-of-phone.html

Java, using hashmap - Good idea
http://blog.welkinlan.com/2015/10/25/letter-combinations-of-a-phone-number-leetcode-java/

终于出现我最不擅长的递归题了，这道题是经典递归题，标准DFS解法，应作为模板牢牢记住。
http://simpleandstupid.com/2014/10/16/letter-combinations-of-a-phone-number-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

So, Julia is not good at recursive function design as well. So, she likes to search a blog and find the most important tip she can grasp in next 20 minutes.

Array initiliazation can be in one line instead of more than 8 lines
http://yucoding.blogspot.ca/2013/01/leetcode-question-42-letter.html

DFS, backtracking is clear in the code.
http://rleetcode.blogspot.ca/2014/02/letter-combinations-of-phone-number-java.html

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java

very well written,
http://codesniper.blogspot.ca/2015/01/17-letter-combinations-of-phone-number.html

using vector instead of hashmap
http://yumei165.blogspot.ca/2013/04/letter-combinations-of-phone-number-c.html

Good analysis - read the analysis in the following blog -

• 这个是一个结果是排列组合的问题,一个类似的问题就是小组赛N个队, 相互之间的比赛 列表. 这种问题就是回溯法
• 回溯法最重要的就是要"先加再减" (Julia's comment -> backtracking ) 
• 回溯法函数参数的设计是把结果当成参数(此处是用参数引用), 返回值返回一个void. 这样容易设计递归.
• java的做法会比c++看起来麻烦一点, 而且java是无法做到真的const String数组

http://harrifeng.github.io/algo/leetcode/letter-combinations-of-a-phone-number.html

九章算法
http://www.jiuzhang.com//solutions/letter-combinations-of-a-phone-number/

Analysis from the following blog:
Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 
http://buttercola.blogspot.ca/2014/09/leetcode-letter-combinations-of-phone.html

use this one as my example to write a good solution. Good style!
https://segmentfault.com/a/1190000003766442

Excellent code style.
http://shanjiaxin.blogspot.ca/2014/02/letter-combinations-of-phone-number.html

So, put together something for DFS /backtracking algorithm - favorite tips:
1. DFS, do not forget backtracking, using Chinese words, "先加再减". 
2. Recursive function design:
    Return result C#: IList<string>, 
    put it as input argument or member variable of class Solution 
3. Remember a tip to convert a char to int, very basic convert using this: 
    Char c (no one can remember the ascii value of '0', but use type conversion c-'0', char to int; in other words, compare to relative char, get the value by type conversion automatically).
    c - '0' 

4. dictionary declaration, common and easy way is to declare one dimension array:

    String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

5. using C# or Java, string class is not good, using StringBuilder class instead. 

6. Remember one or two DFS algorithms, use them to relax and help to figure out design issue, difficulty level of DFS problem solving - honestly, it is easy and quick solution, less time-consuming compared to an iterative solution, more time-consuming DP with memorization solution. 
   

Algorithm night (3)

January 21, 2016

Find 10 challenging algorithms questions, and then go over them one by one. It is fun, and also good learning experience.

She wishes that she could have more than 100 algorithm night, reviewed 1000 algorithms already, and each time, just so relax to go over different ideas how to solve them, by reading, and by good hints and teaching through blogs. At that time, she will be good thinker about algorithms. Wishful thinking, get back to reality (5 algorithms, 2 hours, a lot of headache, and could not figure out what is brute force solution.), work on 3rd algorithm night.

Be humble, be stupid, and learn from mistakes.

1. Leetcode 295: Find medium from data stream 

https://segmentfault.com/a/1190000003709954
https://gist.github.com/jianminchen/31572a64b2af48e3ccce


http://buttercola.blogspot.ca/2015/12/leetcode-find-median-from-data-stream.html


Julia, read Java priorityQueue class and get some ideas about the class design:
http://www.programcreek.com/2009/02/using-the-priorityqueue-class-example/

http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue

understand priority queue first, read the lecture notes:
http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf

2.  min stack
http://buttercola.blogspot.ca/2015/11/zenefits-mini-stack.html

3. 写一个函数float sumPossibility(int dice, int target)，就是投dice个骰子，求最后和为target的概率。因为总共的可能性是6^dice，所以其实就是combination sum，求dice个骰子有多少种组合，使其和为target。先用brute force的dfs来一个O(6^dice)指数复杂度的，然后要求优化，用dp，最后结束代码写的是两者结合的memorized search吧，

https://gist.github.com/diegozeng/6c964f623bbeaa716526

http://www.labnol.org/internet/github-gist-tutorial/28499/

4. 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. )

5.  Top K int in a large stream (This can be done in O(n))
http://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence

6. Leetcode solutions - blog reading
Just read as many solution and see if there are something new to write down here:

http://www.cnblogs.com/grandyang/p/4606334.html  ( No. 1 - No. 280)

Review Leetcode questions 1 - 20 (January 24, 2016)

So, here are some notes about DFS - backtracking problem solving:

1. DFS vs BFS, DFS usually involves backtracking as well. So, remember backtracking.
2. How to design the DFS function?
    A. return result - one of arguments:
   IList<string> res
    is a good idea, also, it can be member variable of class Solution.
    B. Convert a char to integer '1' -> 1
         quickest way is c - '0'
    C. Backtracking is the key to ensure the bug free
    D. Java, C# using stringBuilder to construct string, append

Review solutions:
http://codesniper.blogspot.ca/2015/03/sticky-post-all-of-my-published.html

Java solution:  Leetcode 1 - 120

Algorithm night (2): 10 questions to read

January 20, 2016

Plan to spend 2 hours (9pm - 12pm) to read 10 blogs about algorithms, each blog 10 minutes.

1.    Leetcode: Coin Change 
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
Think about recursive function solution first, and then DP solution to remove redundant calculation

http://blog.csdn.net/kenden23/article/details/17636599
http://buttercola.blogspot.ca/2016/01/leetcode-coin-change.html

2.    Leetcode: Maximum product of word lengths 

https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-product-of-word-lengths.html

Brute force analysis, bit manipulation - encode string using integer, and then, optimize the algorithm - instead of two strings' comparison, using two integer bit manipulation - And operator - clever solution. 

3.   Leetcode questions: Power of 2 / Power of 3 

 http://www.cnblogs.com/grandyang/p/4623394.html
 Power of 3
http://my.oschina.net/Tsybius2014/blog/601048

  http://buttercola.blogspot.ca/2016/01/leetcode-power-of-three.html

4.    Leetcode 325: Maximum size subarray sum to K (Level: easy)

https://asanchina.wordpress.com/2016/01/05/325-maximum-size-subarray-sum-equals-k/

http://buttercola.blogspot.ca/2016/01/leetcode-maximum-size-subarray-sum.html

January 21, 2016

5.    BFS - algorithm 
http://www.geeksforgeeks.org/find-number-of-islands/
Read the blog, understand the algorithm. Rate: 10

http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/

http://algobox.org/number-of-connected-components-in-an-undirected-graph/

http://buttercola.blogspot.ca/2016/01/leetcode-number-of-connected-components.html

6.    Sparse Matrix Multiplication

http://www.cs.cmu.edu/~scandal/cacm/node9.html
https://leetcode.com/discuss/71912/easiest-java-solution

http://buttercola.blogspot.ca/2016/01/leetcode-sparse-matrix-multiplication.html

7.    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

8.  Leetcode: Remove duplicate letters

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

9.   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),

10. Leetcode: Binary Tree Longest Consecutive Sequence

Excellent chance to practice recursive function

https://segmentfault.com/a/1190000003957798

http://buttercola.blogspot.ca/2015/12/blog-post.html

Leetcode questions 20: Valid Parentheses

January 20, 2016 

Leetcode 20: Valid parentheses

http://blog.csdn.net/fightforyourdream/article/details/13011825

Julia’s C# code:

https://github.com/jianminchen/Leetcode_C-/blob/master/20ValidParentheses.cs

January 20, 2016

https://github.com/jianminchen/Leetcode_C-/blob/master/20ValidParentheses_B.cs 

favorite blogs to read: January 20, 2016

Great time to go over different ideas to implement the algorithm, using Map in C++, Hashmap, and see so many talents through those code - 

http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-parentheses.html

http://www.acmerblog.com/leetcode-solution-valid-parentheses-6316.html

http://blog.csdn.net/foreverling/article/details/49685177?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

http://segmentfault.com/a/1190000003481208

http://harrifeng.github.io/algo/leetcode/valid-parentheses.html

http://www.jiuzhang.com/solutions/valid-parentheses/

So, ready to review more about parentheses:

Leetcode 32: longest valid parentheses -

http://codeganker.blogspot.ca/2014/03/longest-valid-parentheses-leetcode.html

Julia’s blog on this question:
Leetcode question 22: Generate Parentheses
https://github.com/jianminchen/Leetcode_C-/blob/master/GenerateParentheses_No22.cs

Leetcode question 32:
32 Longest Valid Parentheses

http://codeganker.blogspot.ca/2014/03/longest-valid-parentheses-leetcode.html

http://bangbingsyb.blogspot.ca/2014/11/leetcode-longest-valid-parentheses.html

http://blog.csdn.net/worldwindjp/article/details/39460161

http://shanjiaxin.blogspot.ca/2014/04/longest-valid-parentheses-leetcode.html

C# code:
https://github.com/jianminchen/Leetcode_C-/blob/master/32LongestValidParentheses.cs