Easy ones

Insertion sort

Bubble sort

Selection sort

Merge sort

  1. Divide an array of nn elements into sub-arrays of n/2n/2 elements [Divide]
  2. Sort each of the sub-arrays with Merge Sort [Solve]
  3. Merge the sorted sub-arrays [Conquer]

Efficient merge Given sub-arrays of n1n_1 and n2n_2 elements, it merges them in O(n1+n2)O(n_1 + n_2): Compare a pair of elements from the beginning of sub-arrays, put down the small one, and move to the next. This is a correct way to merge only because these sub-arrays are already sorted.

Time Complexity Dividing an array of nn elements takes log2n\log_2 n steps to reach the leaf. Merge takes O(n)O(n) time, thus time complexity is O(nlogn)O(n\log n)

Partition (prep for Quick sort)

partition(AA, 00, NN) divides array A[0:N]A[0:N] into two sub-arrays A[0:q1]A[0:q-1] and A[q+1:N]A[q+1:N], and return qq. All the elements in the first subarray is smaller than A[q]A[q], and those in the second subarray is larger than A[q]A[q].

![partition](/media/posts/algorithms/partition.jpg =400x)

At every step, jj always increments by one, and decides which group A[j]A[j] should go into. :::message How do we move A[j]A[j] to the correct group?

  • If A[j]>A[N]A[j] > A[N], just increment jj
  • If A[j]A[N]A[j] \leq A[N], increment ii, and then exchange A[i]A[i] and A[j]A[j]. :::

Time complexity is O(n)O(n), as jj goes from 00 to N1N-1.

Quick sort

  1. Divide an array into two sub-arrays with Partition algorithm [Divide]
  2. Sort each of the sub-arrays with Quick Sort [Solve]

The average time complexity of Quick sort is O(nlogn)O(n \log n), and it's the fastest sorting algorithm in most cases. However, if you pick the value xx (in the figure above) in the same way all the time, it becomes O(n2)O(n^2) in the worst case.


Tree walk

  • Preorder Tree walk: [root] -> [left subtree] -> [right subtree]
  • Inorder Tree walk: [left subtree] -> [root] -> [right subtree]
  • Postorder Tree walk: [left subtree] -> [right subtree] -> [root]
def preorder(node):
    if node is None:
def inorder(node):
    if node is None:
def postorder(node):
    if node is None:

Time complexity is O(n)O(n) as it visits each node exactly once.

Binary Heap

Binary heap is a complete binary tree that meets:

  • max-heap (min-heap): the value of a node is smaller (larger) or equal to its parent

There are no constraints between sibling node values. A binary heap is represented as an array with 1-origin.

It has a very nice property that, given a node index ii,

  • parent: i/2\left\lfloor i/2 \right\rfloor
  • left child: 2i2i
  • right child: 2(i+1)2(i+1) ![partition](/media/posts/algorithms/binary_heap.jpg =150x)

:::message Complete binary tree: All the leaves on the left side is filled, and the maximum difference of leaves' depths is one or zero. :::

Dynamic Programming

Longest Common Subsequence (LCS)

Given a pair of sequences X={x1,,xm}X=\{x_1, \ldots, x_m\} and Y={y1,,yn}Y=\{y_1, \ldots, y_n\}, LCS asks to return a longest common subsequence of them. NOTE: {x1,x3,x5}\{x_1, x_3, x_5\} is a subsequence of XX (no need to be consecutive in the original sequence!!)

Let's define Xm={x1,x2,,xm},Yn={y1,y2,,yn}X_m = \{x_1, x_2, \ldots, x_m\}, Y_n = \{y_1, y_2, \ldots, y_n\}, and think about LCS of XmX_m and YnY_n. If xm=ynx_m = y_n,

LCS(Xm,Yn)=LCS(Xm1,Yn1)+xm\text{LCS}(X_m, Y_n) = \text{LCS}(X_{m-1}, Y_{n-1}) + x_m

If xmynx_m \neq y_n,

LCS(Xm,Yn)=ReturnLongerOne{LCS(Xm1,Yn), LCS(Xm,Yn1)}\text{LCS}(X_m, Y_n) = \text{ReturnLongerOne}\big\{\text{LCS}(X_{m-1}, Y_n),~\text{LCS}(X_m, Y_{n-1})\big\}

Time complexity is O(mn)O(mn).


Cracking the coding interviews

Trees (+ Graphs)

  • Binary Tree vs Binary Search tree

    • In a Binary search tree, every node (and its descendants) satisifies a specific ordering
  • Balanced vs Unbalanced

    • Complete Binary Trees: every level of the tree is fully filled, except for perhaps the last level (all nodes are as far left as possible)
    • Full Binary Trees: every node has either zero or two children
    • Perfect Binary Trees: both full and complete
  • Binary Tree Traversal

    • In-order traversal: left -> root -> right
    • Pre-order traversal: root -> left -> right
    • Post-order traversal: left -> right -> root
  • Binary Heaps (Min-Heaps and Max-Heaps)

    • is a complete binary tree
    • Min-Heap: every node is smaller than its children (thus, root is the minimum)
    • Two key operations: insert and extract min element
    • Insert: start at the bottom level, and then swap with its parent until it's in the correct order
      • "Bubble up" the minimum element
    • Extract min element: Finding the min element is easy (always at the root)
        1. Replace the minimum element (i.e., root) with the last element (bottommost, rightmost)
        1. "Bubble down" the new root by swapping iteratively
  • Depth-First Search (DFS) and Breadth-First Search (BFS)

    • Implementation:
      • DFS can be simply implemented with recursion
      • BFS a bit tricky: Use a queue
    • Pros and Cons:
      • DFS: simpler to implement, uses less memory, but might not find the shortest path (in an unweighted graph (why?))
      • BFS: preferred for finding a (shortest) path, but uses more memory (queue)
        • To find the shortest path from s to t (assume running DFS / BFS from s), it's a good idea to stay close to s (BFS) rather than going far away (DFS)
  • Bidirectional Search

    • To find the shortest path between s and t
    • Much more efficient than BFS for this purpose