Here is a categorized list of algorithms and techniques that are essential for cracking interviews at FAANGM (Facebook/Meta, Amazon, Apple, Netflix, Google, Microsoft) companies. These algorithms are grouped based on data structures and problem types, along with tips for identifying when to use them.
1. Arrays
Key Algorithms and Techniques
Two-Pointer Technique
When to use: When the problem involves finding pairs, triplets, or partitions in sorted/unsorted arrays.
Examples:
Finding a pair with a given sum.
Sorting colors (Dutch National Flag problem).
Sliding Window
When to use: When the problem involves subarrays or substrings with specific properties (e.g., fixed/variable length).
Examples:
Maximum sum subarray of size K.
Longest substring with at most K distinct characters.
Kadane's Algorithm
When to use: To find the maximum sum subarray.
Examples: Maximum subarray problem.
Merge Intervals
When to use: When the problem involves overlapping intervals or intervals manipulation.
Examples:
Merging overlapping intervals.
Meeting room scheduling.
Cyclic Sort
When to use: When dealing with problems involving permutations of numbers from 1 to N.
Examples:
Finding missing numbers.
Detecting duplicates.
2. Strings
Key Algorithms and Techniques
Knuth-Morris-Pratt (KMP) Algorithm
When to use: To find patterns in strings efficiently.
Examples: String search, substring match.
Rabin-Karp Algorithm
When to use: When dealing with multiple pattern matching or substring search.
Examples: Detecting plagiarism.
Sliding Window (for Strings)
When to use: When dealing with substring problems.
Examples:
Longest substring without repeating characters.
Minimum window substring.
Trie (Prefix Tree)
When to use: Problems involving prefixes or dictionaries.
Examples:
Word search in a grid.
Autocomplete systems.
Z Algorithm
When to use: For pattern matching and finding repetitions in strings.
Examples: Substring search, string compression.
3. Linked Lists
Key Algorithms and Techniques
Reversal
When to use: Reversing parts of a linked list.
Examples: Reverse nodes in groups.
Fast and Slow Pointers
When to use: Detecting cycles or finding the middle element.
Examples:
Detecting a cycle in a linked list.
Finding the starting point of the cycle.
Merge Sort
When to use: Sorting a linked list.
Examples: Sorting a singly or doubly linked list.
4. Trees
Key Algorithms and Techniques
Binary Search Tree (BST) Traversals
When to use: Searching, inserting, or deleting elements.
Examples: Validating a BST.
Depth-First Search (DFS)
When to use: To explore all paths or nodes in a tree.
Examples:
Finding the maximum depth of a binary tree.
Path sum problems.
Breadth-First Search (BFS)
When to use: Level-order traversal or shortest path.
Examples: Zigzag level order traversal.
Lowest Common Ancestor (LCA)
When to use: Problems involving ancestor relationships.
Examples: Finding the LCA of two nodes.
Segment Trees and Fenwick Trees
When to use: When dealing with range queries or updates.
Examples: Range sum or minimum queries.
5. Graphs
Key Algorithms and Techniques
Depth-First Search (DFS)
When to use: When exploring paths or checking connectivity.
Examples:
Detecting cycles.
Connected components.
Breadth-First Search (BFS)
When to use: Finding the shortest path in an unweighted graph.
Examples: Word ladder problem.
Dijkstra’s Algorithm
When to use: Finding the shortest path in a weighted graph.
Examples: Navigation systems.
Kruskal's and Prim's Algorithms
When to use: Finding the minimum spanning tree.
Examples: Network connection problems.
Topological Sort
When to use: For problems involving dependencies.
Examples: Course scheduling.
Union-Find
When to use: Problems involving connected components or cycle detection.
Examples: Redundant connection in a graph.
6. Dynamic Programming
Key Algorithms and Techniques
Knapsack Problems
When to use: Resource optimization problems.
Examples:
Subset sum.
Partition problem.
Longest Common Subsequence (LCS)
When to use: Comparing sequences.
Examples: Text similarity.
Matrix Chain Multiplication
When to use: Optimal parenthesization problems.
Examples: Multiplying matrices with minimum cost.
Floyd-Warshall Algorithm
When to use: All-pairs shortest paths.
Examples: Finding shortest paths in a graph.
Bellman-Ford Algorithm
When to use: Shortest paths in a graph with negative weights.
Examples: Currency arbitrage.
7. Recursion and Backtracking
Key Algorithms and Techniques
Subset and Permutation Generation
When to use: Generating combinations or permutations.
Examples:
Subsets of a set.
Permutations of a string.
N-Queens Problem
When to use: Placing objects under constraints.
Examples: Chessboard problems.
Sudoku Solver
When to use: Solving grid-based puzzles.
Examples: Sudoku, crossword puzzles.
8. Greedy Algorithms
Key Algorithms and Techniques
Activity Selection
When to use: Maximizing the count of non-overlapping intervals.
Examples: Interval scheduling.
Huffman Encoding
When to use: Data compression.
Examples: Compressing text files.
Dijkstra's Algorithm
- When to use: When greedily finding the shortest path works.
How to Identify the Algorithm from the Problem
Subarray/Subsequence Problems: Use Sliding Window or Kadane's Algorithm.
Pattern Search in Strings: Use KMP or Trie.
Cycle Detection in Graphs: Use DFS or Union-Find.
Matrix Problems: Use Dynamic Programming or DFS/BFS.
Optimal Resource Allocation: Use Knapsack or Greedy Algorithms.
Dependency Resolution: Use Topological Sort.
Master these algorithms and practice solving problems on platforms like LeetCode, HackerRank, and Codeforces to build a solid foundation for FAANGM interviews! 🚀