## Sunday, January 31, 2016

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

Julia's practice:

### 3. LRU Cache Miss

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

### 6. K closest point

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

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

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

### 10. Iterative binary tree traversal

12. Trie - Java Implementation

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

16. HeapSort

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

18. Merge Intervals

19.

BFS - graph traversal

20. validBST

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

22. insert node in circular list

23. LRU miss count

example   size = 4 input array   1234541
1 miss
2 miss
3 miss
4 miss
5 miss  替换 1
4 hit    4提前到第一位
1 miss  替换 2

February 2, 2016

February 2, 2016

24.
8  cell
example：【01111110

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

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

## Sunday, January 24, 2016

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

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:

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:

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/

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

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.

## Thursday, January 21, 2016

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

## Wednesday, January 20, 2016

### 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/

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

Power of 3
http://my.oschina.net/Tsybius2014/blog/601048

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/

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/

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

### Leetcode questions 20: Valid Parentheses

January 20, 2016

Leetcode 20: Valid parentheses

Julia’s C# code:

January 20, 2016

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://www.jiuzhang.com/solutions/valid-parentheses/