Test

The process of preparing for coding interviews is anxiety-inducing for many developers. There’s so much material to cover, and often much of it feels irrelevant to what devs are doing in their day jobs, which only adds to the stress.

One of the outcomes of this is that it’s now common for developers to spend weeks combing through hundreds of interview questions on sites like LeetCode. One of the most comm points of anxiety developers that I’ve talked to have before the interview is: Have I solved enough practice questions? Could I have done more?

That’s why I try to focus on helping developers grasp the underlying patternsbehind each question — so they don’t have to worry about solving hundreds of problems and suffer from Leetcode fatigue. If you understand the generic patterns, you can use them as a template to solve a myriad of other problems with slight variations.

Here, I’ve laid out the top 14 patterns that can be used to solve any coding interview question, as well as how to identify each pattern, and some example questions for each. If you’re interested in going into more detail on any of the patterns, check out Grokking the Coding Interview: Patterns for Coding Questions.

The following patterns assume that you’ve brushed up on Data Structures. If not, check out these courses on Data Structures.

Here are the 14 patterns that we will look at today.

1. Sliding Window
2. 2 Pointers or Iterators
3. Fast and Slow Pointers or Iterators
4. Merge Intervals
5. Cyclic sort
6. In-place reversal of linked list
7. Tree BFS
8. Tree DFS
9. Two heaps
10. Subsets
11. Modified binary search
12. Top K elements
13. K-way merge
14. Topological sort

Let’s get started!

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 1st element and keep shifting right by one element and adjust the length of the window according to the problem that you are solving. In some cases, the window size remains constant and in other cases the sizes grows or shrinks.

Following are some ways you can identify that the given problem might require a sliding window:

• The problem input is a linear data structure such as a linked list, array, or string
• You’re asked to find the longest/shortest substring, subarray, or a desired value

Common problems you use the sliding window pattern with:

• Maximum sum subarray of size ‘K’ (easy)
• Longest substring with ‘K’ distinct characters (medium)
• String anagrams (hard)

2. Two Pointers or Iterators

Two Pointers is a pattern where two pointers 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; for example, when you have to compare each element of an array to its other elements.

Two pointers are needed because with just pointer, you would have to continually loop back through the array to find the answer. This 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 1 pointer would work, it will produce something along the lines of O(n²). In many cases, two pointers can help you find a solution with better space or runtime complexity.

Ways to identify when to use the Two Pointer method:

• It will feature problems where you deal with sorted arrays (or Linked Lists) and need to find a set of elements that fulfill certain constraints
• The set of elements in the array is a pair, a triplet, or even a subarray

Here are some problems that feature the Two Pointer pattern:

• Squaring a sorted array (easy)
• Triplets that sum to zero (medium)
• Comparing strings that contain backspaces (medium)

3. Fast and Slow pointers

The Fast and Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/linked list) at different speeds. This approach is quite useful when dealing with cyclic linked lists or arrays.

By moving at different speeds (say, 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 the pointers are in a cyclic loop.

How do you identify when to use the Fast and Slow pattern?

• The problem will deal with a loop in a linked list or array
• When you need to know the position of a certain element or the overall length of the linked list.

When should I use it over the Two Pointer method mentioned above?

• There are some cases where you shouldn’t use the Two Pointer approach such as in a singly linked list where you can’t move in a backwards direction. An example of when to use the Fast and Slow pattern is when you’re trying to determine if a linked list is a palindrome.

Problems featuring the fast and slow pointers pattern:

• Linked List Cycle (easy)
• Palindrome Linked List (medium)
• Cycle in a Circular Array (hard)

4. Merge Intervals

The Merge Intervals pattern is an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, you either need to find overlapping intervals or merge intervals if they overlap. The pattern works like this:

Given two intervals (‘a’ and ‘b’), there will be six different ways the two intervals can relate to each other:

Understanding and recognizing these six cases will help you help you solve a wide range of problems from inserting intervals to optimizing interval merges.

How do you identify when to use the Merge Intervals pattern?

• If you’re asked to produce a list with only mutually exclusive intervals
• If you hear the term “overlapping intervals”.

Merge interval problem patterns:

• Intervals Intersection (medium)
• Maximum CPU Load (hard)

5. Cyclic sort

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. The Cyclic Sort pattern iterates over the array one number at a time, and 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^2) which is not optimal, hence the Cyclic Sort pattern.

How do I identify this pattern?

• They will be problems involving a sorted array with numbers in a given range
• If the problem asks you to find the missing/duplicate/smallest number in an sorted/rotated array

Problems featuring cyclic sort pattern:

• Find the Missing Number (easy)
• Find the Smallest Missing Positive Number (medium)

6. In-place reversal of linked list

In a lot of problems, you may 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, i.e., using the existing node objects and without using extra memory. This is where the above mentioned pattern is useful.

This pattern reverses one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) will point to the previous node that you have 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 variable “previous” to always point to the previous node that you have processed.

How do I identify when to use this pattern:

• If you’re asked to reverse a linked list without using extra memory

Problems featuring in-place reversal of linked list pattern:

• Reverse a Sub-list (medium)
• Reverse every K-element Sub-list (medium)

7. Tree BFS

This pattern is based on the Breadth First Search (BFS) technique to traverse a tree and 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 in a level-by-level order can be efficiently solved using this approach.

The Tree BFS 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 BFS pattern:

• If you’re asked to traverse a tree in a level-by-level fashion (or level order traversal)

Problems featuring Tree BFS pattern:

• Binary Tree Level Order Traversal (easy)
• Zigzag Traversal (medium)

8. Tree DFS

Tree DFS is based on the Depth First Search (DFS) technique to 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 DFS pattern works by starting at the root of the tree, if the node is not a leaf you need to do three things:

1. Decide whether to process the current node now (pre-order), or 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 DFS pattern:

• If you’re asked to traverse a tree with in-order, preorder, or postorder DFS
• If the problem requires searching for something where the node is closer to a leaf

Problems featuring Tree DFS pattern:

• Sum of Path Numbers (medium)
• All Paths for a Sum (medium)

9. Two heaps

In many problems, we are given a set of elements such that we can divide them into two parts. To solve the problem, we are interested in knowing the smallest element in one part and the biggest element in the other part. This pattern is an efficient approach to solve such problems.

This pattern uses two heaps; A Min Heap to find the smallest element and a Max Heap to find the biggest element. The pattern works by storing the first half of numbers in a Max Heap, this is because you want to find the largest number in the first half. You then store the second half of numbers in a Min Heap, as you want to find the smallest number in the second half. At any time, the median of the current list of numbers can be calculated from the top element of the two heaps.

Ways to identify the Two Heaps pattern:

• Useful in situations like Priority Queue, Scheduling
• If the problem states that you need to find the smallest/largest/median elements of a set
• Sometimes, useful in problems featuring a binary tree data structure

Problems featuring

• Find the Median of a Number Stream (medium)

10. Subsets

A huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements. The pattern Subsets describes an efficient Breadth First Search (BFS) approach to handle all these problems.

The pattern looks like this:

Given a set of [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 a visual representation of the Subsets pattern: