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