The Ultimate Strategy to Preparing for the Coding Interview

How to do faster preparation 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 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 like to share a strategy that I’ve been following to prepare for coding interviews. My software engineering career spans around 15 years, in which I have switched jobs five times. I’ve given around 30 interview loops containing 120+ interviews. I’ve 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 have had my challenges solving coding problems on a whiteboard, especially in an interview setting where someone is evaluating me. To tackle this problem, I had been spending 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 was able to go through 12–15 questions practicing two hours every day. This meant that I was able to 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 full-time job? Well, I was not solving coding problems but practicing to ‘map’ problems to already known problems that I’ve solved before. . I used to read a problem, spend a few minutes mapping it to a similar problem that I have seen before. If I can map it, I focus only on the different constraints this problem has compared to the parent problem If it is a new problem, then I try to solve it and also read around to find smart ways other people have used to device its algorithm. Over time, I developed a set of problem-patterns, that helped me quickly ‘map’ a problem to an already known pattern. Here are some examples of these patterns: If the given input is sorted (array, list, or matrix), then we will be using a variation of or a strategy. Binary Search Two Pointers If we are dealing with top/maximum/minimum/closest ‘k’ elements among ’n’ elements, we will be using a . Heap If we need to try all combinations (or permutations) of the input, we can either use recursive or iterative . Backtracking Breadth-First Search Following this pattern-based approach helped me save a lot of preparation time. As once you’re familiar with a pattern, you will be able to solve dozens of problems with it. In addition to that, this strategy made me confident to tackle unknown problems, as I’ve been practicing to map unknown problems to known problems. In the remaining post, I will share all the patterns that I’ve collected over time and present sample problems for a few. For a detailed discussion of these patterns and their related problems with solutions take a look at Grokking the Coding Interview . Sample problem for Binary Search: Bitonic Array Maximum 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 . Problem statement: arr[i] != arr[i+1] : [1, 3, 8, 12, 4, 2], : 12 Example : Input Output 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 to solve this problem. Remember that in we have , , and indices and in each step we reduce our search space by moving or . Since no two consecutive numbers are same (as the array is monotonically increasing or decreasing), whenever we calculate the index for , we can compare the numbers pointed out by the index and to find if we are in the ascending or the descending part. So: Solution: Binary Search Binary Search start end middle start end middle Binary Search middle middle+1 If , we are in the second (descending) part of the bitonic array. Therefore, our required number could either be pointed out by or will be before . This means we will be doing: end = middle. arr[middle] > arr[middle + 1] middle middle If , we are in the first (ascending) part of the bitonic array. Therefore, the required number will be after . This means we will be doing: . arr[middle] arr[mid + ]) { end = mid; } { start = mid + ; } } arr[start]; } { System.out.println(MaxInBitonicArray.findMax( [] { , , , , , })); System.out.println(MaxInBitonicArray.findMax( [] { , , , })); System.out.println(MaxInBitonicArray.findMax( [] { , , , })); System.out.println(MaxInBitonicArray.findMax( [] { , , })); } } class MaxInBitonicArray public static int findMax ( [] arr) int int 0 1 while int 2 if 1 else 1 // at the end of the while loop, 'start == end' return public static void main (String[] args) new int 1 3 8 12 4 2 new int 3 8 3 1 new int 1 3 8 12 new int 10 9 8 Sample Problem for Two Pointers: Pair with Target Sum Given an array of sorted numbers and a target sum, find a . Problem statement: 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. : [1, 2, 3, 4, 6], =6, : [1, 3] (The numbers at index 1 and 3 add up to 6: 2+4=6) Example: Input target Output 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 . The time complexity of this algorithm will be O(N*logN). Can we do better than this? Solution: Binary Search We can follow the 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 have found our pair. Otherwise, we will do one of two things: Two Pointers If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that 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: Here is what our algorithm will look like: Code: { [] search( [] arr, targetSum) { left = , right = arr.length - ; (left arr[right]) left++; right--; } [] { - , - }; } { [] result = PairWithTargetSum.search( [] { , , , , }, ); System.out.println( + result[ ] + + result[ ] + ); result = PairWithTargetSum.search( [] { , , , }, ); System.out.println( + result[ ] + + result[ ] + ); } } class PairWithTargetSum public static int int int int 0 1 while // comparing the sum of two numbers to the 'targetSum' can cause integer overflow // so, we will try to find a target difference instead int if return new int // found the pair if // we need a pair with a bigger sum else // we need a pair with a smaller sum return new int 1 1 public static void main (String[] args) int new int 1 2 3 4 6 6 "Pair with target sum: [" 0 ", " 1 "]" new int 2 5 9 11 11 "Pair with target sum: [" 0 ", " 1 "]" Sample problem: ‘K’ Closest Points to the Origin Given an array of points in a 2D plane, find ‘K’ closest points to the origin. Problem statement: : points = [[1,2],[1,3]], K = 1, : [[1,2]] Example: Input Output The of a point from the origin can be calculated through the following formula: Solution: Euclidean distance P(x,y) We can use a to find ‘K’ points closest to the origin. We can start with pushing first ‘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. Max Heap Here is what our algorithm will look like: Code: java.util.*; { x; y; { .x = x; .y = y; } { (x * x) + (y * y); } } { { PriorityQueue maxHeap = PriorityQueue<>( (p1, p2) -> p2.distFromOrigin() - p1.distFromOrigin()); ( i = ; i (maxHeap); } { Point[] points = Point[] { Point( , ), Point( , ), Point( , - ) }; List result = KClosestPointsToOrigin.findClosestPoints(points, ); System.out.print( ); (Point p : result) System.out.print( + p.x + + p.y + ); } } import class Point int int public Point ( x, y) int int this this public int distFromOrigin () // ignoring sqrt return class KClosestPointsToOrigin List public static findClosestPoints (Point[] points, k) int new // put first 'k' points in the max heap for int 0 // go through the remaining points of the input array, if a point is closer to // the origin than the top point of the max-heap, remove the top point from // heap and add the point from the input array for int if // the heap has 'k' points closest to the origin, return them in a list return new public static void main (String[] args) new new 1 3 new 3 4 new 2 1 2 "Here are the k points closest the origin: " for "[" " , " "] " Sample Problem: Subsets : Given a set with distinct elements, find all of its distinct subsets. Problem Statement : [1, 5, 3], : [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3] Example: Input Output To generate all subsets of the given set, we can use the 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. Solution: Breadth-First Search (BFS) Let’s take the above-mentioned 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: Here is what our algorithm will look like: Code: java.util.*; { List > findSubsets( [] nums) { List > subsets = ArrayList<>(); subsets.add( ArrayList<>()); ( currentNumber : nums) { n = subsets.size(); ( i = ; i set = ArrayList<>(subsets.get(i)); set.add(currentNumber); subsets.add(set); } } subsets; } { List > result = Subsets.findSubsets( [] { , }); System.out.println( + result); result = Subsets.findSubsets( [] { , , }); System.out.println( + result); } } import class Subsets public static int new // start by adding the empty subset new for int // we will take all existing subsets and insert the current number in them to // create new subsets int for int 0 // create a new subset from the existing subset and // insert the current element to it new return public static void main (String[] args) new int 1 3 "Here is the list of subsets: " new int 1 5 3 "Here is the list of subsets: " Sample Problem: Binary Tree Path Sum : 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.’ Problem Statement As we are trying to search for a root-to-leaf path, we can use the technique to solve this problem. Solution: Depth First Search (DFS) 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 => , b) Make two recursive calls for both the children of the current node with the new number calculated in the previous step. S = S - node.value 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 these conditions 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. Here is what our algorithm will look like: Code: { val; TreeNode left; TreeNode right; TreeNode( x) { val = x; } }; { { (root == ) ; (root.val == sum && root.left == && root.right == ) ; hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val); } { TreeNode root = TreeNode( ); root.left = TreeNode( ); root.right = TreeNode( ); root.left.left = TreeNode( ); root.right.left = TreeNode( ); root.right.right = TreeNode( ); System.out.println( + TreePathSum.hasPath(root, )); System.out.println( + TreePathSum.hasPath(root, )); } } class TreeNode int int class TreePathSum public static boolean hasPath (TreeNode root, sum) int if null return false // if current node is a leaf and its value is equal to the sum, we've found a path if null null return true // recursively call to traverse the left and right sub-tree // return true if any of the two recursive call return true return public static void main (String[] args) new 12 new 7 new 1 new 9 new 10 new 5 "Tree has path: " 23 "Tree has path: " 16 Following these patterns helped me tremendously to save time for my coding interview prep. Take a look at and to find more of such patterns and their sample problems. Grokking the Coding Interview Grokking Dynamic Programming Patterns for Coding Interviews This post was originally published on Medium: The Ultimate Strategy to Preparing for the Coding Interview