link: https://www.youtube.com/watch?v=nr08biZfSZ3Y

Top 7 Algorithms for Coding Interviews Explained Simply

Introduction

7 most important algorithms for coding interviews:
1. Binary Search
2. Depth-First Search (DFS)
3. Breadth-First Search (BFS)
4. Insertion Sort
5. Merge Sort
6. Quick Sort
7. Greedy Algorithms
Data Structures and Time Complexity are recommended prerequisites.

What it is: Finds the position of an element in a sorted list.
How it works: Repeatedly divides the search space in half until the target element is found.
Example: Guessing a number between 1-100 by starting in the middle.
Efficiency: O(log n) time complexity (log base 2).
Key takeaway: Efficient on sorted lists, making it a go-to for those types of problems.

What it is: Used to search through trees and graphs.
How it works: Starts at the root, explores as far down a branch as possible before backtracking.
Example: Solving a maze by following a path to its end and backtracking if a wall is hit.
Efficiency: O(V + E), where V = vertices, E = edges.
Key takeaway: Useful for graph traversal, especially for exploring all paths.

What it is: Another search method for trees and graphs.
How it works: Explores all nodes at the present level before moving deeper.
Example: Chess algorithms for evaluating possible moves.
Efficiency: O(V + E), same as DFS.
Key takeaway: Better for finding the shortest path in unweighted graphs.

What it is: A simple sorting algorithm.
How it works: Compares elements and swaps them into the correct order by iterating over the list.
Efficiency: Best-case O(n) when nearly sorted, worst-case O(n^2) when unordered.
Key takeaway: Efficient for small or mostly sorted lists but not for larger ones.

What it is: A divide-and-conquer sorting algorithm.
How it works: Recursively splits the array into smaller subarrays, sorts them, and then merges them.
Efficiency: O(n log n) in both best and worst cases.
Key takeaway: Ideal for larger or more unordered lists compared to Insertion Sort.

What it is: Another divide-and-conquer sorting algorithm.
How it works: Picks a pivot and partitions the list into elements smaller and larger than the pivot, recursively sorting subarrays.
Efficiency: Best-case O(n log n), but worst-case O(n^2) if the pivot is poorly chosen.
Key takeaway: Faster on average than merge sort, but requires careful implementation to avoid pitfalls like poor pivot selection.

What it is: Makes the locally optimal choice at each step without considering future consequences.
When not to use: When the problem requires global optimization, as it can lead to suboptimal solutions.
Example of failure: A path selection problem where the greedy algorithm selects the lowest immediate cost at each step, but misses the globally optimal path.
When to use: When the problem naturally fits into a locally optimal framework.

Mastering these 7 algorithms provides a strong foundation for acing coding interviews.
Understanding their time complexities, when to use each, and how to implement them efficiently is crucial.