moonbogi/cheat-sheet

Data structures & algorithms cheat sheet

cheat-sheet

This cheat sheet contains templates for common data structures and algorithms in Python.

Table of Contents

• Math
  • Fibonacci sequence
  • Line sweep
  • Reservoir sampling
• Search
  • Binary search
  • Knuth-Morris-Pratt
  • Rabin-Karp
  • Aho-Corasick
• Sorting
  • Counting sort
  • Radix sort
  • Quickselect
• Deque
  • Sliding window
  • String parsing
  • All nearest smaller values
• Tree
  • Depth-first traversal
  • Memoization
  • Level-order traversal
  • Binary tree recovery
• Graph
  • Dijkstra's algorithm
  • Bellman-Ford
  • Floyd-Warshall
  • Bipartite
  • Kruskal's algorithm
  • Prim's algorithm
  • Topological sort
  • Get neighbors
  • Convert adjacency matrix to graph
  • Flood fill
    • Flood fill borders
  • Word ladder
  • Floyd's tortoise and hare
  • Longest path
• Dynamic Programming
  • Kadane's algorithm
  • Best time to buy and sell stock
  • Single number
  • Wagner-Fischer
  • 2D prefix sum
    • 2D range sum
  • Hirschberg's algorithm
  • Longest common subsequence
  • Longest palindromic subsequence
  • Knapsack problem
  • Matrix chain multiplication