Over the past few years, I’ve interviewed with a dozen or so companies and have completed ~50 or so individual algorithm problems. I’m frequently given feedback that I did a great job at the algorithms problem. In this post, I’m going to share how exactly I approach algorithm problems.

Thought Process

A guiding principle I use is that every interview problem is designed to be solved. You aren’t going to be asked to prove Fermat’s Last Theorem in an interview. If you are given some impossible problem, it’s not like you’re going to have much of a chance anyways.

In my experience, around 80% of the time an algorithm problem will boil down to a few core data structures and algorithms. The data structures I see the most are are:

• Hash Tables
• Linked Lists
• Binary Search Trees

As for the algorithms:

• Depth-first search
• Binary Search
• Sorting Algorithms

(You probably won’t be expected to implement a binary search or sorting algorithm, but you should be aware that they exist.)

There’s also two additional programming techniques you should be aware of:

• Dynamic Programming
• Recursion

Assuming the solution to your problem can be solved using the items in this list, we can come up with a simple algorithm to solve the problem.

The Algorithm

The algorithm goes like this:

1. After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you.
2. Filter out the data structures and algorithms that obviously aren’t relevant to the problem at hand. This will eliminate most of the list and you will usually be left with 2-3 data structures and algorithms.
   1. You can filter out data structures that are too slow. If you need to solve a problem in O(1) time, it’s impossible to use a binary tree in the solution, because a binary tree will always take at least O(log n) time. 
   2. You can filter out algorithms if they are impossible to use for the given problem. If there isn’t a graph in the problem, you know that depth-first search can’t be relevant.
3. Go through the use cases for the remaining data structures and see which ones are relevant to the problem at hand. The solution for the problem is going to be a combination of these use cases. All you need to do is piece together these different use cases and you’ll come up with the solution to the problem.

Let’s go through the runtimes and main use cases for each data structure and algorithm. Then walk through a few examples so you can see just how easy it is to use the algorithm.

Runtimes and Use Cases

Algorithm or Data Structure	Runtime	Use Cases
Hash Tables	O(1) insertion, lookup, and deletion.	When you only need to store and lookup objects. When you need to partition a list of objects distinct groups by some property (basically what a group by in SQL does) You need to count the number of distinct items in a list.
Linked Lists	O(1) insertion, lookup, and deletion at the ends or next to a node you already have a pointer to.	The main use cases of a linked list revolve around the fact that a linked list maintains relative ordering of the elements. In programming interviews, a linked list is primarily used as either a stack or queue.
Binary Trees	O(log n) insertion, lookup, and deletion.	Used when you need to keep your data in sorted order. This lets you quickly answer questions like how many elements fall into a given range or what is the Nth highest element in the tree.
Binary Search	O(log n)	You need to find the number in a sorted array closest to another number. You need to find the smallest number in a sorted array that is larger than another number. You need to find the largest number in a sorted array that is smaller than another number. If you aren’t able to use a hash table for whatever reason, you can use a binary search to check if a given element is in a sorted array.
Depth-first Search	O(n)	Traverse an entire graph. Find a specific element in a graph. Find the connected components of a graph.
Sorting	O(n log n)	Can be used if you need to process elements in a specific order. First sort by that order, then iterate through the elements. Can be used to sort an array that you will later perform binary search on.

Dynamic programming and recursion are a bit different in that they are general techniques for solving algorithm problems and not specific algorithms themselves. This means they don’t have concrete runtimes or use cases. The good news is after a bit of practice, it becomes fairly easy to recognize programs that can be solved with dynamic programming or recursion. My recommendation is practice a few problems that require dynamic programming or recursion so you can get a feel for them. Fully explaining dynamic programming and recursion is outside the scope of this post.

Examples

Now let’s take a look at a few different interview problems and how we can use the algorithm to solve them.

Problem #1: Build a rate limiter

This is a problem that I’ve seen multiple times across several different companies.

You need to write a function that can only be called at most N times within any 1 minute window. For example, it can be called at most 10 times in a minute. If the function is called more than N times it should throw an exception. The function should have expected O(1) performance.

Take a look at the data structures and algorithms we can use and see which ones can be used to solve the problem. Then try to see how you can use those data structures to solve the problem. Give it a shot before moving onto the solution.

• Hash Tables
• Linked Lists
• Binary Trees
• Depth-first search
• Binary Search
• Sorting
• Dynamic Programming
• Recursion

Solution

Let’s start by eliminating all the data structures and algorithms that obviously can’t be used:

• Hash Tables
• Linked Lists
• Binary Trees – Too slow.
• Depth-first search – Too slow. There’s also no graph to run DFS on.
• Binary Search – Too slow. Also no sorted array.
• Sorting – Too slow. There’s also no elements to sort.
• Dynamic Programming – No way to apply dynamic programming to the problem.
• Recursion – No way to apply recursion to the problem.

That leaves just hash tables and linked lists. If we go through the common use cases for hash tables, there doesn’t appear to be any way to apply them to the problem.  We don’t need to quickly lookup different objects and we don’t need to partition a list of objects into different groups. That means we can cross off hash tables from the list.

The only data structure remaining are linked lists. Looking at the use cases the only two are for a stack and a queue. Can we use either of those to keep track of how many times a function has been called in the last minute? Yes! What we can do is keep a queue that has one entry for each time the function was called within the last minute. Whenever the function is called, we remove all entries from the queue that were inserted more than a minute ago. If the queue still has a length greater than N, we throw an exception. Otherwise we add a new entry to the queue with the current time. By keeping track of the length of the queue with a counter, we can determine with O(1) expected time, this function will have O(1) expected performance.

Problem #2: Anagrams

Given a list of words, produce a list of words in the input that are anagrams of at least one other word in the list. Two words are anagrams of each other if you can rearrange the letters in one to get the other. The runtime should be O(n) assuming the words have constant length.

Again attempt the problem yourself before reading the solution. Here’s the complete list of data structures and algorithms for reference:

• Hash Tables
• Linked Lists
• Binary Trees
• Depth-first search
• Binary Search
• Sorting
• Dynamic Programming
• Recursion

Solution

Let’s start by eliminating the items from the list that can’t possibly be used for this problem:

• Hash Tables
• Linked Lists
• Binary Trees – Too slow.
• Depth-first search – There’s no graph.
• Binary Search – There’s no sorted array.
• Sorting – Too slow.
• Dynamic Programming – No way to apply DP to the problem.
• Recursion – No way to apply recursion to the problem.

That leaves us with just hash tables and linked lists. Linked lists don’t seem to be relevant to the problem since it doesn’t look like there’s any way a stack or queue would help us. That leaves only hash tables left.

The only hash table use case that seems relevant here is the ability to split apart elements in a list into separate groups based on a property. In this case, if had a way to split the list into separate groups based on which words are anagrams of each other, that would give us a way to solve the problem:

1. Split the list of words into separate groups based on which words are anagrams of each other.
2. Append all the groups together that have more than one word in it. This will produce a list of words that are anagrams of at least one other word in the input list.

The only bit that’s left to solve is to find some property we can use to group anagrams together. We need to find some function f such that f(x) is the same as f(y) when x and y are anagrams of each other. There’s two different functions we can use to do this:

• Sort the characters of the words alphabetically. Since anagrams are all made up of the same letters. This will give us the same string for any pair of words that are anagrams of each.
• Produce a dictionary of the number of times each letter occurs in each word. This solution is a bit trickier since you will need to somehow use the dictionary as a key in a hash table. Some languages have a way to do this, while others don’t.

Now that we know how we can group words that are anagrams of each other together, we can put everything together to produce the solution!

Now let’s try one more problem.

Problem #3: K-sorted

Given an array of objects that is partially sorted, sort the array. Every element in the array is at most distance k away from its actual spot. You aren’t given the target runtime for this problem.

As usual, here’s the list of algorithms and data structures: 

• Hash Tables
• Linked Lists
• Binary Trees
• Depth-first search
• Binary Search
• Sorting
• Dynamic Programming
• Recursion

Solution

Let’s first see if we can deduce anything about the runtime. The fastest runtime we could possibly achieve is O(n) since that’s how long it would take to iterate through the list. We could also always perform a normal sort on the list which gives us a runtime of O(n log n). Let’s see if it’s possible to do better than O(n log n).

Is it possible to get as fast as O(n)? Well, if k=n, this problem becomes the same as sorting the list, so it’s not possible to hit O(n) all the time. Maybe it’s still possible to achieve something better than O(n log n). Let’s now see which data structures and algorithms are relevant:

• Hash Tables
• Linked Lists
• Binary Trees
• Depth-first search – No graph.
• Binary Search – No sorted array.
• Sorting – Too slow.
• Dynamic Programming – Not relevant.
• Recursion – Not relevant.

Of the data structures left, the only data structure that is relevant to the problem is a binary tree. Binary trees are the only data structure in the list that deals with sorting elements. If you think a little about how a binary tree can be used to solve the problem, the answer becomes clear. We can keep a binary tree of the last k elements. We repeatedly remove the smallest element from the binary tree and add the next element from the input array. The full algorithm looks like this:

• Insert the first k elements of the input array into the binary tree.
• Iterate through the rest of the input array. On each iteration remove the smallest element from the binary tree and add it to the result array. Then add the current element in the input list to the binary tree.
• Once we get to the end of the input array, repeatedly remove the smallest element from the binary tree until the tree is empty.

Analyzing the runtime of this solution, this gives us a runtime of O(n log k). Is it possible to do better than that? It seems intuitive that there won’t be a faster algorithm. What possible algorithm could have a runtime between O(n) and O(n log k), especially one that you would have to come up with in an interview? Here’s an informal proof that you can’t solve the problem faster than O(n log k). Given that it’s non-trivial to come up with, you wouldn’t be expected to come up with it in an interview. If you aren’t interested in the proof, you can skip it.

Let’s assume you have an algorithm that is faster than O(n log k). We can use this algorithm to come up with a sorting algorithm faster than O(n log n) which is impossible. Let’s say we have n/k separate lists, each of size k, with the elements of each list strictly greater than the elements of the previous. If you concatenate all the lists together, run k-sorted on them, and then split up every k elements into separate lists, you would have sorted n/k lists in less than O(n log k) time. This means on average, you sorted each list in less than O(n/(n/k) log k) = O(k log k) time which is impossible. Therefore no algorithm for k-sorting is faster than O(n log k).

That means we have found the optimal solution to the problem.

Hopefully by this point I’ve convinced you that the algorithm is an effective way for solving algorithm problems. Note that not only is it effective at solving problems in interviews, but if you’ve encountered an algorithm problem in the real world, you can use it to check if the problem has a solution composed of the basic data structures in our list.

If you want to learn about other ways to solve problems, I highly recommend the book How to Solve It. The book covers tons of different approaches you can use to solve any problem. How to Solve It has been a huge influence on how I approach any kind of problem today.