When you’re preparing for a technical interview, it’s good to prepare for solving the data structures problems. Spending hours on LeetCode trying to figure out solutions can feel like you’re trying to reinvent the wheel though. These problems get a lot easier to solve when you start developing an instinct around the patterns you can apply to solve them. Most of the coding problems you’ll come across in a technical interview involve applying on of the 15 coding patterns below. Solving these kinds of questions is really about having a mental model for the different patterns, and recognising which pattern to apply.
In this blog post, I’ll take you through 15 common coding patterns, focusing on the visual representation of what they’re doing. I’ll avoid writing a code implementation till later, because I find it’s much more useful to get a clear mental picture about what’s actually happening, rather than trying to start with the code.
Once we’ve gone through the 15 patterns, I’ll show you my four-step approach to getting from a coding question to an implementation in code.
Categories of Patterns
This article describes 15 patterns that I’ve grouped into five categories, based on the kinds of data structures that they work on.
| Category | Patterns |
| Array Patterns | Prefix Sum Two Pointers Sliding Window (Fixed width and Variable width) Overlapping Intervals |
| Linked List Patterns | In-place Reversal Slow and Fast Pointers |
| Stack and Heap Patterns | Monotonic stack Top K Elements |
| Tree and Graph Patterns | Breadth-first Search (BFS) Depth-first Search (DFS) Binary Tree Traversal Matrix Traversal |
| Algorithm Patterns | Backtracking Dynamic Programming Modified Binary Search |
Array Patterns
Questions about array traversal are very common. They can generally be solved by recognising the solution to the problem needing one of the following four processes: Prefix Sum, Two Pointers, Sliding Winder, and Overlapping Intervals.
Prefix Sum
Imagine travelling somewhere in stages and you want to keep track of the distance between each of the stages. One approach would be to log the distance between each stage. So, for example, the distance from Point A to Point B is 5km, and the distance from Point C to Point D is 7km. This works really well if you only need to know the distance between points, but what if you then need to know the distance from Point A to Point C, and from Point B to Point D. Each time, you’d need to recalculate the whole thing!
A better approach is to somehow encode all this information at the start, so you have easy access to all these answers. To do this, you can do a step at the start where you create a new array where each cell shows the running total. Once you have this array, you can refer to it to get the distance between any point and any other point by taking the value of the destination point and subtracting the value of the starting point. So, index[point c] – index[point a] = distance from Point A to Point C, and, without any further calculations, index[point d] – index[point b] = distance from Point B to Point D.
Using Prefix Sum, you do an upfront first-pass through the array, storing a new array that has the information you need to quickly access all the distances.
Two Pointers
This approach takes two pointers, one starting on the left side of the array and the other starting on the right side of the array, and then working inwards.
Sliding Window
Using this approach, you observe a window of the array. Do this by moving two pointers along the array from left to right, and measuring the value of the cells that are in the window.
There are two variations of this approach. The first is the fixed window size, where you start with a specific window width and move the left and right pointers at the same time. The second approach is a variable window size, where you move the right pointer to the right, but only move the left pointer to the right as needed. The variable window size approach is useful when you need to determine something about contiguous cells.
Overlapping Intervals
Imagine you have a set of employees and they all work at different timeslots. Each timeslot has a start time and an end time. You want to see when they overlap. The overlapping intervals pattern lets you do this.
Stack and Heap Patterns
Monotonic Stack
Imagine you’re walking along a street with high skyscrapers. You look at one tower and you have the perfectly normal thought where you ask yourself “I wonder what the tallest building is after this building on this street”…. As I said, it’s a perfectly normal question that we’ve all asked!
Well, worry no more. The solution is to use a monotonic stack. Here, you make a stack of the highest buildings to the right of the building.
Top K Elements
Imagine you’re at a marathon running race and you’re interested to know the top 3 podium positions based on the chip time. Each runner crosses the start line at different times, so when they reach the finish line they won’t be in order. You’re going to have to find an elegant way to keep track of which three runners as they arrive. The solution is a Top K Elements pattern that uses a Heap, specifically a min-value heap.
Using the min-value heap, you can quickly access the element in that has the minimum value. Whenever a runner crosses the finish line, you compare their time to the minimum value element in the heap (without needing to look at any other element in the heap!) and if the runner’s time is faster then you just replace the min-value element in the heap with their time.
Tree and Graph Patterns
Breadth-First Search (BFS)
Imagine you’re in the middle of a maze and you need to find the shortest path to the exit. To be sure you find the shortest path, you can test every single possible path by gradually increasing the distance one step at a time in all possible directions. If you do this, you’re doing breadth-first search, by moving through a graph one level at a time. This approach guarantees that you’ll find the shortest possible path, but, as you can imagine, it also involves you taking a lot of footsteps to get there!!!
Depth-First Search (DFS)
DFS takes a different approach to BFS. Rather then going through each level of the graph (or the maze) step by step, DFS goes as deep as possible into each path, keeping track of which spaces in the maze have been visited. Starting in the centre of the maze, start walking. Whenever you come to a junction, take the right-most option. Follow this approach until you either find the exit or get stuck. If you get stuck, go back to the last junction and then take the option that’s most on the right that you haven’t taken yet. Continue this approach until you find the exit. When you exit, there is likely to be many parts of the maze that you never explored, so there might have been a shorter path that you missed…. but at least you escaped safe and sound!
This approach will find the exit quicker than Breadth-First Search, but it’s not guaranteed to find the shortest path. So, the tradeoff between BFS and DFS depends on whether you need the shortest possible route with extra work finding it, or you need to quickly find a path through the graph even though it might not be the shortest path.
Binary Tree Traversal
Matrix Traversal
Algorithm
Dynamic Programming
Break the problem down into smaller chunks
Backtracking
Backtracking has a similar flavour to Depth-First Search. It involves going through a set of options and, whenever an option turns out to be wrong, stepping backwards, undoing the decision, and then looking again at the options. The difference between the two is that in backtracking, the options don’t already exist. You construct them as you go along. In DFS, there are a set of nodes, like in a maze, that you can travel through. In backtracking, you’re not given a maze. You construct the tree of possibilities yourself, one decision at a time, and then you prune away the branches that don’t lead anywhere. While DFS is useful for determining whether a goal is reachable in a tree, backtracking is useful when you need to explore the entire decision space, including paths that turn out to be invalid.
Modified Binary Search
Imagine you’re looking through a phone book, where the names are listed in alphabetical order. You go to the middle of the book, see that the name you’re searching for will be before the middle of the book. You then find the middle of the first half of the book (25% into the book…) and continue this process. This is standard binary search, using a ‘divide and conquer’ algorithm. This works really well when we’re dealing items that are perfectly sorted. But what about if it’s not perfectly sorted? For example, if there was a sorted list, but it got rotated and now the sorted list starts somewhere in the second half of the list. Imagine someone’s taken a random pile of pages from the start of the phone book and they’ve stuck it at the end. How can you find your way through the phone book now?
The trick is to think about the search space. Even though a random number of pages were added at the end, and we don’t know how many pages it was (it could be 10% or 70% or anything else!), what we do know for sure is that there’s one half of the book that’s still perfectly sorted. We just don’t know whether it’s the first half of the book or the second half of the book.
To solve this, follow these steps:
1, Find the midpoint of the book, same way as you did in standard binary search.
2, Figure out which half of the book is correctly sorted. You can do this by comparing the start of the array with the midpoint of the array.
3, Check if the target you’re looking for falls inside the sorted half of the book.
4, If it does, then proceed using a divide-and-conquer algorithm on that half. If not, repeat steps 1 to 3 on the other half of the book.
Since you’re dividing the search space in half with each step, you still keep it at O(log n) even though the book isn’t fully sorted anymore.
Four-step Approach to Solve Coding Questions
Rather than dive into the technical implementation in code, I find that it’s much more useful to first build your mental model, so you understand exactly what’s happening. I’m a very visual person when it comes to these kinds of things. My approach is to (1) recognise which pattern can be used to solve the problem, then (2) stepping through a small version of the problem, (3) writing some pseudocode for how it should be implemented, and then (4) code it up in whatever programming language is needed. (I mostly write in Java, and some Python, steps 1-3 are language agnostic, and step 4 can be implemented in most programming languages).
