Data Structure & Algorithm

Time Complexity Expressions:

  • Omega: best scenario

  • Theta: average scenario

  • Big-O: worst scenario

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

Linear Algebra

PreviousMemoNextDatabase

Last updated