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. I didn’t realize that while doing my preparation, I was following a systematic approach. I would go through 12–15 questions, practicing for two hours every day. This meant that I could solve 350+ problems 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 full-time 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 mapping 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:

1. If the given input is sorted (array, list, or matrix), we will use a variation of Binary Search or a Two Pointers strategy.
2. If we’re dealing with top/maximum/minimum/closest k elements among n elements, we will use a Heap.
3. 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. Furthermore, 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:

1. 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.

2. 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 the 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:

1. 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.
2. 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

Problem Statement: 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

We can use the Breadth-First Search (BFS) approach to generate all subsets of the given set. 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]

1. Start with an empty set: [[]]
2. Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
3. Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
4. 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:

1. Start DFS with the root of the tree.
2. 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.
3. 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.
4. 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. Please take a look at Grokking the Coding Interview to find more of such patterns and their sample problems.

Please take a look at Grokking the System Design Interview and Grokking the Advanced System Design Interview for some good examples of system design question and their answers.

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

Thanks for reading

• 👏 Please clap for the story and follow me 👉
• 📰 View more content on Coding and System Design Interviews
• 🔔 Follow me: LinkedIn | Twitter | Newsletter