Disclaimer: This post is created based off my experience looking for internships and entry level (new grad) roles. At any point if I state you need to know an algorithm, this means you should be able to understand how it works algorithmically (including time/space complexity and being able to demonstrate your knowledge with an example) and be able to implement it in the language of your choice. Also, the link to Cracking the Coding Interview on Amazon is an affiliate link and I will receive a commission if you purchase anything on Amazon using my link. Now that we have that out of the way, let’s get to the list!
1. Tree Traversal Algorithms
These are algorithms that allow you to visit every node in a tree in a structured order. They are primarily designed for binary trees, but you can adapt these concepts to visit all the nodes in any tree. Learning these algorithms will also help you understand how to recursively traverse through all the nodes in a tree.
The three algorithms you should focus on are Pre-Order, In-Order, and Post-Order traversal. Each of these differs in the order in which they visit the nodes of a tree. I recommend understanding the order in which they visit values in a binary search tree.
2. Graph Search Algorithms
These work on trees, graphs with vertices and edges, and any encoding of a graph. These algorithms take different approaches to take you from a starting node to a destination node.
The algorithms in this class are Depth First Search (DFS), Breadth First Search (BFS), and Dijkstra’s algorithm. If you have additional time, I recommend you learn the A* algorithm as well.
3. Search Algorithms
This is a class of algorithms that really only has one important algorithm: binary search. Traditional search is an O(n) algorithm since you visit every element one at a time. If you have a sorted input list, then you can leverage binary search for an O(log(n)) runtime. I have been frequently asked to implement binary search as part of my solutions to interview questions, so I highly recommend knowing this one.
4. Sorting Algorithms
Bubble sort, insertion sort, selection sort, etc. All of these are standard algorithms that you should understand and be able to implement, but these are O(n²) for the average case algorithms. The most important sorting algorithms for interviews are the O(n*log(n)) algorithms. Two of the most common algorithms in this class are merge sort and quick sort. It is important that you know at least one of these and preferably both. I recommend starting with merge sort because it has a worst-case time complexity of O(n*log(n)) whereas quicksort drops to a worst-case O(n²).
