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

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

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

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:

February 2, 2016

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

Feb. 17, 2016

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