Data Structure & Algorithm

Time Complexity Expressions:

• Omega: best scenario

• Theta: average scenario

• Big-O: worst scenario

  • Big-O cheatsheet

Trees

• BST (Binary Search Tree)

  • Adding element according to status of children (can become an unbalanced BST in worst cases).

  • Having Θ(log N), O(N) for access, search, insertion, deletion due to the BST is balanced or not.

• Red-black Tree

  • Self-balanced (not perfectly balanced) BST with O(log N) for searching, insertion, deletion.

• Heap

  • Adding elements from left to right and check its ancestors (no need to re-balancde it.)

  • Good at finding max / min and adding elements. Ex. priority queue, sorting algorithm.

  • Having O(1) for finding max /min, O(log N) for insertion, deletion, O(N) for lookup.

• Trie (prefix tree)

  • Usually a empty root node, can have multiple children nodes.

  • For auto-completion lookup.

• Tree Traversal (Depth First Search)

  • Pre-order: self -> left -> right.

  • In-order: left -> self -> right.

  • Post-order: left -> right -> self.

Sorting

• Types and Implementations:

  • Selection Sort (not practical)

    • IMPL: Search the min (max) value and swap to the front in each round.

  • Bubble Sort (not practical)

    • IMPL: Compare with neighbor and swap.

  • Insertion Sort

    • Good at dealing with small data set (or almost sorted data set).

    • IMPL: Create sub-group with size 1 at the front, move edge element into sub-group by bubble sorting in each round.

  • Merge Sort

    • Stable time complexity: N log N, but space complexity is O(N).

    • IMPL: A recursive function to split array (sub-array) into 2 halves till becoming single element and then merge them back.

  • Quick Sort

    • Good space complexity with O(log N), and time complexity: linearithmic Θ(N log N)and quadratic O(N^2) if chosed worst pivot.

    • IMPL:

      • Choose strategy for pivot (Ex. at the end.)

      • A recursive function to :

        • (1) move elements larger then pivot to the right, keep smaller elements at the left.

        • (2) sub-array at the left calls step (1)

        • (3) sub-array at the right calls step (1)

  • Heap Sort

    • Stable time complexity: N log N, and good space complexity: O(1).

    • IMPL: Given root as index: 0.

      • index of parent: (i - 1) / 2

      • index of left child = 2i + 1.

      • index of right child: 2i + 2.

  • External Sort

Searching

• Linear search (checking elements sequentially)

• Binary search (check sorted elements from the middle)

• BFS

  • Good at finding shortest path, but takes more memory to keep track of neighbors.

  • Impl: Queue

• DFS

  • To identify a path especially when it's far away from the source (Ex. a maze), with less memory.

  • Impl: Stack

Recursion

• Fibonacci

  • Time complexity: O(2 ^ N) (exponential, pronounced as "two to the N").

• Find tree depth

  • return 1 + Math.max(findMax(node.left), findMax(node.right));

Dynamic Programming (Caching)

• Fibonacci

  • Time complexity: O(N), space complexity: O(N).

Graph

• Example

  • 2 - 0 / \ 1 - 3

• Example with primitive representations

  • Edge List

    • int[][] data = {{0, 2}, {1, 2}, {1, 3}, {2, 3}};

  • Adjacent List

    • int[][] data = {{2}, {2, 3}, {0, 1, 3}, {1, 2}};

  • Adjacent Matrix

    • int[][] data = { {0, 0, 1, 0}, {0, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}};

• Finding shortest path with weight

  • Dijkstra's algorithm (more effecient but can only take positive weight)

  • Bellman-Ford algorithm (can take negative weight)

Bit Manipulation

• Find the single number in an array

Linear Algebra

• Matrix

  • Multiplication
  • 線性代數的第一堂課──矩陣乘法的定義