Data structures and algorithms for interviews

This repository contains C++ implementations of general algorithms and data structures.

For a quick revision checkout the readme files for each topic.

Algorithm analysis
- Solving recurrences
  - Iteration Method
  - Substitution Method
  - Recurrence Tree Method
  - Master Method
- Amortized Analysis
Searching, Sorting and Order Statistics Readme
1. Searching
2. Sorting
  - Insertion Sort
  - Selection Sort
  - Bubble Sort
  - Bucket Sort
  - Merge Sort
  - Heap Sort
  - Quick Sort
  - Counting Sort
  - Radix Sort
3. Order Statistics
  - Minimum and maximum
Algorithmic Paradigms
1. Complete Search
  - N-queen
2. Divide and Conquer
  - Strassen's algorithm for matrix multiplication
3. Dynamic programming
  - 0-1 Knapsack
  - Coin change
  - 1D Range Sum Query
  - Longest Increasing Subsequence
  - Longest Common Subsequence
  - Matrix Chain Multiplication
  - Optimal Binary Search Tree
  - Binomial Coefficient
  - Ways to add upto an integer
  - Number of paths in a dag
  - Knuth optimization
  - Convex hull optimizations
  - RMQ (sparse table a.k.a 2^k-jumps)
  - Bitonic cycle
  - Log partitioning (loop over most restricted)
  - 3^n set cover
  - DP over intervals
  - DP over subsets
  - DP over probabilities
  - DP over trees
4. Greedy algorithm
  - Task Scheduling
  - Max contiguous subvector sum
  - Invariants
  - Huffman encoding
  - Matroid
  - Activity Selection
  - Fractional Knapsack
Trees Readme
- Binary Tree
  - Traversal
    - DFS (preorder, inorder, postorder)
    - BFS (levelorder)
    - Morris
    - Vertical
    - Diagonal
    - Boundary
  - Views
    - top
    - side
  - Binary Search Tree
  - AVL Trees
  - Red-Black Trees
- Treap
- Splay Tree
- N-ary Tree
- Trie
- Suffix Tree
- Huffman Tree
- Heap
- B+, B- Tree
- Merkle Tree
- Segment Tree
- Fenwick Tree (Binary Indexed Tree)
- Square Root Decomposition
Graph theory
- Traversals
  - Depth first search
  - Breadth first search
  - Flood-Fill (DFS)
  - Forest-Fire (BFS)
- Topological Sort
  - Using modified DFS/BSF
  - Kahn algorithm
- Articulation points and bridges (Undiredted graphs)
- Strongly connected components (Directed graphs)
  - Tarajan algorithm
  - Kosaraju algorithm
- Vertex coloring
  - Bipartite graphs (=> trees)
  - 3^n (special case of set cover)
- Edge coloring
  - Trees
- Union-Find Disjoint Sets
- Minimum spanning tree (Undirected Graphs)
  - Kruskal algorithm
  - Prim algorithm
  - Boruvka algorithm
  - Steiner Tree
  - Bernard Chazelle
- Minimum spanning tree (Arborescence/ Directed Graphs)
  - Chu–Liu/Edmonds algorithm.
- Shortest paths
  - Bellman-Ford algorithm
  - SPFA (Shortest Path Faster Algorithm)
  - Dijkstra algorithm
  - A* algorithm
  - Floyd-Warshall algorithm
  - Johnson algorithm
- Paths and circuits
  - Eulerian path
  - Hamiltonian path
  - De Bruijn sequences
  - Knight's tour
- Network flows and cuts
  - Ford-Fulkerson algorithm
  - Augmenting paths
  - Edmonds-Karp
- Matching
  - Maximal matching, general graphs
  - Bipartite matching
- Min-cost max flow
- Shortest cycle
- Konig's theorem and vertex cover
- Lovasz toggle
- Matrix tree theorem
- Hopcroft-Karp
- Hall's marriage theorem
- Graphical sequences
- Min. path cover
- Cut vertices, cut-edges and biconnected components
- Diameter and centroid
- K'th shortest path
- 2-SAT
- Dynamic graphs (extra book-keeping)
Math
1. Combinatorics
  - Computation of binomial coefficients
  - Pigeon-hole principle
  - Inclusion/exclusion
  - Catalan number
  - Pick's theorem
2. Number theory
  - Integer parts
  - Divisibility
  - Euclidean algorithm
  - Modular arithmetic
    - Modular multiplication
    - Modular inverses
    - Modular exponentiation by squaring
  - Chinese remainder theorem
  - Fermat's little theorem
  - Euler's theorem
  - Phi function
  - Frobenius number
  - Quadratic reciprocity
  - Pollard-Rho
  - Miller-Rabin
  - Hensel lifting
  - Vieta root jumping
3. Game theory
  - Combinatorial games
  - Game trees
  - Mini-max
  - Nim
  - Games on graphs
  - Games on graphs with loops
  - Grundy numbers
  - Bipartite games without repetition
  - General games without repetition
  - Alpha-beta pruning
4. Numerical methods
  - Numeric integration
  - Newton's method
  - Root-finding with binary/ternary search
  - Golden section search
5. Matrices
  - Gaussian elimination
  - Exponentiation by squaring
Geometry
- Coordinates and vectors
  - Cross product
  - Scalar product
- Convex hull
- Polygon cut
- Closest pair
- Coordinate-compression
- Quadtrees
- KD-trees
- All segment-segment intersection
Strings
- Knuth-Morris-Pratt
- Rabin Karp
- Tries
- Rolling polynomial hashes
- Suffix array
- Suffix tree
- Aho-Corasick
- Manacher's algorithm
- Letter position lists
Others
- Combinatorial search
  - Meet in the middle
  - Brute-force with pruning
  - Best-first (A*)
  - Bidirectional search
  - Iterative deepening DFS / A*
  - MiniMax
- Sweeping
  - Discretization (convert to events and sweep)
  - Angle sweeping
  - Line sweeping
  - Discrete second derivatives
- Data structures related
  - LCA (2^k-jumps in trees in general)
  - Pull/push-technique on trees
  - Heavy-light decomposition
  - Centroid decomposition
  - Lazy propagation
  - Self-balancing trees
  - Convex hull trick (wcipeg.com/wiki/Convex_hull_trick)
  - Monotone queues / monotone stacks / sliding queues
  - Sliding queue using 2 stacks
  - Persistent segment tree
- Travelling salseman
- Sliding window
- 2 pointers
- Fast & slow pointers
- Merge interval
- Cyclic Sort
- 2 Heaps
- K-way merge
- Minimax
- Line sweep
- Rolling Hash
- Reservoir sampling
- Rejection sampling
- Scan Line
- Matrix fast exponentiation
- Repeated squaring
- Euler's Theorem
- Fermat's Little theorem
- Shunting yard algorithm: expression parsing
- LRU caching

Niketdeshmukh/Data-Structures-and-Algorithms

Data structures and algorithms for interviews

Contents