If you prefer to follow along via my YouTube video, you can watch it here!
In many interviews I have been asked to either just implement a common algorithm or to implement one as part of a bigger solution. The typical algorithms that you would learn in a data structures and algorithms class are very common in coding interviews. Not understanding these algorithms could cost you a job, so I wanted to share some must-know algorithms for coding interviews. If this post is helpful, please consider subscribing to my YouTube channel or following me on medium for more content like this! If you’re looking for a good resource to learn these algorithms, I recommend picking up a copy of Cracking the Coding Interview which goes over all of these and more in detail!
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²).
I hope you found this story informative! If you liked the post/video, feel free to like and subscribe to my YouTube account for more content like this. Also, if you haven’t already, make sure you pick up a copy of Cracking the Coding Interview because it really is one of the best resources for learning these algorithms and to start preparing for coding interviews!