Coding Interviews: Essential Algorithms

Study Notes

There are seven essential algorithms to know for coding interviews, categorized into three search algorithms and three sorting algorithms, plus a special type of algorithm called a greedy algorithm.
Binary search is a search algorithm used to find the position of a specific element in a sorted list, with a runtime of O(logn), making it more efficient than linear search.
Linear search has a runtime of O(n), making it inefficient when scaled, whereas binary search is optimal for computer algorithms.
Depth-first search (DFS) is a search algorithm used to traverse through trees and graphs, with a time complexity of O(V + E), where V represents total nodes and E represents total branches.
DFS starts at the root node, goes as far down one branch as possible, and then backtracks to an unvisited branch, repeating the process until the entire graph is traversed.
One real-life example of DFS is solving a maze, where the algorithm looks through each path to find the exit, backtracking when hitting a wall.
Breadth-first search (BFS) is a search algorithm that looks at every node at one level before continuing further down, with a time complexity of O(V + E), similar to DFS.
BFS starts at the root node, adds it to the visited array, and adds all neighboring nodes to the neighbors queue, repeating the process until all nodes are visited.
One real-life example of BFS is in Chess algorithms, where the program predicts the best move by looking at each possible move and its subsequent possibilities.
Insertion sort is a simple sorting algorithm that works by comparing each element in the list and swapping them if necessary, with a best-case runtime of O(n) and worst-case runtime of O(n^2).
Insertion sort is best used for lists that are already mostly sorted or for smaller lists, as it becomes problematic for larger, more unordered lists.
Merge sort is a sorting algorithm that breaks down the problem into smaller problems, solving each smaller problem, and is better suited for larger lists.- Merge sort is a recursive algorithm with a run-time of O(n log(n)) in both best and worst cases.
Merge sort works by splitting an array in half, sorting each half, and then merging the sorted halves back together.
For smaller lists, insertion sort has a runtime closer to O(n), while merge sort has a runtime of O(n log(n)), making insertion sort a better choice.
For larger lists, insertion sort has a runtime closer to O(n^2), while merge sort remains at O(n log(n)), making merge sort a better choice.
Quick sort is a divide-and-conquer algorithm that is also recursive, with a best-case run-time of O(n log(n)) and a worst-case run-time of O(n^2).
Quick sort works by selecting a pivot element, partitioning the array around the pivot, and recursively sorting the sub-arrays.
Quick sort has a space complexity of O(log n), making it more memory-efficient than merge sort, which has a space complexity of O(n).
However, quick sort's performance relies heavily on optimized code, and small mistakes can greatly impact its performance.
Greedy algorithms make the best possible choice at each local decision point, but may not always find the optimal solution.
Greedy algorithms are used when finding the optimal solution is not possible, and a relatively accurate solution is acceptable.
The traveling salesman problem is an example of a problem where a greedy algorithm can be used to find a relatively efficient solution.
The traveling salesman problem involves finding the shortest route that visits each city once and returns to the starting city.
The number of possible routes in the traveling salesman problem grows exponentially with the number of cities, making it impractical to find the optimal solution.
A greedy algorithm can be used to find a relatively efficient solution by always choosing the next city that is closest to the current city.

Description

Learn about the seven essential algorithms you need to know for coding interviews, including search algorithms, sorting algorithms, and a greedy algorithm. Understand the time and space complexities of each algorithm and their real-life applications.