References & Quick Guide

This chapter collects all the essential reference material from the tutorial into one place. Use these tables as a quick cheatsheet when solving problems or preparing for interviews.

Data Structures — Operations & Complexities

* Average case for hash tables. Worst case: O(n) due to collisions.

Sorting Algorithms Reference

Searching Algorithms Reference

Graph Algorithms Reference

Dynamic Programming Patterns

• Fibonacci-style — DP[i] = DP[i-1] + DP[i-2]. Examples: climbing stairs, Fibonacci.
• Knapsack-style — DP[i][w] = max(DP[i-1][w], value[i] + DP[i-1][w-weight[i]]). Examples: 0/1 knapsack, subset sum, partition equal sum.
• Longest Common Subsequence — DP[i][j] = DP[i-1][j-1] + 1 if match, else max(DP[i-1][j], DP[i][j-1]). Examples: LCS, edit distance, longest palindromic subsequence.
• Longest Increasing Subsequence — DP[i] = 1 + max(DP[j]) for j < i and arr[j] < arr[i]. O(n²) or O(n log n) with patience sorting.
• Interval DP — DP[i][j] = optimal solution for subarray i..j. Examples: matrix chain multiplication, burst balloons.
• Tree DP — DP on tree nodes, usually combining child results. Examples: diameter of tree, tree max independent set.

Quick Guide Cheatsheet

Big-O Complexity Classes

O(1)       < O(log n)   < O(n)     < O(n log n)  < O(n²)     < O(2ⁿ)     < O(n!)
constant   logarithmic   linear    linearithmic   quadratic   exponential   factorial

Common Recurrence Solutions

T(n) = 2T(n/2) + O(n)      → O(n log n)   (Merge Sort)
T(n) = T(n-1) + O(1)        → O(n)         (Linear recursion)
T(n) = T(n-1) + T(n-2)      → O(2ⁿ)        (Naive Fibonacci)
T(n) = 2T(n-1) + O(1)       → O(2ⁿ)        (Subset generation)

Python Snippets for Quick Reference

# Binary search
lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == target: break
    elif arr[mid] < target: lo = mid + 1
    else: hi = mid - 1

# Tree traversals
def inorder(node): inorder(node.left); print(node); inorder(node.right)
def preorder(node): print(node); preorder(node.left); preorder(node.right)
def postorder(node): postorder(node.left); postorder(node.right); print(node)

# BFS
queue = [start]; visited = {start}
while queue:
    u = queue.pop(0)
    for v in graph[u]:
        if v not in visited: visited.add(v); queue.append(v)

# DFS recursion
def dfs(u):
    visited.add(u)
    for v in graph[u]:
        if v not in visited: dfs(v)

# DSU find with path compression
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]