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

Read blogs about LRU first:

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

4. Leetcode 64: Minimum Path Sum

5. Disk scheduling algorithm: Round Robin

6. K closest point

Read blogs on this website:

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

7. Rearrange array - 区分正负

 8. Window sum 

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


16. HeapSort

Read 10 minutes lecture notes

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

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

写一个函数,给一个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.
               /  |  \
             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

上面哪个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   1234541
1 miss
2 miss
3 miss
4 miss
5 miss  替换 1
4 hit    4提前到第一位
1 miss  替换 2

February 2, 2016
Read blogs:

February 2, 2016

8  cell  
规律每天变化:两边相同--0 两边不同--1
输入:8cell  天数n


ps:两端cell两边假设const = 0

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.

May 17, 2016

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

Write C# practice on Leetcode 16 - 3 sum closest solution:

First practice on Leetcode 16 - 3 sum closest solution on

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

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.

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母,并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。

Java, using hashmap - Good idea


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

DFS, backtracking is clear in the code.

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)

very well written,

using vector instead of hashmap

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


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.

use this one as my example to write a good solution. Good style!

Excellent code style.

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

Julia, read Java priorityQueue class and get some ideas about the class design:

understand priority queue first, read the lecture notes:

2.  min stack

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

    4. Possible triangle

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

    6. Leetcode solutions - blog reading
    Just read as many solution and see if there are something new to write down here:  ( 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:

    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
    Think about recursive function solution first, and then DP solution to remove redundant calculation

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

    5.    BFS - algorithm
    Read the blog, understand the algorithm. Rate: 10

    9.   Leetcode: Longest increasing subsequence

    spend 10 minutes to read the blog:
    Previous blog:

    Write some C# code for this algorithm later.

    NLogn solution, better than DP solution, Recursive solution

    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

    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 - 

    So, ready to review more about parentheses:

    Leetcode 32: longest valid parentheses -

    Julia’s blog on this question:
    Leetcode question 22: Generate Parentheses