Arslan Ahmad

Posted on Aug 13, 2019 • Edited on Mar 9, 2023 • Originally published at Medium

The Ultimate Strategy to Preparing for the Coding Interview

#programming #career #codinginterview #codinginterviewquestions

How to prepare more quickly for coding interviews

Coding interviews are getting harder every day. A few years back, brushing up on key data structures and going through 50–75 practice coding interview questions was more than enough prep for an interview. Today, everyone has access to massive sets of coding problems, and they’ve gotten more difficult as well. The overall interview process has gotten more competitive.
In this post, I’d like to share a strategy I follow to prepare for coding interviews. My software engineering career spans around 15 years, in which I’ve switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I have some experience sitting on the other side of the table too. I’ve taken 200+ coding interviews and 100+ system design interviews.

I consider myself a reasonably smart engineer, but I had my challenges solving coding problems on a whiteboard, especially in an interview setting with someone evaluating me. To tackle this, I’d spend a reasonable time for preparation and practice. One thing I didn’t realize was that while doing my preparation, I was following a systematic approach. I would go through 12–15 questions, practicing two hours every day. This meant that I could solve 350+ questions within one month. Using this routine, I was able to crack my interviews for FAANGs (Facebook, Apple, Amazon, Netflix, Google).

How was I able to practice 12+ coding questions every day with a fulltime job? Well, I wasn’t solving coding problems but practicing to map problems onto problems that I’d already solved. I used to read a problem and spend a few minutes to map it to a similar problem I’d seen before. If I could map it, I’d focus only on the different constraints this problem had compared to the parent problem. If it was a new problem, then I’d try to solve it and also read around to find smart ways other people used to devise its algorithm. Over time, I developed a set of problem-patterns that helped me quickly map a problem to an already-known one. Here are some examples of these patterns:

If the given input is sorted (array, list, or matrix), then we will use a variation of Binary Search or a Two Pointers strategy.
If we’re dealing with top/maximum/minimum/closest k elements among n elements, we will use a Heap.
If we need to try all combinations (or permutations) of the input, we can either use recursive Backtracking or iterative Breadth-First Search.

Following this pattern-based approach helped me save a lot of preparation time. Once you’re familiar with a pattern, you’ll be able to solve dozens of problems with it. In addition, this strategy made me confident to tackle unknown problems, as I’ve been practicing mapping unknown problems to known ones.

In the remaining post, I will share all the patterns I’ve collected and present sample problems for a few. For a detailed discussion of these and related problems with solutions take a look at Grokking the Coding Interview.

Sample Problem for Binary Search

Bitonic array maximum

Problem statement
Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array, arr[i] != arr[i+1].

Example: Input: [1, 3, 8, 12, 4, 2], Output: 12

Solution
A bitonic array is a sorted array; the only difference is that its first part is sorted in ascending order, and the second part is sorted in descending order. We can use a variation of Binary Search to solve this problem. Remember that in Binary Search we have start, end, and middle indices and in each step we reduce our search space by moving start or end. Since no two consecutive numbers are the same (as the array is monotonically increasing or decreasing), whenever we calculate the middle index for Binary Search, we can compare the numbers pointed out by the index middle and middle+1 to find if we are in the ascending or the descending part. So:

If arr[middle] > arr[middle + 1], we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by middle or will be before middle. This means we will do end = middle.
If arr[middle] <= arr[middle + 1], we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after middle. This means we do start = middle + 1.

We can break when start == end. Due to the above two points, both start and end will point at the maximum number of the Bitonic array.

Code
Here is the Java code to solve this problem:

Sample Problem for Two Pointers

Pair with target sum

Problem statement
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Write a function to return the indices of the two numbers (i.e., the pair) such that they add up to the given target.

Example: Input: [1, 2, 3, 4, 6], target = 6, Output: [1, 3] (The numbers at index 1 and 3 add up to 6: 2+4=6)

Solution
Since the given array is sorted, a brute-force solution could be to iterate through the array, taking one number at a time and searching for the second number through Binary Search. The time complexity of this algorithm will be O(N*logN). Can we do better than this?

We can follow the Two Pointers approach. We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we’ve found our pair. Otherwise, we’ll do one of two things:

If the sum of the two numbers pointed by the two pointers is greater than the target sum, we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Here is the visual representation of this algorithm for the example mentioned above:

Code
Here is what our algorithm will look like:

Sample Problem

K closest points to the origin

Given an array of points in a 2D plane, find K closest points to the origin.
Example: Input: points = [[1,2],[1,3]], K = 1, Output: [[1,2]]

Solution
The Euclidean distance of a point P(x,y) from the origin can be calculated through the following formula:

We can use a Max Heap to find K points closest to the origin. We can start by pushing K points in the heap. While iterating through the remaining points, if a point (say P) is closer to the origin than the top point of the max-heap, we will remove that top point from the heap and add P to always keep the closest points in the heap.

Code
Here is what our algorithm will look like:

Sample Problem

Subsets

Problem statement
Given a set with distinct elements, find all of its distinct subsets.

Example: Input: [1, 5, 3] Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Solution
To generate all subsets of the given set, we can use the Breadth-First Search (BFS) approach. We can start with an empty set, iterate through all numbers one-by-one, and add them to existing sets to create new subsets.

Let’s take the aforementioned example to go through each step of our algorithm:

Given set: [1, 5, 3]

Start with an empty set: [[]]
Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

Here is the visual representation of the above steps:

Code
Here is what our algorithm will look like:

Sample Problem

Binary Tree Path Sum

Problem Statement
Given a binary tree and a number S, find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S.

Solution
As we are trying to search for a root-to-leaf path, we can use the Depth First Search (DFS) technique to solve this problem.

To recursively traverse a binary tree in a DFS fashion, we can start from the root and, at every step, make two recursive calls, one for the left and one for the right child.

Here are the steps for our Binary Tree Path Sum problem:

Start DFS with the root of the tree.
If the current node is not a leaf node, do two things: a) Subtract the value of the current node from the given number to get a new sum => S = S - node.value, b) Make two recursive calls for both the children of the current node with the new number calculated in the previous step.
At every step, see if the current node being visited is a leaf node and if its value is equal to the given number S. If both are true, we have found the required root-to-leaf path, therefore return true.
If the current node is a leaf, but its value is not equal to the given number S, return false.

Code
Here is what our algorithm will look like:

Conclusion

Following these patterns helped me tremendously to save time for my coding interview prep. Take a look at Grokking the Coding Interview and Grokking Dynamic Programming Patterns for Coding Interviews to find more of such patterns and their sample problems.

Check Design Gurus for some good courses on Programming Interviews and System Design interviews.

Top comments (5)

richie-edwards • Aug 14 '19

Hi Arslan, what is a good resource for enhancing on the system design side? You mentioned you participated in 100+ system design interviews. How did you prepare for those? Thanks for your insight!