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

1. Quick Sort

   • Efficient, in-place sorting algorithm with average-case time complexity O(n log n).
   • Key concepts: partitioning, divide and conquer.

2. Merge Sort

   • Stable, divide and conquer sorting algorithm with time complexity O(n log n).
   • Key concepts: merging sorted arrays, recursion.

3. Heap Sort

   • Comparison-based sorting algorithm using a heap data structure with time complexity O(n log n).
   • Key concepts: heapify, max/min heap.

4. Bubble Sort

   • Simple, comparison-based sorting algorithm with time complexity O(n^2).
   • Key concepts: swapping adjacent elements.

Searching Algorithms

1. Binary Search

   • Efficient searching algorithm for sorted arrays with time complexity O(log n).
   • Key concepts: divide and conquer, middle element comparison.

2. Depth-First Search (DFS)

   • Graph traversal algorithm using stack (or recursion) with time complexity O(V + E).
   • Key concepts: visiting nodes, recursion, backtracking.

3. 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

1. Longest Common Subsequence (LCS)

   • Finds the longest subsequence common to two sequences with time complexity O(n * m).
   • Key concepts: memoization, 2D array.

2. Knapsack Problem

   • Optimization problem with different variants (0/1, unbounded) and time complexity O(n * W).
   • Key concepts: dynamic programming table, recursion.

3. Fibonacci Sequence

   • Computes nth Fibonacci number using dynamic programming with time complexity O(n).
   • Key concepts: memoization, iterative approach.

4. Edit Distance

   • Measures the similarity between two strings with time complexity O(n * m).
   • Key concepts: dynamic programming table, string manipulation.

Graph Algorithms

1. 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.

2. Bellman-Ford Algorithm

   • Shortest path algorithm for weighted graphs, handles negative weights with time complexity O(V * E).
   • Key concepts: edge relaxation, dynamic programming.

3. Kruskal’s Algorithm

   • Minimum spanning tree algorithm with time complexity O(E log E).
   • Key concepts: sorting edges, union-find data structure.

4. 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

1. Activity Selection Problem

   • Selects the maximum number of non-overlapping activities with time complexity O(n log n).
   • Key concepts: sorting, greedy choice property.

2. Huffman Coding

   • Compression algorithm that builds an optimal prefix tree with time complexity O(n log n).
   • Key concepts: priority queue, prefix codes.

3. 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

1. KMP Algorithm (Knuth-Morris-Pratt)

   • Pattern searching algorithm with time complexity O(n + m).
   • Key concepts: prefix function, avoiding re-comparison.

2. Rabin-Karp Algorithm

   • Pattern searching algorithm using hashing with average-case time complexity O(n + m).
   • Key concepts: rolling hash, modulo operation.

3. 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

1. 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.

2. Sudoku Solver

   • Solves the Sudoku puzzle using backtracking with time complexity O(9^(n^2)).
   • Key concepts: constraint satisfaction, recursion.

3. Combination Sum

   • Finds all unique combinations that sum up to a target with time complexity exponential.
   • Key concepts: recursion, backtracking.

Tree Algorithms

1. 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.

2. AVL Tree / Red-Black Tree

   • Self-balancing BST with time complexity O(log n) for all operations.
   • Key concepts: rotations, balance factor.

3. Trie (Prefix Tree)

   • Data structure for storing dynamic sets of strings, supporting efficient search operations.
   • Key concepts: nodes, edges, prefix matching.

Miscellaneous

1. 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.

2. Topological Sort

   • Linear ordering of vertices in a directed acyclic graph (DAG) with time complexity O(V + E).
   • Key concepts: DFS, in-degree.

3. 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.