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

    No comments:

    Post a Comment