The difference between Linked List and Array List
|
get(index) and add() is O(1) for ArrayList;
Iterator.remove(), ListIterator.add(E element), add() is O(1) for Linked List
|
|
BFS DFS 时间空间复杂度
|
DFS: K - # of children each node has; H - height(depth)
Time O(K^H): exponential over the depth K
1 + K + K^2 + … + K^(H-1)
Geometric Progression(等比数列) a1(1 - q^n)/(1 - q)
1(1 - K^H)/(1 - K) so the Big O is O(K^H)
Space: O(K)
BFS: Same thing. Vertical traverse to horizontal traverse
For a graph G(V, E) :|V| - # of vertices; |E| - # of edges
BFS & DFS:
Time O(|V| + |E|);
Space O(|V|);
|
|
What data structure do you use when designing a phone contact book?
|
Trie Tree:
|
|
HashMap vs TreeMap and it’s big O
|
TreeMap’s key have to be comparable(implement comparable interface) or give a comparator object to constructor will constructing this TreeMap.
It’s Insertion, Deletion and Search is O(log n). Because TreeMap is implemented with a red-black tree. Where n is the number of entries in the hash map.
|
|
Abstract class vs Interface
| tring s1 and String s2, determine if s2 can be used to construct s1
(Find if s2’s char set is a subset of s1’s char set)
|
|
Sorted LinkedList, find loop in it
(If (next.val < cur.val) return true;)
|
|
|
Best time to buy and sell stock
|
|
|
Check if one string is rotated string of another
|
|
|
gray code
|
|
|
find nth Fibonacci number
|
|
|
An array of number with length 500 million. All numbers are 10 bit. Sort it
1) Bucket sort
2) Counting sort
3) Radix sort
|
|
|
Delete repeat nodes in a linked list
|
|
|
Min Max Stack
|
|
|
LC: Minimum Window Substring(sub int[] array)
|
|
|
compare version number
|
|
|
valid palindrome
|
|
|
Given any two nodes in a binary tree. Find a path that across least nodes
1) LCA(Least Common Ancestor)
|
|
|
Write a function that will take in email lists and return a new email list that contains only the email addresses that existed in all lists// 1: ,
// 2: ,
// o:
rolling HashSet
or one set
|
|
|
|
|
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
