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.
No comments:
Post a Comment