I gave 127 interviews. Top 5 Algorithms they asked me.

Key Concepts:

1. Introduction

The video focuses on the most frequently asked algorithms in coding interviews at top tech companies like Google, Facebook, and Amazon.
The speaker emphasizes that knowing a select few algorithms well (the "20%") is more effective than trying to learn every algorithm.
The video aims to provide a list of the top 5 algorithms, along with specific problems where they can be applied.

2. Top K Elements Algorithm

Main Idea: Finding the k largest or smallest elements in an array, or the k most frequent elements.
Example: Finding k largest numbers in an array.
Inefficient Approach: Sorting the array (O(n log n) time complexity).
Efficient Approach: Using a heap data structure to track the top k largest numbers.
Process:
1. Add the first k numbers of the array to a heap.
2. For each subsequent number in the array:
  - Add the number to the heap.
  - Remove the minimum number from the heap.
- This maintains a heap of size k containing the largest k numbers seen so far.
Time Complexity: O(n log k) because adding and removing from the heap takes O(log k) time, and this is done for each of the n numbers in the array.
Data Structure: Heap (efficient for getting the maximum or minimum number).

3. Sliding Window Algorithm

Main Idea: Efficiently processing contiguous subarrays or substrings of a given size.
Examples: Largest Substring Without Repeating Characters, Maximum Sum Subarray of Size k, Largest Substring with k Distinct Characters.
Example Problem: Largest Substring Without Repeating Characters.
Process:
1. Initialize two pointers, left and right, at the beginning of the string.
2. Increment the right pointer to expand the window.
3. Store information about the characters present in the window (e.g., using a hash map).
4. If a repeating character is found:
  - Update the answer (maximum window size).
  - Increment the left pointer to shrink the window until the repeating character is no longer in the window.
  - Remove the characters that are no longer in the window from the stored information.
5. Repeat steps 2-4.
Key Idea: The algorithm "slides" the window across the input, maintaining a valid window at each step.

4. Backtracking

Main Idea: Exploring all possible solutions by building them step by step. If an invalid state is reached, backtrack and explore other possibilities.
Implementation: Typically implemented using recursion.
Example Problem: Combination Sum (given a list of positive numbers and a target sum, find all unique combinations that add up to the target sum, allowing numbers to be picked more than once).
Process:
1. Start with an empty combination and a current sum of 0.
2. If the current sum exceeds the target, backtrack (return).
3. If the current sum equals the target, add the combination to the answer and return.
4. Otherwise, for each number after the current index:
  - Add the number to the combination.
  - Update the current sum.
  - Update the current index.
  - Recursively call the function.
Applications: Word Ladder, Permutations, Sudoku Solver.

5. Dynamic Programming

Main Idea: Breaking a problem into smaller overlapping subproblems, solving each subproblem only once, and storing the results to avoid recomputation.
Comparison to Backtracking: Dynamic programming is more thoughtful about the solutions it explores, avoiding redundant computations.
Example Problem: Combination Sum (revisited).
Process (using the Combination Sum example):
1. Imagine you have all combinations that add up to target sum - 1, target sum - 2, etc., using all numbers except the last one.
2. Given the last number, you can find all combinations that add up to the target sum by adding the last number to the appropriate combinations from the subproblems.
3. Keep track of all sums from 1 to the target using an array.
4. For target sum 0, add an empty list (base case).
5. Iterate through the numbers and for each number, iterate through the target sums.
6. For a particular target sum, add more combinations by using all the combinations for target sum - current number.
Key Idea: Storing and reusing solutions to subproblems to avoid redundant computations.

6. Breadth-First Search (BFS) and Depth-First Search (DFS)

Main Idea: Algorithms for traversing graphs.
DFS: Explores as far as possible along each branch before backtracking. Implemented using a stack (Last-In, First-Out). Explores the neighbors of the last vertex visited first.
BFS: Explores neighboring vertices first before moving to deeper unvisited vertices. Implemented using a queue (First-In, First-Out). Explores the neighbors of the first vertex visited first.
Applications:
- BFS: Finding the shortest path from Vertex A to Vertex B.
Related Algorithms: Dijkstra's algorithm (also finds the shortest path), Topological Sort (closely related to DFS).

7. Conclusion

Mastering these 5 algorithms requires a deep understanding of data structures.
These 5 algorithms are not sufficient to crack all coding interviews, but they represent a significant portion of frequently asked questions.
The speaker recommends watching another video for advice on mastering data structures and algorithms.