The 14 Patterns You Should Know to Ace Coding Interview Questions

The 14 Patterns You Should Know to Ace Coding Interview Questions

Preparing for a coding interview is anxiety-inducing for many software engineers and developers. There is often a lot of material to cover, but you do not have to spend weeks combing through hundreds of interview questions or studying how to code. Instead of spending time solving different coding problems or job interview questions, you should learn the underlying patterns behind each question.

These are the top 14 patterns you can use to solve nearly every coding interview question. Check out this cheat sheet to know how to identify each pattern and some typical coding interview questions.

1. Sliding Window

The sliding window pattern is used to perform a required operation on a specific window size of a given array or linked list, such as finding the longest subarray containing all 1s. Sliding windows start from the first element and keep shifting right by one element. Adjust the length of the window to meet the criteria in your coding interview. The window size can grow, shrink or stay constant.

How to identify the sliding window problem

You might be asked to find the longest or shortest substring, subarray or a certain value. Additionally, if the problem input is a linear data structure such as a linked list, array or string, chances are it is a sliding window problem.

Some common problems with the sliding window problem:

  1. Maximum sum subarray of size “K”
  2. Longest substring with “K” distinct characters
  3. String anagrams

2. Two pointers or iterators

The two-pointers pattern includes two pointers which iterate through the data structure in tandem until one or both of the pointers hit a certain condition. Two pointers is often useful when searching pairs in a sorted array or linked list, like when you have to compare each element of an array to its other elements.

With one pointer, you would have to continually loop back through the array to find the answer. The back and forth with a single iterator is inefficient for time and space complexity—a concept referred to as asymptotic analysis. While the brute force or naive solution with one pointer would work, it will produce something like O(n²). In many cases, two pointers can help you solve the problem with better space or run-time complexity.

How to identify the two-pointer method

A two-pointer problem will feature sorted arrays or linked lists. You will typically need to find a set of elements that fulfill certain constraints. The set of elements in the array may also be a pair, triplet or even a subarray.

Some common problems with the two-pointer method:

  1. Squaring a sorted array
  2. Triplets that sum to zero
  3. Comparing strings that contain backspaces

3. Fast and slow pointers

The fast and slow pointers approach is also known as the hare and tortoise algorithm. It is a pointer algorithm that uses two pointers which move through the array or sequence or linked list at different speeds.

The fast and slow pointers approach is quite useful when dealing with cyclic linked lists or arrays.

By moving at different speeds (for example, in a cyclic linked list), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both of the pointers are in a cyclic loop.

Fast and slow pointers can be used if you’re trying to determine if a linked list is a palindrome. You could also use this pattern instead of the two-pointer method if you have a single-linked list where you can’t move backwards.

How to identify the fast and slow pointers problem

Fast and slow problems will typically deal with a loop in a linked list or array. You can also use the pattern when you need to know the position of a certain element or the overall length of the linked list.

Some common problems with the fast and slow pointers pattern:

  1. Linked list cycle
  2. Palindrome linked list
  3. Cycle in a circular array

4. Merge intervals

The merge intervals pattern is an efficient technique to work through overlapping intervals. In many problems involving intervals, you either need to find overlapping intervals or merge intervals if they overlap.

The merge-interval pattern works like this: Given two intervals “a” and “b,” there will be six different ways the two intervals can relate to each other:

How to identify the merge-intervals pattern

You have a merge-intervals pattern if you’re asked to produce a list with only mutually exclusive intervals or you hear the term “overlapping intervals.”

Some common problems with the merge-intervals pattern:

  1. Intervals intersection
  2. Maximum CPU load

5. Cyclic sort

The cyclic-sort pattern is used with arrays containing numbers in a given range. It iterates over the array one number at a time. If the current number you are iterating is not at the correct index, you swap it with the number at its correct index.

You could try placing the number in its correct index, but this will produce a complexity of O(n²), which is not optimal. Enter: The cyclic-sort pattern.

How to identify the cyclic-sort pattern

You can use the cyclic-sort pattern on problems involving a sorted array with numbers in a given range or if the problem asks you to find the missing, duplicate or smallest number in a sorted or rotated array.

Some common problems with a cyclic-sort pattern:

  1. Find the missing number
  2. Find the smallest missing positive number

6. In-place reversal of linked list

You might be asked to reverse the links between a set of nodes of a linked list. Often, the constraint is that you need to do this in-place, using the existing node objects and without using extra memory. In-place reversal of a linked list is useful in these situations.

The in-place reveral of linked list pattern reverses one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) pointing to the previous node that you processed. In a lock-step manner, you will reverse the current node by pointing it to the previous before moving on to the next node. Also, you will update the “previous” variable to consistently point to the previous node that you have processed.

How to identify the in-place reversal of linked list pattern

You will be asked to reverse a linked list without using extra memory.

Some common problems featuring the in-place reversal of linked list pattern:

  1. Reverse a sublist
  2. Reverse every K-element sublist

7. Tree breadth-first search

The tree breadth-first search pattern uses a queue to keep track of all the nodes of a level before jumping onto the next level. Any problem involving the traversal of a tree level by level can be efficiently solved using this approach.

The tree breadth-first search pattern works by pushing the root node to the queue and then continually iterating until the queue is empty. For each iteration, we remove the node at the head of the queue and “visit” that node. After removing each node from the queue, we also insert all of its children into the queue.

How to identify the tree breadth-first pattern

If you’re asked to traverse a tree in a level-by-level fashion or level-order traversal, you can use the tree breadth-first pattern.

Some common problems featuring the tree breadth-first pattern:

  1. Binary tree level order traversal
  2. Zig-zag traversal

8. Tree depth-first search

The tree depth-first search technique helps you traverse a tree. You can use recursion or a stack for the iterative approach to keep track of all the previous (parent) nodes while traversing.

The tree depth-first search pattern works by starting at the root of the tree. If the node is not a leaf, you need to do the following:

  1. Decide whether to process the current node now (pre-order), between processing two children (in-order) or after processing both children (post-order).
  2. Make two recursive calls for both the children of the current node to process them.

How to identify the tree depth-first pattern

If you’re asked to traverse a tree with in-order, preorder, or postorder depth-first search or the problem requires searching for something where the node is closer to a leaf, you can use the tree depth-first pattern.

Some common problems featuring the tree depth-first search pattern:

  1. Sum of path numbers
  2. All paths for a sum

9. Two heaps

The two-heaps pattern is an efficient approach when you need to know the smallest element in one part and the biggest element in the other part. The pattern might be common, as in many problems, you are given a set of elements, which can be divisible into two parts.

You use a min heap to find the smallest element and a max heap to find the biggest element. The pattern stores the first half of the numbers in a max heap because you want to find the largest number in the first group. You then store the second half of numbers in a min heap, as you want to find the smallest number in the second half. You can calculate the median of the current list of numbers from the top element of the two heaps.

How to identify the two heaps pattern

The two heaps pattern is useful in priority queue and scheduling situations. If you need to find the smallest, largest or median elements of a set or solve a problem with a binary tree data structure, you can use the two heaps pattern.

Some common problems featuring the two heaps pattern:

  • Find the median of a number stream

10. Subsets

Many coding interview problems involve permutations and combinations of a given set of elements. Subsets are an efficient breadth-first search approach to these problems.

How to identify the subsets pattern

You can use the subsets pattern when you need to find the combinations or permutations of a given set.

Some common problems featuring the subsets pattern:

  1. Subsets with duplicates
  2. String permutations by changing case

11. Modified binary search

Whenever you are asked to find a certain element in a sorted array, linked list or matrix, the best algorithm you can use is binary search. Modified binary search is a more efficient way to handle these problems.

How to identify the modified binary search pattern

You can use the modified binary search pattern to solve order-agnostic binary search or search in a sorted infinite array problems.

12. Top “K” elements

You can use the top “K” elements pattern to solve any problem where you need to find the top, smallest or frequent “K” elements among any given set.

The best data structure to keep track of “K” elements is heap, which can help you solve multiple “K” elements problems from a set of given elements. You don’t need a sorting algorithm because the heap will keep track of the elements.

How to identify the top “K” elements pattern

If you’re asked to find the top, smallest or frequent “K” elements of a given set or sort an array to find an exact element, you can use the top “K” elements pattern.

Some common problems featuring the top “K” elements pattern:

  • Top “K” numbers
  • Top “K” frequent numbers

13. K-way merge

The K-way merge pattern helps you solve problems that involve a set of sorted arrays. Whenever you have “K”-sorted arrays, you can use a heap to efficiently perform a sorted traversal of all the elements in every array. You can push the smallest element of each array in a min heap to get the overall minimum. After you have the overall minimum, push the next element from the same array to the heap. Then, repeat this process to make a sorted traversal of all elements.

How to identify the K-way merge pattern

The K-way merge pattern can be used in problems featuring sorted arrays, lists or a matrix. You can also use the pattern if you need to merge sorted lists or find the smallest element in a sorted list.

Some common problems featuring the K-way merge pattern:

  1. Merge K-sorted lists
  2. “K” pairs with largest sums

14. Topological sort

The topological sort pattern is used to find a linear ordering of elements that have dependencies on each other. For example, if event “B” is dependent on event “A,” then “A” comes before “B” in a topological order. The pattern is an easy way to understand how to perform topological sorting of elements sets.

How to identify the topological sort pattern

If you’re asked to update all objects in a sorted order or have a class of objects in a particular order, you can use the topological sort pattern. The problem might also deal with graphs that have no directed cycles in some problems.

Some common problems featuring the topological sort pattern:

  1. Task scheduling
  2. Minimum height of a tree

This article was written by Fahim ul Haq for HackerNoon and was lightly edited and published with permission.