<aside>
📌 Key Points to review for a coding interview:
- Algorithm Complexity
- Sorting algorithm implementation (selection sort, merge sort, quick sort, heap sort)
- Understand sorting algorithms that work well with specific input scenarios (e.g., nearly sorted data, size of input, stability requirement, memory constraints ).
| Sorting Algorithm |
Time Complexity (Worst Case) |
Time Complexity (Average Case) |
Time Complexity (Best Case) |
Space Complexity |
Stability |
| Bubble Sort |
O(n^2) |
O(n^2) |
O(n) |
O(1) |
Stable |
| Selection Sort |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
Not stable |
| Insertion Sort |
O(n^2) |
O(n^2) |
O(n) |
O(1) |
Stable |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Stable |
| Quick Sort |
O(n^2) |
O(n log n) |
O(n log n) |
O(log n) |
Not stable |
| Heap Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
Not stable |
- Fundamental Concepts of Sorting Algorithm
- What are the TradeOffs for Each Sorting Algorithm?
</aside>
<aside>
✍️ Typical Problems:
- Implement a specific sorting algorithm (e.g., Quick Sort, Merge Sort) from scratch.
- Analyze the time and space complexity of a given sorting algorithm.
- Compare and contrast two different sorting algorithms and discuss their trade-offs.
- Modify a sorting algorithm to handle specific requirements (e.g., sorting in reverse order, sorting objects with custom comparison criteria).
- Solve sorting-related problems using a specific algorithm (e.g., finding the kth largest/smallest element, finding duplicate elements, finding a pair of elements with a specific sum).
- Optimize a given sorting algorithm for specific scenarios (e.g., already partially sorted input, limited memory constraints).
- Implement a stable sorting algorithm (or modify an existing one to maintain stability).
- Combine multiple sorting algorithms to solve a complex sorting problem efficiently.
- Design an algorithm to sort a large dataset that cannot fit into memory.
</aside>
<aside>
🌵 Table of Contents
</aside>
https://www.youtube.com/watch?v=RfXt_qHDEPw
Selection Sort
Sort 1: Selection Sort (Array)
Merge Sort
Sort 2: Merge Sort (Array)
Quick Sort
Sort 3: Quick Sort (Array)
Sort 3-1: Move 0s To The End
Sort 3-2: Rainbow Sort (3 groups)