Introduction
It's recruiting season. Be it that you are an experienced professional looking to make it big in top tech companies or students who are starting their career. Chances are you have to brush up your data structures and algorithms(DSA) knowledge in order to nail the technical interviews.
You may be tempted to enroll in an expensive online course or buy a thick book on data structures and algorithms but hear me out.
If you are someone who had in the past, taken a DSA course, chances are you already know or have some faint idea about the subject. Instead of re-learning everything from scratch, I would advise you to solve problems on Leetcode that are based on these data structures in order to refresh your memory. This has two benefits
- You will get a chance to refresh your knowledge
- You will get a feel for how to solve Leetcode problems
In this post, I will provide links to such problems that should give you a good start. If you are starting from 0, I would suggest reading my Leetcode survival guide. It contains resources to learn the main DSA topics and problem lists(like this one) to effectively prepare for your interviews.
In no way these problems are enough to clear your technical interviews but they form a good spring board to ease into problem solving. Each section contains short notes on what you should focus on that particular data structure. Don't expect to be able to solve all the problems on your own. Though the problems are marked as easy, it can be daunting for first-timers. If you are spending more than 30 minutes trying to come up with your solution, please look at the discuss section or watch a video. Understand the solution well and code it up. Ensure that you digest the "pattern" or the trick that is used to solve the problem.
Table of content
Array
Arrays though basic are very versatile data structures. Arrays are the fastest way to access elements. You should be comfortable searching and manipulating values in arrays. A frequent mistake is off by one errors when indexing arrays.
Longest Continuous Increasing Subsequence
Find Winner on a Tic Tac Toe game
There are many data structures such as heap, segment trees and disjoint set union whose underlying implementation uses arrays. Knowing different applications, advantages, disadvantages of arrays will elevate your knowledge. A common optimization in algorithms is to substitute Hash Maps with fixed length arrays and using the index of arrays as the key.
String
Strings in it's most base form is just an array of characters. Usually problems involving strings would be limited to lower-case or upper-case characters. It is always a good idea to clarify with your interviewer what type of characters are present in the input string. You should be familiar with common string operations in your language such as concatenation, checking the character at a particular index and replacing a character at a particular index. Java programmers should know how to use StringBuilder class.
Linked List
Interview problems on Linked Lists mainly tests you ability to detect edge cases. In introductory DSA courses, this is where you first get introduced to pointers. The problems are tricky because you can move in one direction. Don't be surprised to get null pointer exceptions when solving Linked List problems.
Be familiar with how to traverse linked lists, add and remove elements. If your programming language of choice provides a linked list implementation, know the function calls that are supported.
A popular form of the Linked List is the Doubly Linked List. A traditional Linked List only has a "next" pointer which points to the next element in the list. A doubly linked list has two pointers, "next" which points to the next element and "prev" which points to the previous element in the list.
Once you solve problems from Linked List and Hash Maps, I encourage you to solve this popular interview problem LRU cache. This is the toughest problem in the list but it illustrates how you can combine known data structures to solve existing problems.
Though it's slow to access elements in Linked Lists(you should understand why) compared to arrays, adding elements to the end of the Linked List and removing elements from Linked Lists are faster compared to arrays(again you should understand why). Linked Lists can dynamically grow which is helpful when you don't know the size of your lists. Linked Lists can act as helper data structures to implement other data structures such as queues and graphs.
Stack
Stacks though simple are amazing data structures. This section contains problems which will expose you to different ways stacks are used. Many problems, especially string problems can be converted into a stack problem. To solve such problems you need to mainly understand the common stack operations such as push, pop, peek and check for empty stack.
If there is an in-built stack class in your language, make sure you are familiar with the common functions. If not, ensure you can easily implement the stack.
Keep in mind to always check for empty stack when popping from the stack.
Remove All Adjacent Duplicates in a string
Evaluate reverse polish notation
Queue
Queues are a first in first out data structure. Though problems are limited, queues provide a very specific function and that is to track what came first. Many of the points regarding stack applies to queues. Be familiar with the common operations and if there is any in-built support for a queue in your programming language know the functions well.
Hash Map
Hash Maps are versatile data structures providing constant time searches, inserts, deletes and look ups. A popular interview question asks you to implement your own hash maps and I would recommend checking out the following videos from MIT open course-ware to understand how Hash Maps are implemented.
Pro tip: Watch at 1.25x speed
A variation of the Hash Map is the Hash Set. It's important to know the difference between the two and when to use the Hash Map over the Hash Set.
First Unique Character in a String
Heap/Priority Queues
A heap is a data structure that is capable of giving you the minimum value among a list of items in constant time. Yes, constant time. It supports adding elements in log time and it can only remove the top element. It also does not support searching. A famous problem that is solved by heaps is the heavy hitters problem(Top K Frequent Words). It's not a very versatile data structure though a lot of problems can be solved using heaps.
A follow-up to heap problems would be to remove the heap and use an optimized data structure or algorithms. Still using heaps would be a good first approach.
A surprising property of heaps is that adding n elements to a heap is linear time and not nlogn time as you might expect. Here's a link to a lecture that proves it.
It's important to be familiar with how to use the in-built heap data structure in your programming language. I suggest you solve the problems below with the in-built data structure instead of implementing your own heap.
Tree
Tree problems are the first time you would be exposed to recursive problems(if you don't solve Linked List problems recursively). They are good interview problems. Solutions involving trees require you to understand pointers/references in your programming language. Don't worry if you are having a tough time with the easy problems, it's normal. Go slow but make sure to understand the solution and be fluent in coding up the different tree traversal techniques. A good way to understand is to trace out the recursive solution.
By the end, you should be comfortable with recursion or at least not feel intimidated when you have to solve a problem recursively.
Inorder traversal of Binary Tree
Postorder traversal of Binary Tree
Preorder traversal of Binary Tree
Binary tree level order traversal
Lowest Common Ancestor of a Binary Tree
Most problems for trees can be solved with one of the traversal techniques so it's extremely important to know them. Be wary of null pointer exceptions.
Binary Search Tree
Binary Search Tree(BST) is a special form of trees where if you perform an inorder traversal of the tree you would get the elements of the tree in sorted order. This is achieved by ensuring all the elements to the left of the current node is less than the current node and all the elements to the right of the current node is greater than the current node.
Fluency in pointer/reference traversal along with recursion is required.
Convert Sorted Array to Binary Search
BSTs support log(n) operation in best case and in certain cases it will give linear time operations(you should know those cases). Hence, there are advanced data structures such as red black trees that impose additional constraints to ensure all operations on BSTs are log(n). You are not required to know the implementation of red-black trees but you should be familiar with any in-built data structure that uses red-black trees(such as Java's TreeMap/TreeSet)
Graph
In my experience graphs are the most frequently asked topics in companies. These problems requires applications of different data structures such as Hash Maps, Lists, and Set. At this point you should be fluent in recursion.
You should be familiar with the different graph representations, their advantages and disadvantages. You should know the different traversals for graphs(Breadth first search and Depth First search) and their use-cases
Some problems will require you to identify that it's a graph problem and straight up apply a graph traversal algorithm whereas others require you to construct a graph before traversing it.
Find all possible recipes from given supplies
For interview prep, a lot of your focus should be identifying and mastering graph problems. Being able to solve graph problems will act as a spring board for being able to solve dynamic programming problems.
Top comments (3)
I love this list. I am thinking about brushing up on some of the algorithm course work for my masters and I would love to work through a few of these for Hacktoberfest
Hey, I am glad you liked the list. I hope it is a learning experience for you. Also consider sharing this with others who you might think will benefit.
In 2023, with ChatGPT you can level up your Leetcode game and problem solving skills with this open source tool: leetchatgpt.com/
youtube.com/watch?v=yQ7m25nEJTA