An Algorithm for Passing Programming Interviews

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.

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:

(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:

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.

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.

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.

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.

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.

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

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.

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

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.

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:

Let’s start by eliminating the items from the list that can’t possibly be used for this 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:

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:

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!

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:

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:

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:

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.