When preparing for coding interviews, the number one risk is getting lost with the enormous amount of information available online. We are all-too-familiar with wasting hours jumping from YouTube video to “top x tips to nail your coding interview” blog post, back to another video. It is essential to choose a plan and stick to it. In this post, I use my 5-year experience running this website, to curate a guide to excelling on your next coding interview.
This guide targets big-tech interviews such as FAANG (acronym for Facebook, Apple, Amazon, Netflix and Google) companies. These companies’ influence is so significant that other companies, such as startups and eCommerce, have adopted similar interview processes. These companies believe that a deep understanding of computer science essentials (algorithms and data structures) is a strong indicator of how well you perform as a software engineer. They further believe that coding exercises can effectively test your willingness to tackle challenging problems and being inquisitive. It contrasts with the interview process prevalent in the 90s and 2000s, which focused more on specific technologies.
This plan includes the following sections:
- Array, Strings and Time Complexity
- Lists, Queues, Stacks
- Binary Trees
- Hashing and Hash Maps
- Search and Sorting
- Dynamic Programming
- Practice! Practice! Practice!
Arrays, Strings and Time Complexity
I recommend you start with arrays and string exercises. Why? Firstly, coding exercises involving arrays and string are still the most common. Secondly, it’s important to start slowly, to avoid getting overwhelmed with new concepts and ideas. With that in mind, I wouldn’t start with graph theory or Dynamic programming to begin with.
It is also advisable to mix solving coding exercises, which should take 70% of your preparation time, with some materials about time complexity and Big O notation.
Lists, Stacks and Queues
Linear data structures such lists, stacks and queues appear quite a bit in coding interviews. In some exercises, the problem statement explicitly mentions these data structures. For other exercises, the problem seems to be unrelated at first; the expectation is to use these structures to solve or optimise the solution.
When asked about the three most important algorithms at Google, Google’s search lead replied “hashing, hashing and hashing”. In interviews specifically, hash maps are commonly used to optimise a solution. Problems with O(N2) or O(N log N) brute force solutions, can be optimised to linear complexity due to hash map linear lookup. A classic example is the “Two Sum” exercise that you solved in the array section.
Binary tree questions are common on big-tech interviews. Don’t believe me? Ask Max Howell, the creator of Homebrew, a popular macOS package manager used by most Google engineers.
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.— Max Howell (@mxcl) June 10, 2015
There is a second reason to pay particular attention to this section. Binary trees are a simpler version of other more complex data structures such as non-binary trees, graphs, tries or heaps. For example, Breadth-First Search (BFS) on binary trees is a simplified version of graphs BFS. Remember, start simple, build up.
Before learning standard binary tree algorithms, I recommend you starting with simple coding exercises to get you going with recursion. Of course, feel free to skip them altogether if you are familiar with Binary Trees and recursion already.
- Count Number of Nodes
- Count Number of Leaf Nodes
- Find Depth of Binary Tree
These exercises are more straightforward than a typical exercise you are likely to find in a big-tech on-site interview. Still, you may find them in the early stages of such companies’ interview process, or if you are planning on applying for smaller companies.
Then, dive into Depth First Tree Traversals. Don’t let the jargon discourage you; these concepts are simple. Here is the Wikipedia definition: “The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.”
DFS contrasts with Breadth-First Search (BFS) where you first visit the root, then its children, then all grandchildren, and so on. Most implementations use a first in first out (FIFO) queue. The queue guarantees that we consume nodes “level-by-level”.
Binary Search Trees (BST) are binary trees with sorted values; specifically, for every node, the left child is smaller, and the right child holds an equal or larger value. BSTs are popular because that allow for speedy lookups. A regular binary tree’s search time complexity is no better than a linked list; you still have to iterate through all nodes until finding the value. On the other hand, Binary Search Trees have a time complexity of O(log N), assuming the tree is balanced.
Graphs algorithms are an essential part of the interview preparation. Luckily, algorithms such as BFS and DFS are generalisations of their binary tree counterparts, so nothing in this section should surprise you.
The tricky thing with graph exercises is that they are rarely phrased as “Given a graph do this or that”. The problems look unrelated at first; look for expressions such as “source to target”, “path”, “itinerary” for signs of a graph application.
Practice! Practice! Practice!
In the last stages of your interview preparation, I recommend you to alternate between:
- Practice interview exercises with pen and paper.
- Practice interview exercises on https://www.pramp.com/
On the first point, I am suggesting you change your exercise practice quite dramatically, from using the IDE to using pen and paper only.
The second point is more important. Pram’s model is simple but very effective; you get paired up with another software developer preparing for an interview, and you take turns interviewing.