Selection sort

如果有一沓人民幣，怎么按照面額從小到大按順序排序？
答：每次從這沓人民幣中取出面額最小的放到一邊幕庐，循環(huán)往復直到原有的這沓人民幣被取完就排序完成了。
同理家淤，我們可以循環(huán)遍歷題目中的數(shù)組A每次將最小的element移動到數(shù)組A的左邊翔脱，等for循環(huán)執(zhí)行完之后數(shù)組A就是一個排好序的數(shù)組了。

Merge sort

1.將數(shù)組分成兩組
2.每一組各自排序媒鼓，怎么排?用同樣的方法排届吁，重復動作(1)分成兩組...（遞歸）
3.合并：經過1，2動作的遞歸后绿鸣，最后會變成一顆樹疚沐，再從樹的最底層開始每兩個節(jié)點開始合并,
合并的同時做好排序，當合并到最頂層時整個數(shù)組就排序好了潮模。
如何排序：每個節(jié)點的數(shù)據都是由上一次合并后得到的是排序好的亮蛔！
我們可以把兩個節(jié)點想象為有兩個數(shù)組，每次對比兩個數(shù)組的第一個元素取出較小的元素放到另一個數(shù)組里擎厢，
當兩個數(shù)組的元素都被取完了就完成排序和合并了究流。

Quick sort

快速排序的核心思想：先隨機找到一個支點(pivot)，找到這個支點在數(shù)組中真正的index(排序好后的index),
在尋找index的同時把所有比pivot value小的元素放左邊,大于等于pivot的元素放右邊;
然后以支點為切口將數(shù)組切開成左右兩部分(不包含支點)动遭，再從這兩部分各隨機選中一個支點找到其在數(shù)組中真正的位置芬探，
循環(huán)往復直至無法再切割為止。

尋找pivot index的過程
1.隨機確定一個pivot
2.將pivot放到最右邊
3.根據隨機選中的pivotIndex分區(qū)厘惦，定義左右擋板(指針):i, j向中間遍歷比較ele與pivot ele的大小,
比pivot小的元素放左邊偷仿，大于等于pivot的元素放右邊；
4.最后i就是我們要找的pivotIndex宵蕉，將最右邊的pivot與i互換位置即可

*荷蘭旗問題(Rainbow sort)
這種荷蘭期問題的核心解法很簡單:ijk,ijk,ijk重要的事情說三次酝静，
為什么是ijk呢，因為解這種問題需要定義3個指針配合運算羡玛，
[0,i)i左邊的元素都是-1,
[i,j)中間的元素都是0,
(k, arr.length-1] k右邊的元素的都是1,

遞歸(Recursion)

遞歸三部曲

1.define subproblem：定義子問題
2.find recursion rule: 找出遞歸規(guī)則
3.define base case: 定義退出條件

知識點

1. 表象上: function calls itself
2. 實質上: reduce a big problem to smaller ones(size n depends on size n-1, or size n-2 or n/2...)
3. implementation上:
   1).base case: smallest problem to solve
   2).Recursive rule. how to make the problem smaller
   (if we can resolve the same problem but with a smaller size,
   then what is left to do for the current problem size n)

Binary Search

Essentially, the principle of binary search is reduce the search space by 1/2 of its
original size. In the meantime, you must guarantee that the target must not be ruled out.
核心思想：每次淘汰一定不對的元素

前提：二分查找算法所處理的數(shù)組必須是Sorted好的
二分查找又稱為折半查找别智，僅適用于事先已經排好序的順序表。
其查找的基本思路：首先將給定值K稼稿，與表中中間位置元素的關鍵字比較薄榛，若相等讳窟，
返回該元素的存儲位置；若不等蛇数，這所需查找的元素只能在中間數(shù)據以外的前半部分或后半部分中挪钓。
然后在縮小的范圍中繼續(xù)進行同樣的查找。如此反復直到找到為止耳舅。

中心開花等解法

Queue Stack

Question：How to use multiple Stacks to implement a de-queue
Method: Use 3 stacks to improve the time compleity of pop() operation.
We use a buffer stack, say stack3 to buffer the element, when moving all elements
from left part to right part.To make sure the number of elements in Left and Right part are
roughly 50% of all element.In detail, Stack3 is used as the buffer to store the top 1/2 element,
so that the bottom 1/2 element can be moved to stack2.

worst case amortized time= ??
step1:we move 1/2n ele from stack2 to stack3(buffer)
1/2n + 1/2n = n
step2:we move the remaining 1/2 ele from stack2 to stack1(from right to left)
1/2n+1/2n = n
step3:reverse step1,
1/2n+1/2*n = n
So, In order to blance both sides, it takes O(3n) for n element.
All the flowing pop operation, take only O(1)
xxxxxx(n/2) ||stack1 stack2||yyyyyy(n/2)

                        3n+n/2*1      3.5n
For 1st n/2 elements ------------- = ------ = O(7) = O(1)
                          n/2         0.5n
                          
                        3n+n'/2*1     3.5n'
For 2st n/4 elements ------------- = ------ = O(7) = O(1)  n'=n/2
                          n'/2        0.5n'

                        3n''+n''/2*1  3.5n''
For 3st n/4 elements ------------- = ------ = O(7) = O(1)   n'=n/2
                          n''/2       0.5n''
        
            3.5n + 3.5n*1/2 + 3.5n*1/4 + ....       3.5n(1+1/2+1/4+...)
total = --------------------------------------- = --------------------- 3.5* 2 = O(7)
                        n                                   n

1.什么問題要往stack上考慮?
anwser:從左到右linear scan一個array/string時,如果要不斷回頭看左邊最新的元素時碌上，
往往要用到stack
1.histogram中找最大長方形
2.逆波蘭表達式
3.String的repeatedly dedduplication. cabba->caa->c
2.Stack的移動操作有什么常見特性?
1.將stack1所有元素全部move到stack2，元素在stack2的順序完全reverse
2.將stack1所有元素move到stack2,然后元素全部(或者部分)move回stack1,則
回到原來stack1的元素的順序不變, amortized的時間復雜度分攤到每一個move的元素的時間為O(1)

LinkedList

Key points
1.When you want to de-reference a ListNode, make sure it is not a Null pointer
2.Never ever lost the control of the head pointer of the LinkedList.

Binary Tree & Binary Search Tree

基本知識點:
tree traverse
1.pre-order
2.in-order
3.post-order
trick:base case usually refers to the null ChildNode below the leaf node.
(null pointer under the leaf node)

基本概念：
1.Balanced binary tree: is commonly deefined as a binary tree in which the depth of the
left and right subtrees of every node differ by 1 or less
Conclusion 1:If a tree has n number of nodes. and it is balanced,
then the height(level) of the tree = O(lgn)

2.Complete binary tree: is a binary tree in which every level, except possibly the last,
is completely filled, and all nodes are as far left as possible.
Conclusion 2:If a tree is a complete tree, then it must be a balanced tree.

3.Binary Search Tree: for every single node in the tree, the values in its left subtree
are all smaller than its value, and the values in its right subtree are all larger than its value.
Conclusion 3:If we print the value of the nodes in BST in in-order sequence,then it must form an ascending order.

Recursion在tree題目的基本應用大致分為2類
1.把value從上往下傳遞(then從下往上)的題目
1.1 BST判頂方法
2.只把value從下往上傳遞
2.1 getHeight(Node root) 是把integer value 從下往上傳遞
2.2 isBalanced(Node root)是把boolean value 從下往上傳遞
2.3 isSymmetric(Node root)是把boolean value 從下往上傳遞
2.4 assign the value of each node to be the total number of nodes that belong to its left subtree
(是把integer value從下往上傳遞的題目)

Heap & Graph Search Algorithms I

性質:heap的實現(xiàn)通過構造二叉堆(binary heap),這種數(shù)據結構具有以下性質

1. heap總是一顆完全樹. complete binary tree
2. 任意節(jié)點小于它的所有后裔,最小元素在堆的根上(堆序性).
3. 將根節(jié)點最大的堆叫做MAX HEAP,根節(jié)點最小的堆叫做Min Heap
4. index of lChild = index of parent*2 + 1
5. index of rChild = index of parent*2 + 2
6. index of parent = (index of child-1)/2 (integer divsion)
7. unsorted but fpllpw rules above
   支持的基本操作
8. insert: 向堆插入一個新元素,復雜度O(lgn) 插入到heap的最后一個index浦徊，再跟parent節(jié)點比較馏予，比parent小就往上冒泡
9. update(index): 將新元素提升使其符合堆的性質;時間復雜度O(lgn)
10. get/peek: 獲取當前heap頂部元素的值 O(1)
11. pop:刪除堆頂元素,T=O(lgn), 刪除第一個index，再將最后一個元素移到頂部盔性，再往下壓與較小的子節(jié)點交換霞丧，直到沒有比它小的節(jié)點
12. heapify: 堆化，使一個unsorted array變成一個堆O(n)

Graph & BFS
trick: Queue while{poll} for{offer}
Breadth First Search(BFS1)
BFS1的操作過程&How to describe a BFS's action during an interview?
1.Definition 1: expand a node;中文: 延展一個node, e.g. visit/print its value...
2.Definition 2: generate node's neighbor node:earch out to its neighboring node
(First, to generate Node 3, and then generate Node 2).
3.Data Stucture: Maintain a FIFO queue, put all generated nodes in the queue.
e.g. 3 and then 2 into the queue(FIFO) queue head->[3, 2] tail
4.Termination condition: do a loop until the queue is empty
5.Process
When should we consider to use breadth first search?
Deal with relationship between nodes on the same level.Especially in a tree.
Best First Search(BFS2)
1.Objective: 由點到面 == 所有點的最短距離算法
2.Example problem: 從北京到中國其他主要城市的最短距離各是多少
3.Data structure: priority queue(min heap or max heap)
4.解題思路
4.1 Inital state(start node)
4.2 Node expansion/Generation rule:
4.2.1 expand the node x with xxxxxx
4.2.2 generate the neighbors (y) of this node
4.3 Termination condition:所有點都計算完畢才停止冕香，也就是priorityqueue變空

properties
1.one node can be expanded once and only once
2.one node can be generated more than once.(cost can be reduced over time)
3.all the cost of the nodes that are expanded are monotonically non-decreasing
(所有從priority queue里面pop出來的元素的值是單調非遞減-->單調遞增)
4.for a graph with n nodes and m edges, time complexity is O(mlogn)
5.when a node is popped out for expansion,its value is fixed which is equal to
the shortest distance from the start node.

DFS

Depth-First Search：
1.DFS一般用來計算有多少種排列組合的問題.
2.Recall "using pre-order to traverse a tree"
3.實現(xiàn)方法：easy to use recursion
4.常見考題
* print all subsets of a set
* Given a string with no duplicate characters,
return a list with all permutations of the characters. (swap call swap)
* print all valid permutaions of () () ()
* 99cents 湊硬幣金額蛹尝，有1分,5分,10分,25分coin,給定一個錢數(shù)99cent,有多少種組成方式
并打印出所有的可能組合.

DFS基本方法:完成一件事情需要N個步驟，每個步驟有M種選擇
1.what does it store on each level?
(每層代表什么意義悉尾？一般來講解題之前就能推斷出DFS要recurse多少層)
2.How many different states should we try to put on this level?
(每層有多少個狀態(tài)/case 需要try? 每層叉出多少個叉)

DFS復雜度分析：
Using revursion tree to get the complexity

of levels

of branches for each node

use the # of nodes of last level to represent the # of nodes in the whole tree.

String I

5類常見問題:(和array的某些問題相似突那，往往需要2個index來完成操作.)

1. Removal
   1.1 remove some particular chars from a string
   1.2 remove all leading/trailing/duplicated empty spaces from a string.
2. De-duplication aaabbb_ccc->ab_c
   3.Substring
   3.1 regular method
   3.2 robin-carp (hash based string matching) & KMP (Knuth-Morris-Pratt)
   4.String replacement:replace empty space ‘ ‘ with "%20"
   5 Reversal(swap) e.g. I Love Google-> Google Love I

Advanced operation (Defer to String II)

1. Move letter around e.g. ABCD1234->A1B2C3D4
2. Permutation (use DFS)
3. Decoding/encoding aaaabcc->a4b1c2
4. Longest substring that contains only unique chars
5. Matching(*,?)
6. etc

解題思路：
擋板大法1：
1.兩個擋板，相向而行
2.2個擋板构眯，3個區(qū)域愕难，同向而行
Initialization
i=0; all letters to the left-hand side of i(not including i) are all processed letters
that should not be removed(slow)
j=0; j is the current index to move(fast). all letters in [i, j] are all area that we do not care(empty space xxx)
(j, size-1] unknown area to explore
3.sliding window in a string (slow=fast indices)
slow：
fast：

Bit

Bit Operation

&
|
~
^
<<
>>
>>>

Q1: determine whether a number x is a power of 2
Q2: How to determine the number of bits that are different between two positive integer?
Q3: What happens if we assign a negative to an unsigned integer?
Q4: determine whether a string contains unique characters(i.e. no duplication)
Q5: How to reverse all bits of a number?
Q6: Given a number x, how to get the hexadecimal representation of the number in string type?

OOD II

Polymorphism

Recursion II

Q1 a^b
Q2 Recursion與1D or 2D array的結合
1.1D array 二分法比較常見
1.1 MergeSort
1.2 QuickSort
2. 2D Array
2.1 逐曾(row by row)遞歸: n queen
Q3. Recursion與LinkedList的結合
Q3.2 Reverse a Linked list(pair by pair)
Q4. Recursion與String的結合
Q4.1 reverse a string using recursion
Q4.2
Q5. Recursion與Tree的結合
Q5.1 Tree+Recursion：從下往上返值
way of thinking(Tricks)
1.What do you expect from your lchild / rchild?
(usually it is the return type of the recursion function)
2.What do you want to do in the current layer?
3.What do you want to report to your parent?(same as Q1=Q3)

Dynamic Programming I

DP的核心思想類似數(shù)學歸納法

1. 把一個大問題(size==n)的解決方案用比他小的問題(問題們)來解決，也就是思考從問題
   size=n-1 增加到size=n的時候惫霸，如何用小問題的solution構建大問題的solution.

2.與 Recursion的關系:
2.1 Recursion從大到小來解決問題猫缭，不記錄任何sub-solution只要考慮
2.1.1 sub problem
2.1.2 base case
2.1.3 recursive rule
2.2 DP從小到大來解決問題，不記錄任何sub-solution只要考慮
2.2.1 由size(<n)的subsolution(s)-> size(n)的solution
2.2.2 base case
2.2.3 Induction rule

DP的解題常用方法：
適合什么類型的問題：
1.一維的original data (such as a rope, a word, a piece of wood),求MAX or MIN (cut, merge, etc)
1.1 if the weight of each smallest element in the original data is identical/similar
1.1.1 e.g. identical: 1 meter of rope
1.1.2 e.g. similar. a letter, a number
Then this kind of problem is usually:
Linear scan and look back to the previous elements.
For example:
Longest Ascending Subarray (when at i, look back at i-1)
Longest Asending Subsequence (when at i, look back at 1......i-1)
1.2 if the wight are not the same:
1.2.1 e.g. DP1課后題 沙子歸并
1.2.2 e.g. 強化練習:切木頭
從中心開花,[index=0,1,2,3,n-1], for each M[i,j], we usually need to try out all possible k that (i<k<j), M[i,j] = max(M[i,k]+/-* M[k,j]) for all possible k)

2. (稍微復雜)二維的original data(such as two words 求 longest common substring; 2D matrix求最大sub-matrix和最大)
   思路：
   1. Base case:
      DP[0] = ?
   2. Induction rule:
      a.DP[i] represents what ???
      DP[i] represents ....
      b.DP[i] = 數(shù)學表達式壹店，與小一號或小兩號問題扯上關系

左大段右小段 etc

OOD II

Parking Lot
1.Understand/Analyze the use case(明確這個系統(tǒng)是干什么的)
    Usecase --> APIS
2.Classes and thir relationships
    Association: ageneral binary relationship that describes an activity between two classes.
    Aggregation/Composition:a special form of association, which represents an ownership relationship between two ckasses(has-a)
    Inheritance: is a

DP II

Q1 Minimum Number of Jumps
Q2 Largest sum of a subarray. T=O(n) S=O(n)
Follow up1: how to optimize space
Follow up2:how to return the left-right border of the solution?
Q3 Dictionary word problem
Q4 Edit Distance
DFS猜丹、DP
Q5 Largest square of 1's in binary matrix

Element deduplication/removal in an array

1.同向而行隔板題：
a.基本思想: 用兩個變量，一個變量記錄當前指針位置(= fast index), 一個變量記錄隔板位置(= slow index).
b.性質1：slow隔板左邊時處理好的元素茫打，當前指針fast右邊是未處理的元素居触，隔板和當前指針之間的區(qū)域時無用的元素，每次只要分析當前元素性質是否要加入或者移動slow隔板就可以了老赤。
c.性質2：用快慢兩個指針，同向而行制市，處理完畢后抬旺，return的結果中，每個Integer/char的相對位置不變祥楣。
Prerequlsite: We need to ensure the fast poiter is always ahead of the slow pointer.
關鍵點: 每個隔板的物理意義在整個程序運行過程中都要保持consistent.

Data structure:
fast index: the current position of the linear scan slow index A[0, slow-1] is the answer for A[0, fast-1]

2. 隔板, 相向而行,Two pointers moving in opposite direction
   a.基本思想：用兩個變量开财，一個變量記錄左邊隔板位置(=left index), 一個變量記錄右邊隔板位置(= right index)
   b.性質1: left左邊是處理好的元素, right右邊也是處理好的元素汉柒，兩個隔板中間是未處理區(qū)域。
   c.性質2: 處理完畢之后, return的結果中, 每個integer/char的相對位置可能發(fā)生變化责鳍。