What are the must-know algorithms for coding interviews?

To excel in coding interviews, it's crucial to have a solid understanding of a variety of algorithms and data structures. Here are some must-know algorithms, categorized by their primary applications and types:

Sorting Algorithms

Quick Sort
- Efficient, in-place sorting algorithm with average-case time complexity O(n log n).
- Key concepts: partitioning, divide and conquer.
Merge Sort
- Stable, divide and conquer sorting algorithm with time complexity O(n log n).
- Key concepts: merging sorted arrays, recursion.
Heap Sort
- Comparison-based sorting algorithm using a heap data structure with time complexity O(n log n).
- Key concepts: heapify, max/min heap.
Bubble Sort
- Simple, comparison-based sorting algorithm with time complexity O(n^2).
- Key concepts: swapping adjacent elements.

Searching Algorithms

Binary Search
- Efficient searching algorithm for sorted arrays with time complexity O(log n).
- Key concepts: divide and conquer, middle element comparison.
Depth-First Search (DFS)
- Graph traversal algorithm using stack (or recursion) with time complexity O(V + E).
- Key concepts: visiting nodes, recursion, backtracking.
Breadth-First Search (BFS)
- Graph traversal algorithm using queue with time complexity O(V + E).
- Key concepts: visiting nodes level by level, queue.

Dynamic Programming

Longest Common Subsequence (LCS)
- Finds the longest subsequence common to two sequences with time complexity O(n * m).
- Key concepts: memoization, 2D array.
Knapsack Problem
- Optimization problem with different variants (0/1, unbounded) and time complexity O(n * W).
- Key concepts: dynamic programming table, recursion.
Fibonacci Sequence
- Computes nth Fibonacci number using dynamic programming with time complexity O(n).
- Key concepts: memoization, iterative approach.
Edit Distance
- Measures the similarity between two strings with time complexity O(n * m).
- Key concepts: dynamic programming table, string manipulation.

Graph Algorithms

Dijkstra’s Algorithm
- Shortest path algorithm for weighted graphs with non-negative weights, time complexity O(V^2) or O(E + V log V) with a priority queue.
- Key concepts: priority queue, relaxation.
Bellman-Ford Algorithm
- Shortest path algorithm for weighted graphs, handles negative weights with time complexity O(V * E).
- Key concepts: edge relaxation, dynamic programming.
Kruskal’s Algorithm
- Minimum spanning tree algorithm with time complexity O(E log E).
- Key concepts: sorting edges, union-find data structure.
Prim’s Algorithm
- Minimum spanning tree algorithm with time complexity O(E + V log V) using a priority queue.
- Key concepts: priority queue, spanning tree.

Greedy Algorithms

Activity Selection Problem
- Selects the maximum number of non-overlapping activities with time complexity O(n log n).
- Key concepts: sorting, greedy choice property.
Huffman Coding
- Compression algorithm that builds an optimal prefix tree with time complexity O(n log n).
- Key concepts: priority queue, prefix codes.
Job Scheduling Problem
- Optimizes job sequence to minimize maximum completion time with time complexity O(n log n).
- Key concepts: sorting, greedy choice.

String Algorithms

KMP Algorithm (Knuth-Morris-Pratt)
- Pattern searching algorithm with time complexity O(n + m).
- Key concepts: prefix function, avoiding re-comparison.
Rabin-Karp Algorithm
- Pattern searching algorithm using hashing with average-case time complexity O(n + m).
- Key concepts: rolling hash, modulo operation.
Trie (Prefix Tree)
- Data structure for efficient retrieval of keys in a dataset of strings with time complexity O(m) for search/insert.
- Key concepts: nodes and edges representing characters, prefix matching.

Backtracking

N-Queens Problem
- Places N queens on an N×N chessboard so that no two queens threaten each other with time complexity O(N!).
- Key concepts: recursion, backtracking.
Sudoku Solver
- Solves the Sudoku puzzle using backtracking with time complexity O(9^(n^2)).
- Key concepts: constraint satisfaction, recursion.
Combination Sum
- Finds all unique combinations that sum up to a target with time complexity exponential.
- Key concepts: recursion, backtracking.

Tree Algorithms

Binary Search Tree (BST) Operations
- Efficient searching, insertion, and deletion with average-case time complexity O(log n).
- Key concepts: binary tree, in-order traversal.
AVL Tree / Red-Black Tree
- Self-balancing BST with time complexity O(log n) for all operations.
- Key concepts: rotations, balance factor.
Trie (Prefix Tree)
- Data structure for storing dynamic sets of strings, supporting efficient search operations.
- Key concepts: nodes, edges, prefix matching.

Miscellaneous

Union-Find (Disjoint Set Union)
- Data structure for keeping track of disjoint sets with time complexity O(α(n)) per operation.
- Key concepts: path compression, union by rank.
Topological Sort
- Linear ordering of vertices in a directed acyclic graph (DAG) with time complexity O(V + E).
- Key concepts: DFS, in-degree.
Sliding Window
- Technique for problems involving subarrays or substrings with time complexity O(n).
- Key concepts: two-pointer technique, maintaining a window.

Mastering these algorithms will significantly enhance your ability to solve a wide range of coding interview problems. Practice implementing these algorithms and understanding their underlying principles to prepare effectively for coding interviews.