To solve interview problems, you will need to know a number of common algorithms and techniques. In the next sections, we will study them in detail and go over a number of interview problems where they are used. But before we dive in, let's discuss which algorithms and techniques you need to know, and how and where to study them.
Here is a list of algorithms and techniques that you definitely need to know when preparing for coding interviews. There is a good chance that these may appear on your coding interview, and if you solve about 200-400 problems on Leetcode, you will encounter most of these at least several times.
The following algorithms and topics are rarer, but are still good-to-know and have a fair chance of occurring:
Finally, these algorithms and topics are nowhere near necessary, but they still occur at the interviews sometimes and may be helpful. You can check them out if you are already comfortable with other topics:
|Dijkstra's algorithm||String hashing (Rabin-Karp) algorithm||Knuth–Morris–Pratt algorithm|
|Segment tree||Binary indexed tree (Fenwick tree)||Probability and Combinatorics|
Make sure you know the algorithms from the must-know table above. You can create a checklist for yourself, and practice these essential algorithms one-by-one.
While solving problems on Leetcode or elsewhere, you will also encounter some algorithms that you didn't know before. When you do, it makes sense to stop, study this new algorithm properly, and solve some more problems using it.
Learning new algorithms is difficult and takes time. For each new algorithm that you study make sure that you really know it. You can follow the following process:
Read about a new algorithm, and make sure you understand everything. When possible, study the code for an algorithm too.
Answer questions like: what does this algorithm do? When is it useful?
Solve several problems on a new algorithm. When writing a solution, try to code an algorithm yourself from scratch, only using a reference code when absolutely necessary.
Thankfully, currently there are a lot of resources where you can study algorithms. Often, it is enough to just check Wikipedia or do a quick Google search.
If you are new to algorithms, it makes sense to study them more systematically, and one of the best ways to do this is to take an online course on algorithms. For example, you can take an Algorithms course on Coursera or study an Algorithms Unit on Khan Academy.
Here are some more great resources that I recommend:
Introduction to Algorithms by Cormen, et al – probably the best book on algorithms. It is very rigorous and dives deep into the heart of algorithms. When you want to deeply understand some topic in and out, this is the best resource for it.
Competitive Programmer’s Handbook by Antti Laaksonen – targeted for competitive programmers, this book gives very succinct and clear explanations of many common algorithms used in the interview questions as well. Also, unlike Introduction to Algorithms, which provides only pseudocode, Competitive Programmer’s Handbook contains working implementations in C++ for a lot of algorithms it describes.
The book is available free online. Also, it has a companion set of problems, that you can try if you are feeling adventurous :)
Cracking the Coding Interview by Gayle McDowell also has a lot of nice descriptions of interview problems and algorithms.
CP-Algorithms.com provides detailed descriptions and implementations for a lot of algorithms, especially the harder ones.