Array
Concepts
- 2D arrays
- N-dimensional arrays
- Jagged arrays
Problems
- Two sum
- Search insert position
- Kth largest element in array
Linked List
Operations
- Insert
- Delete
- Find
- Reverse
Problems
- Counting nodes
- Finding middle element
- Merging lists
- Kth to last node
- Detecting cycles
Stack
LIFO (Last In, First Out)
Problems
Towers of Hanoi
Queue
FIFO (First In, First Out)
Tree
Concepts
- Root
- Edge
- Leaf
- Depth
- Height
Binary Tree
Binary Search Trees
Problems
- Level order traversal
- Construct tree from traversal
Balanced Trees
- AVL Tree
- B-tree
- Red-Black Tree
Operations
- Insertion
- Deletion
- Traversal (pre-order, in-order, post-order)
- Search (BFS, DFS)
- Find min/max
- Find successor/predecessor
Hash Table
Implementations
- Array
- Linked List
- Binary Tree
Operations
- Get
- Put
- Delete
Concepts
- Hash function
- Linear probing
- Quadratic probing
- Collision resolution
- Load factor
Problems
- LRU cache
Heap
Concepts
- Complete binary tree
- Priority queue
- Array representation
- Min heap
- Max heap
Priority Queue Operations
- Enqueue
- Dequeue
- Peek
- Compare function
Heap Operations
- Build
- Insert
- Get
- Delete
- Heapify
- Heap sort (in-place)
Problems
- Merge k sorted lists
- Kth largest element in array
- The skyline problem
Trie
- Compressed trie
- Suffix trie
Advanced Data Structures
- Skip list
- Suffix tree
- Suffix array
- Bloom filter
- Segment tree
- Fenwick tree (Binary Indexed Tree)
Sorting
Algorithms
- Bubble sort
- Insertion sort
- Selection sort
- Merge sort
- Quick sort
- Heap sort
- Radix sort
- Counting sort
Concepts
- Sort stability
- In-place sorting
- Comparison vs non-comparison sorts
Problems
- Dutch national flag
- Merge two sorted arrays
Graph
Concepts
- Graph theory
- Directed vs undirected graphs
- Weighted vs unweighted graphs
- Pathfinding
- Connectivity
- Shortest path
- Minimum spanning tree
- Cycles
- Disjoint graphs
Traversal
- Breadth First Search (BFS)
- Depth First Search (DFS)
Algorithms
- Bipartite graph detection
- Topological sort
- Dijkstra’s algorithm
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- Prim’s algorithm
- Kruskal’s algorithm
Representations
- Adjacency list
- Adjacency matrix
- Edge list
Recursion
Concepts
- Base case
- Recursive case
- Inductive step
- Tail recursion
- Memoization
- Backtracking
Problems
- Recursive factorial
- Recursive exponent
- Fibonacci numbers
- Pascal’s triangle
- Towers of Hanoi
- Subsets of size n
- Letter case permutations
- Subsets
- Permutations
- Subset sum
- Generate parentheses
- N-Queens
- Subarray sum equals k
- Valid parentheses
String Algorithms
Concepts
- String matching
- Pattern matching
- String search
- Data compression
- Edit distance
- Substring search
- String similarity measures
Algorithms
- Rabin-Karp
- KMP (Knuth-Morris-Pratt)
- Boyer-Moore
Problems
- First non-repeating character
- Anagram detection
- Palindrome check
- Character frequency counting
- Reverse string
Dynamic Programming
Concepts
- Optimal substructure
- Overlapping subproblems
- Memoization (top-down)
- Tabulation (bottom-up)
Problems
- 0/1 Knapsack
- Longest common subsequence
- Subset sum
- Minimum edit distance
- Minimum number of coins
- Longest increasing subsequence
- Longest palindromic subsequence
- Text justification
Computational Geometry
Network Flow Algorithms
Concepts
- Network flow
- Maximum flow
- Minimum cut
Algorithms
- Ford-Fulkerson
- Edmonds-Karp
- Dinic’s algorithm
- König’s theorem
NP-Complete
Approximation Algorithms
- Simulated annealing
- Tabu search
- Genetic algorithms
- Ant colony optimization
- Particle swarm optimization
- Cross-entropy method
Examples of NP-Complete Problems
- Set cover
- Knapsack
- Bin packing
- Vertex cover
- Hamiltonian path
- Traveling salesman
- Boolean satisfiability (SAT)
- Partition problem
- Clique problem
- Graph coloring
Search
Basic Search
- Linear search
- Binary search
Graph Search
- Depth-first search (DFS)
- Breadth-first search (BFS)
- Best-first search
- A* search
Shortest Path
- Dijkstra’s algorithm
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- Johnson’s algorithm
Algorithm Design
- Greedy algorithms
- Dynamic programming
- Divide and conquer
- Decrease and conquer
- Transform and conquer
- Randomized algorithms
- Brute force
Algorithm Analysis
Time Complexity
- Big-O notation (upper bound)
- Omega notation (lower bound)
- Theta notation (tight bound)
- Little-o notation
Space Complexity
- Auxiliary space
- In-place algorithms
Mathematical Series
- Arithmetic series
- Geometric series
- Harmonic series
- Arithmetic-geometric series