Essential Data Structures and Algorithms for Coding Interviews
Top 10 must-know topics to be successful in technical interviews
There’s a misconception that grinding through hundreds or even thousands of coding interview questions is the only way to be successful. This may work for some people, but it can be a huge time sink and misses a key point: you rarely think about why you are learning something and don’t focus on gaining intuition that can be applied to a broad range of questions.
While there are an infinite number of questions you can be asked, there are only a limited number of concepts that are actually tested on. Instead of trying to memorize solutions, if you focus on thoroughly understanding the key fundamentals and seeing how they are applied, you set yourself up to be successful in answering any question.
The actual problems you will be given are all just variations on a set of core concepts.
In my last article, I provided the roadmap to effectively prepare for coding interviews. This article introduces the 10 most important topics in coding interviews (with 2 bonuses at the end).
👇 If you’re ready to ace your coding interviews, I also built this course 👇
In the Skilled.dev course, you will learn all the essential data structures and algorithms, and conceptually how to apply them to be able to answer any coding interview question.
1. Hash Tables
Hash tables are essential in coding interviews, and I can guarantee you will use them many times during the job hunt. We frequently see hash tables for two reasons:
- Hash tables are often the best tool to optimize a solution
- Hash tables enable us to write very readable code
Hash tables are a flexible data structure that allow us to store items using key-value pairs which are very fast at O(1) time and also make our code more intuitive. If you ever need to optimize a solution, always consider if a hash table could be used.
Hash tables can be combined with any other data structure, from arrays to graphs, and can seamlessly integrate and improve code. We also see hash tables used in more advanced topics like dynamic programming. The downside is that hash tables aren’t (typically) ordered which is why they are often combined with other data structures.
2. Arrays
Arrays show up all the time in interviews and on the job. The only reason I include them one spot behind hash tables is that I think most developers have slightly more intuition about them from more exposure. However, they are equally as important in coding interviews.
Arrays are linear and indexed. We get fast operations at the indexes and when we add/remove items from the end.
Very often if you’re given a list of data as the question input, it’s going to be in an array. You need to feel completely comfortable iterating through an array (from both the front and back), accessing the items by index, sorting it, searching it, updating it — really performing any operation on an array.
We also frequently see questions with nested arrays that create a matrix. You should feel comfortable iterating and using these two-dimensional data structures as well.
3. Recursion
Companies love to test on recursion in programming interviews. In fact, I would almost guarantee that a company will have at least one problem on recursion if you go through their entire round of interviews.
Companies can introduce recursion without it being specifically a “recursion problem”. For example, depth-first search in graph or tree traversal has an elegant recursive solution, and it can appear in advanced concepts like dynamic programming. Other common uses for recursion are binary search, traversing a linked list, or iterating through a stack data structure.
Every recursive function needs a base case and recursive case — this is the foundation of recursion. Then you need to start thinking about how the overall problem can be viewed as subproblems where the recursive function just takes a smaller input value each time until it reaches the base case. One thing to always keep in mind is that recursion adds O(n) space from the call stack (if you don’t have tail-call optimization), and can cause a stack overflow.
4. Sorting
Needing to sort data shows up in our interviews all the time. However, I want to note that you likely don’t need to implement sorting algorithms from scratch, and you definitely shouldn’t spend time or brainpower memorizing sorting algorithms.
The most important thing for sorting is to know how to use a built-in sort function from your programming language, and to know the implications of sorting on your code.
Always assume sorting takes O(n log n) time.
You should be able to sort an array containing any type of data (numbers, strings, etc.), including arrays of objects that have nested attributes.
5. Trees
Understanding how we construct trees using nodes and being able to traverse them is essential. This can appear by directly asking a tree question, or if you’re a frontend engineer, you may be asked to iterate through the DOM which follows the exact same principles. Trees are often a developer’s first introduction to non-linear data structures which bridges us to concepts like graphs.
You should know the difference between pre-order, post-order, and in-order traversal. The implementation differences are minor, but it can completely change how you solve the question.
The most common representation of trees are binary trees which contain at-most 2 nodes for each parent. You also frequently see binary search trees which are just sorted binary trees.
6. Graphs (and Graph Traversal)
Graphs actually tend to show up more than trees in interviews, but it’s easier to understand graphs by first learning how trees work.
Many developers find graphs intimidating when they first learn about them, but once you understand the fundamentals, they can become some of the easier questions.
Graph questions appear much more frequently than you may think. For example, you may be given a matrix as an input but the way you traverse it is by treating it as a graph. A common example of this is the Count Islands interview question each item in the matrix is either land or water. Then when you find a land piece, you traverse it find all the connected land items that are included in this island. You can’t traverse easily linearly, so instead you treat it as a graph traversal where each node’s neighbors are the item up, down, left, and right node from any given item.
You should know how to implement depth-first search (which uses a stack data structure) and breadth-first search (which uses a queue data structure) and feel comfortable traversing through a graph.
7. Binary Search and O(log n) Time
Companies like to introduce binary search indirectly. You are usually given some input and are told (or need to recognize) that it’s sorted. By understanding it’s sorted, you can then implement a version of binary search based on the context of the problem to find items in O(log n) time.
Binary search requires sorted data. Since the data is ordered, when you search through it, you know which direction the item you’re looking for must be in. For example with a standard array of sorted integers, if you pick the middle item and compare its value to the target you’re looking for, you know it’s either to the left or right of this middle item and can move in that direction. This eliminates half of the items.
- Binary search requires sorted data
- Binary search operates in O(log n) time because it eliminates half of the remaining items each step
- You should understand how to implement binary search from scratch
- Binary search is a fundamental concept to binary search trees
- Recognize that when input is sorted (whether stated directly or implied indirectly), this could be an opportunity to use binary search
8. Linked List Techniques
Linked lists are a lower-level data structure, so most of us don’t use them in our every-day work. In fact, needing to understand them is often a joke in that during interviews is the only time in a programmer’s life that they need to know how to reverse a linked list.
Regardless of your opinion on them, you should understand how they work for interviews, and the foundation of linked lists are rooted in computer science fundamentals which is beneficial to anyone in our field.
Luckily the essential concepts for linked lists can be distilled to a few points.
- Know how to iterate through a linked list by being given a head node
- Delete or insert an item from a linked list
- Manage multiple pointers (more on this in the next section)
- Implement the runner technique
- Common questions: reverse a linked list, delete an item from the tail, find an item, determine if there are duplicates, determine if there is a cycle, merge multiple linked lists
9. Manage Pointers
Pointers are how we reference a specific location in our input data structure. This can be when we have an array or string and want to maintain a variable that points to specific indexes, or it can be used to reference nodes in a linked list, tree, or graph.
It’s worth mentioning that pointers can have a deeper technical definition about how we reference data in memory, and then a higher-level way that it’s used where we “point” to an item from the input. Typically you only need to understand the concept through the higher-level definition, especially with dynamic programming languages like JavaScript or Python.
Most often, the challenge with pointers is just transforming logic to code and ensuring you maintain the references to the correct items the whole. A common example of this is finding the longest palindrome substring. You iterate through the array and at each point iterate outward from the center using two pointers to check for possible palindrome lengths. Then once the palindrome ends, you must return to the center pointer and move forward through the string again to the next item.
10. Stacks and Queues
We use stacks and queues when we care about fast operations at the end. This can be when we care about the most-recently added item (the LIFO nature of stacks), or if we want to handle items based on the order in which they arrive (the FIFO nature of queues).
We see stacks and queues frequently with other data structures and algorithms. For example, we use stacks with depth-first search, we use queues with breadth-first search, and the call stack with recursion is a critical concept. We use queues for implementing things like an LRU Cache (a common interview question) and stacks for maintaining the minimum or maximum of a set of data.
Bonus 1: Object-Oriented Programming OR Functional Programming
While this isn’t specifically a data structure or algorithm, there is often at least one interview where you are asked to build something from scratch using either object-oriented programming (OOP) or functional programming (FP). In the past, it was almost always OOP, but with the growth of FP, that is an option as well.
Likely it’s up to which you choose between OOP and FP, but the goal is to see if you can write good code to build something “real”. The company is trying to see if you can effectively encapsulate your logic/functionality and maintain the data in an intuitive manner.
The question they want to answer: Will you be able to write good code that maintains or improve the quality of their codebase?
Bonus 2: Practical Applications and System Design
The system design interview has evolved as the industry has changed, with microservices becoming heavily utilized and frontends growing in complexity. The exact question you’ll be asked will depend on the role you’re applying for, but I’ll outline the core concepts below and break them into the backend and frontend.
Backend: You will be asked to build a complex backend system that will likely consist of some type of data storage and exposing APIs. Companies want to see if you can understand how to logically encapsulate services and have sound reasoning for architecture decisions that will allow the system to be scalable and maintainable.
Frontend: Companies want to see if you can manage a modern frontend. This can either be tested conceptually by discussing your decisions, or they will ask you to build a small application. The concepts typically tested on the frontend are: API integration, building a complex user interface, handling state, or considering performance.
The best way to study for system design questions is to build real things. Spend your time working on projects and trying out different technologies to see how they work. Once you have done this, look at sample system design interview questions so you’ll have a much more practical connection to the problem and see how others solve them.
Conclusion
In my next article, I will take this one step further and show you how to study the right concepts to gain broad intuition.
The most important factor in being successful in coding interviews is using your time effectively. I strongly encourage you to focus on learning concepts and building intuition as you work on programming questions, and this will allow you to broadly apply the concepts to many additional problems and increase your probability of success.
— Trey (@treyhuffine)
P.S. Reminder that the Skilled.dev coding interview course is set to launch on Nov 17! The biggest discount will only be available for a limited time, so be sure to sign up for the email list for notifications.
Level Up Coding
Thanks for being a part of our community! Level Up is transforming tech recruiting. Find your perfect job at the best companies, not just your next job.
