This is the article I wish I had read when I started coding. Programming is about solving problems and here I will dive deep into 20 problem-solving techniques, with code samples, big O analysis, and challenges so that you can master them. In this article, I outlined a high-level strategy to prepare for your next coding interview as well as the top mistakes to avoid. Here, I will dive deep into 20 problem-solving techniques that you must know to excel at your next interview. They have helped me at work too and even given me ideas for a side project I am working on. Also, the last section includes a step-by-step guide to learn data structures and algorithms, with examples.
I have grouped these techniques in:
I will explain each of them, show how to apply them to coding problems, and leave you some exercises so that you can practice on your own.min
This list is part of the study notes that I took before I applied to Amazon. I hope they will be as useful to you as they have been to me.
For your convenience, I have copied here the problem statements, but I have left links to all of the exercises. You can copy-paste my solution and play around with it. I strongly recommend you code your solution and see if it passes the tests.
Some of the questions are better explained through an image or diagram. For these, I have left a comment asking you to open the link to get a graphical description of the problem.
This technique is very useful on sorted arrays and arrays whose elements we want to group.
The idea is to use two (or more pointers) to split the array into different areas or groups based on some condition:
The following examples will help you understand this principle.
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Notes:
Example:
Since the array a is sorted, we know that:
With this, we can design the following algorithm:
Here is a simple C++ implementation:
The time complexity is O(N), since we may need to traverse the N elements of the array to find the solution.
The space complexity is O(1), since we only need two pointers, regardless of how many elements the array contains.
There are other ways of solving this problem (using a hash table, for example), but I have used it just as an illustration of the two pointer technique.
Here are two variations of this exercise: three sum and four sum. They can be solved similarly by reducing them to this very same problem.
This is a very common technique: transform a problem whose solution you don’t know to a problem that you can solve.
Given a sorted array, nums, remove the duplicates in-place such that each element appears only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Example 2:
It doesn’t matter what values are set beyond the returned length.
The array is sorted and we want to move duplicates to the end of the array, which sounds a lot like grouping based on some condition. How would you solve this problem using two pointers?
The logic is as follows. If the values of the elements at index i (except i = 0) and i-1 are:
This problem has linear time complexity and constant space complexity (it is usually the case for problems solved using this technique).
Given an array with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not supposed to use the library’s sort function for this problem.
Example:
The groups this time are:
What we can achieve with 3 pointers.
This implementation is a bit tricky, so make sure you test it thoroughly.
Since need to traverse the array to sort it, the time complexity is O(N). The space complexity is O(1).
Just as a curiosity, this is an instance of the National Dutch flag problem described by Dijkstra.
Given a Linked List and a number n, write a function that returns the value at the n-th node from the end of the Linked List.
This is one of the most common variations of the two-pointer technique: introducing an offset so that one of the pointers reaches a certain condition, the other one is in the position you are interested in.
In this case, if we move one of the pointers, f, n times and then start advancing both at the same time by one node, when f reaches the end of the list the other pointer, s, will point to the node right before the node we want to delete.
Make sure you define what n = 1 means (last element or the element before the last element?), and avoid off-by-one errors.
The time and space complexity are the same as the previous problems’.
Now, you will have two pointers moving at different speeds: at every iteration, one of the pointers will advance one node and the other will advance two nodes. We can use this variation to:
As usual, it will become clearer once I present some examples.
Given a non-empty, singly linked list with head node head, return a middle node of the list. If there are two middle nodes, return the second middle node.
Example 1:
Solving this problem in 2 passes is easy: on the first pass we compute the size of the list, L, and on the second pass we only advance L/2 nodes to find the element at the middle of the list. This approach has linear complexity in time and constant in space.
How can we use 2 pointers to find the middle element in one single pass?
If one of the pointers, f, moves twice as fast as the other one s, when f reaches the end, s will be in the middle of the list.
Here’s my solution in C++. Make sure you take into account edge cases (empty list, lists of odd and even sizes, etc) when you test your code.
Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where the tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
The simplest solution is to add all the nodes to a hash set. When we traverse the list, if we get to a node that has already been added to the set, there is a cycle. If we get to the end of the list, there are no cycles.
This has a time complexity of O(L), being L the length of the list, and space complexity of O(L), since in the worst case – no cycles – we need to add all the elements of the list to the hash set.
Time complexity cannot be improved. However, space complexity can be reduced to O(1). Think for a minute how this can be achieved with two pointers moving at different speeds.
Let’s call these pointers fast and slow. For each node slow visits, fast will move two nodes forward. Why?
Now, let’s translate this solution into code:
Given an array, nums, containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
This is the same problem/solution as the previous problems, for arrays instead of linked lists.
Here are more problems that can be solved using this technique:
The sliding window technique eases the task of finding optimal chunks of contiguous data that meet a certain condition:
You can think of it as another variation of the two pointer technique, where pointers are updated separately based on a certain condition. Below is the basic recipe for this type of problems, in pseudocode:
Create two pointers, l, and r
Create variable to keep track of the result (res)
Iterate until condition A is satisfied:
Based on condition B:
update l, r or both
Update res
Return resGiven a string, find the length of the longest substring without repeating characters.
Example 1:
Find the length of the longest substring without repeating characters sounds a lot like *finding optimal *chunks of contiguous data* that meet a certain condition.*
Based on the recipe I described above, you will need:
While iterating through the string:
For more practice, you can try the following problems:
There might be simpler solutions but focus on using this technique to get a better grasp of it.
I already published an article on this topic that you can find here.
The idea behind backtracking is to explore all the potential solutions for a problem, in a smart way. It builds candidate solutions incrementally and as soon as it determines that a candidate solution is not viable, it backtracks to a previous state and tries the next candidate.
Backtracking problems present you with a list of choices. Should you:
After you have picked one of the options, it will get you a new list of choices, until you reach a state where there are no more choices: either you arrived at a solution or there is no solution.
Visually, you are moving from the root of a tree with every choice, until you get to a leaf. The basic high-level recipe (in pseudocode) for a backtracking algorithm is the following:
boolean backtracking(Node n){
if(isLeaf(n) {
if(isSolution(candidate)){
sol.add(candidate);
return true;
} else {
return false;
}
}
//Explore all children
for(child in n) {
if(backtracking(child))
return true;
}
return false;
}This can of course change depending on the problem:
But the core idea is the same: examine, in a systematic way, all paths and backtrack as soon as the current path is no longer viable.
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Example:
This is a classic backtracking problem
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent (check the link for diagram). Note that 1 does not map to any letters.
Example:
For every number in the input, you have several letters to choose from. If you can draw a tree (this is what I do) where the branches are born from the different choices you take, chances are that you can apply backtracking.
Note: Before you start solving any problem, try different approaches: dynamic programming, greedy algorithms, divide and conquer, a combination of algorithms and data structures, etc. Coding is the last step.
My solution, in C++:
Since I knew already the size of the solution, I initialize my candidate with that size and just modified the character at position idx. If the size is not known, this can be done instead:
Write a program to solve a Sudoku puzzle by filling the empty cells. Open the link to get a longer description, including an image of the puzzle.
In an interview, unless you have plenty of time, you will not need to implement isViableSolution, just to sketch it. I know a colleague who got this question in an on-site.
Even though the code is long, it is mostly because of isViableSolution. Otherwise, it is not very different from other backtracking problems.
I have created a generic separate section for:
Because conceptually they are similar: take the elements of a container (array, string, etc) and create subsets from them according to some rule(s).
You will notice that most of these are backtracking problems or very similar.
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
For every index i, you need to generate two solutions:
Until you get to the end of the array.
Here’s a simple implementation of what we have discussed.
This is a variant of the previous problem. Try playing around with my code to see if you can change it to meet the new requirement. You have to change less than 5 lines.
Good luck!
Given a collection of distinct integers, return all possible permutations.
Example:
Very similar to the previous problem, but this time we need to consider all the elements of the array in our candidates. The way we move them around is by swapping elements at different positions.
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
We can apply here the same trick as before for combinations. If you could not come up with this “trick”, you can always use a set to store the solutions and then create and return an array from this set.
As you can see, there is no need to learn every single data structure and algorithm in the literature to solve a vast amount of problems. What is valuable, and can be trained, is the ability to systematically think through a problem and skills to turn your ideas into code.
For extra practice:
Sorting is not a problem-solving technique per see but as you have seen in the previous sections we have been able to solve many problems by either sorting the input or assuming it was sorted and then applying one of the other techniques.
When you are facing a new problem, ask yourself:
For instance, our first problem (Two sum) can be solved in linear time with the two-pointer technique because the input is sorted. However, if we have to sort, the complexity becomes O(n log n).
Here you have a couple of problems that can be easily solved after sorting the input.
Other solutions trade space for time, so it is worth considering them before you start writing any code.
Given two strings s and t, write a function to determine if t is an anagram of s.
Example 1:
Example 2:
By definition, two strings are anagrams if they contain the same characters in different order. Therefore, we can simply sort both strings and compare them. The overall time complexity is O(n log n).
Given two arrays, write a function to compute their intersection.
Example 1:
You can solve this problem by sorting both arrays and using a two-pointer based approach. Give it a try before reading my solution.
Imagine we have the following arrays:
And two pointers, l for A and r for B, starting at index 0 in each array.
We need to increment l to see if A has a 2: B can’t contain a 1 to the right of r, because it is sorted.
In short, we compare both elements:
The time complexity of this approach is O(n log n) – even though the two-pointer part is linear – and the space complexity is O(1) – not including the space needed to store the intersection, of course, in which case we could say it is O(min(length(A), length(B)).
Most interval related problems I have seen boil down to:
You can see this as yet another type of problem that can be simplified after sorting the input, which is why I have included it in this section.
I’m leaving here my solution to two exercises, based on what I have just described. Try them before reading my solutions.
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists.
Binary search is a search algorithm that can be applied to sorted data structures (like arrays or binary search trees) with O(log n) time complexity and O(1) space complexity.
What you might not know is its implementation’s most common bug. Assuming we are performing a binary search in the elements whose range goes from [l,r], the element in the middle is usually computed as:
const int m = (l + r) / 2;
Can you spot the problem here?
This line can overflow. The safe way of computing this middle element is:
const int m = l + (r - l) / 2;
Here’s a basic implementation of binary search, using C++ templates. If you understand how it works and how to implement it correctly, you can solve many problems that just have a little tweak in the requirements or that are binary search problems in disguise.
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
We need to find a number in the range [0, x], which is sorted. It sounds a lot like a binary search problem.
It is not critical to know this, but we can optimize a little:
With this, we can search in [2, x/2] and speed things up a bit.
Have fun!
This is one of the techniques you need to know to explore trees and graphs. Since many problems can be modeled as graphs, you must know this technique. To implement it, we just need to use a queue q and add to this same queue the children of the nodes we process from q.
At any given point in the iteration, BFS visits all the nodes at the same distance from the origin. This will become clearer after some of these examples.
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of the shortest transformation sequence from beginWord to endWord, such that:
Note:
Example 1:
I got asked this question during my on-site interview at Amazon. The idea is to model this problem using a graph:
With this setup, this problem is equivalent to finding a path between two nodes in a graph, which BFS can solve. Since all edges have the same weight (1), we do not need Dijkstra or any other fancier algorithm.
After you visit the DFS section:
What would happen if we use DFS instead? Do you see any benefits/drawbacks?
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
Open the link for a graphical description of the problem.
You only need to add here a little tweak to the standard BFS algorithm: you need to know how many elements in the queue you need to process for each level.
This is one approach that can be applied to many other problems.
Let me propose a different kind of challenge: building something, instead of solving abstract problems. I find it more fun and you can add them to your Github profile. Here are just two examples:
Similar to BFS in its purpose: explore trees and graphs. DFS is not guaranteed to find the shortest path between two points, but it will find any existing path.
It is usually shorter to implement than BFS. Some people find it easier. Others, because of the recursive calls, not so much. It is up to you. Just make sure you think about potential stack overflow issues if the size of the stack starts to get big.
Some problems are much easier to be solved with DFS/recursion, that it is worth practicing.
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
I got this problem at my first phone interview at Amazon.
As soon as you see a matrix, think of a graph. This problem (and its variations) is very straightforward:
To sink the island, you need to visit all the surrounding 1s in the matrix, which is equivalent to visit all the neighbors of that node and of all its neighbors, which sounds a lot like a recursive problem.
You can try to solve this using BFS too, but DFS is much shorter.
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
Many tree-related problems have relatively straightforward recursive solutions. This problem could be solved using BFS but DFS makes it so much easier.
I will leave this one here as an exercise for you. Just use my solution in case you get stuck.
Take the same challenges and exercises I gave you for BFS and try to implement them using DFS instead. Also, for more practice, give a try to the following exercises:
You can see this algorithm as an application of DFS. Its implementation just needs one minor change to the regular DFS: after processing all the children of a node, add this node to a stack.
It is that simple.
The best way to intuitively understand what this algorithm achieves is to imagine a bunch of tasks, some of which depend on others (task 1 cannot start until task 2 has finished). A topological sort will list all these tasks preserving this structure of dependencies.
Let’s solve a problem using this algorithm.
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Example 2:
This is the classical topological sort problem. There are a bunch of courses to take and some depend on others. This can be modeled as a directed graph. A topological sort would return the ordering of courses you should take to finish all courses.
A prerequisite to applying topological sort is that the graph is directed and acyclic. From the problem description, we can see that the graph is directed. We can detect if it contains any cycles and compute a topological sort in the same pass.
A more indirect but still valid approach would be to first check whether it has cycles and only if there are no cycles, compute a topological sort.
Here you can find a few more problems to practice.
Have fun!
I have seen data structure mostly used as another way to implement the sliding window technique you read about earlier in this article. The only difference with a standard FIFO queue is that you can operate (insert and delete elements) on both ends of the queue.
That’s it. Simple.
Let’s see how such a minor change can simplify some kind of these problems.
Given an array, nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
*Note: Open the link for a better understanding of the problem (there is an image). *
Example:
We will use the dequeue to store indices, not values. We need this to know what elements are still part of the sliding window. For every iteration, there are four things to do.
This technique can be applied to find the minimum or other properties of a contiguous block of data in an array.
Design your own circular dequeue, to fully grasp the internals of this data structure.
The best way to think of a trie is as an extension of a tree, where you store characters that form words as you move through the different branches of the trie.
There are variants where you store suffixes instead of prefixes, where you use compression to reduce the size of the trie, etc. But at its basic, it is another type of tree.
They are used everywhere:
Implement a trie with insert, search, and startsWith methods.
Here is a simple implementation (for an interview, of course) of a trie. Compared to a tree, you just:
Given a 2D board and a list of words from the dictionary, find all words on the board. Each word must be constructed from letters of adjacent cells, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
This might not be the simplest way of solving this problem, but it is a clear application of a trie.
At every step, you will have built some candidate string and need to check if it belongs to the dictionary. A hash set containing all the words in the dictionary would give a very good performance. Why bothering with a trie then? Because a trie can tell you whether that path is worth exploring or not, improving the efficiency of our solution.
In our previous example, imagine we form the string “oa”.
We can check if this prefix (potential word) exists in our trie. It exists since we have added the word “oath”. Now imagine we keep moving right through our board and form the string “oaa”.
In our trie, there are no words that contain the prefix “oaa”, so we can backtrack at this point.
With a hash set that contains all the words, you could not do this type of prefix matching, unless you create two different tables: one for prefixes and another one for words.
This is a complex problem because it combines different elements and it is not easy to implement, so do not get discouraged if it takes you a few tries (no pun intended) to get it right.
Design your own autocomplete!
Some problems can be solved by using two different instances of the same data structure, so it is worth keeping it in mind when you get stuck in a problem. I have seen it mostly with:
Do not limit yourself to these.
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.
For example,
Design a data structure that supports the following two operations:
In increasing order of difficulty:
This section deserves a separate article. Here I will list some basic tricks and common bit manipulation problems.
This is the most comprehensive site I have found on this topic. Use it as a reference.
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
This problem can be solved just by using the XOR operator:
If we XOR all the numbers in the array (integers in the range [0,n]) with all the integers in [0 to n], the pairs will produce zeroes and the missing number will be XORed with 0 (resulting in itself), solving our problem.
Given an integer, write a function to determine if it is a power of two.
I got this one in an interview.
Powers of two can be expressed in binary as a leading 1 and some 0s:
With this, it is simple to figure out if a number is a power of two or not. You can achieve fast if you know what the following line does (I am sure you can figure it out on your own):
x & (x-1)
This trick is worth knowing since it is used a lot.
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Example 1:
This problem is very straightforward: iterate through all the bits in the input and count how many how of them are 1s.
Try to use the trick I showed you in the previous exercise to improve the performance of this algorithm (in the average case).
These are for you to practice the previous techniques:
This is another very frequent type of problem. You are given a list of elements and have to return the top K, defining top as:
I have seen some of the following (or some sort of variation) asked in interviews.
There is no single data structure that will always give the right solution, but the following elements are very useful:
Priority queues usually provide a better complexity.
Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example 1:
Pretty straightforward: count how many times each word appears (using a hash table) and somehow return the k most common elements.
For this last part, you either:
Or
It is worth knowing this second approach since it can be applied to other problems.
Here is a simple solution in C++ using a priority queue.
We have a list of points on the plane. Find the K closest points to the origin (0, 0). Here, the distance between two points on a plane is the Euclidean distance.
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
The obvious solution is to compute the distance to every single point, add them to an array, sort and get the top k. This is fine, but it can be improved with a priority queue.
We use a max heap, where the root of the heap is the maximum element of the heap. Why the maximum? Our heap contains the K points closest to the origin and the root points to the element that is the furthest from the origin amongst all the other points. If we find a point closer to this one, it may still be further than the rest, but we need to drop our current top and add this new point to the heap.
These problems are common too. There is not a unique approach to all of them, but if you know how to solve the problem of merging 2 lists, you can solve the problem of merging K lists to a bunch of instances of the simpler problem. As I mentioned, this is a very powerful approach that you should always keep in mind.
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4
We solve this problem with the same Two pointer technique we saw at the beginning of this article. In this case, we traverse linked lists instead of arrays, but the same ideas apply.
Given an array of linked-lists lists, each linked list is sorted in ascending order.
Merge all the linked-lists into one sort linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
This is the general version of the previous problem. As I said, you can reduce this problem to many instances of the previous problem by merging lists 2 at a time. However, here I will present a more efficient solution.
Now, instead of two sorted lists, we have K. We need to create a list from picking the next minimum element of all the lists. Since they are sorted, it will be the first element of one of these lists. Luckily, there is a data structure that returns its minimum element in O(1) and has an insertion complexity of O(log K): a priority queue.
For every list, we add to the priority queue a pair containing:
After we pop an element, we add its value to our solution and add to the priority queue the new head of that list (the pair stores the value and the index of the list).
With this information, try to solve the problem. You will learn much more from it than from reading my solution without trying first.
Rabin Karp is a great example of how to design a simple and efficient algorithm using intelligently a rolling hash function. It can be used to find a string s in a text t.
The basic ideas that you need to remember to be able to reconstruct this algorithm are the following:
If we put all this together, we will efficiently compute hashes and only compare c and s when they have the same hash, reducing the number of comparisons and thus the average complexity of our algorithm (worst case, we need to compare all substrings and are back to the brute force method).
Return the index of the first occurrence of needle in a haystack, or -1 if the needle is not part of the haystack.
Example 1:
Example 2:
Based on the above paragraphs, try to code the Rabin-Karp algorithm on your own to solve this problem.
As I have already mentioned here and in other articles, do not try to memorize things. It is counterproductive. You will end up mixing concepts, giving the right solution to the wrong problem, and forgetting what you have memorized. This is why you need to understand the algorithms. If you understand the basic data structures and can turn your ideas into code, you can also code these algorithms.
The best way to learn them is how I showed you when I described the Rabin-Karp algorithm:
1.Understand what problem this algorithm or data structure is trying to solve: Here, learning where other alternatives fall short is helpful.
2.Break it down to the key elements or steps that define the algorithm. Understand them individually and how they connect.
From this, code the algorithm.
I wanted to show you how this breakdown process can be applied to a much more complex data structure. It is very unlikely that you will need to know about quad-trees for an interview. I just read about them once and found them so interesting that I decided to implement them.
From Wikipedia:
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions…
Now that we know the formal definition, I think it is easier to get an intuitive idea of what quadtrees can do from one of its applications.
Imagine we are trying to model a physical system made of a bunch of particles, each having a certain mass. Every particle attracts every other particle in the system. If we have N particles, at every step of our simulation, the number of interactions we need to process grows as N^2. This will be extremely slow for large values of N.
Since the attraction between two particles decays with the square of the distance, we can neglect the contribution of particles that are far. How do we know which particles are far without iterating through all the particles (the problem we are trying to avoid in the first place)? Here is where quadtrees come in handy.
Using quadtrees, we can efficiently query all the particles in a certain region. The lookup takes O(logN) time, making our overall time for every step O(n log n) since we have to do this for N particles.
Notice how at this point we do not care so much about the implementation. This is more of a high-level understanding of the data structure and to get an idea of where it can be useful.
In the next section, we will get into more detail.
Let’s go back to the definition:
A quadtree is a tree data structure in which each internal node has exactly four children.
So, our quadtree class is not very different from any other tree that you may have encountered (including the trie I presented earlier). Each node will contain:
Knowing what problem a data structure is trying to solve and breaking it down to its basic elements makes it much easier to implement it and especially to remember what the data structure is about and when it can be used. All you have to “memorize” is its definitions and properties – which are easier to remember if you think about what it is trying to solve.
You can try to implement it in your favorite language here.
If you want to learn more about this data structure, I recommend these two to see a quadtree in action.
Here is a list of other topics that are good to know and I have not explicitly mentioned in the article. You don’t need to learn them all in one sitting.
I have presented a list of 20 techniques that you will make your next interview a breeze. You will be using some of them at work too, or they might inspire you for side projects.
The point is not to learn every single data structure or algorithm in a book. As you can see, most of them are either basic techniques or small tweaks on basic data structures you already knew. I want to show you that you can achieve a lot with what you already know.
PS: I hope you found this useful. If so, like and share this article and follow me on Twitter.
You have probably heard lately the terms tokens, crypto tokens, and cryptocurrencies. In this article,…
Here you are going to see how to approach coding challenges like a pro and…
UTXO vs Account-Based Blockchains Introduction Bitcoin and Ethereum differ in many ways. In this article,…
This guide is a summary of my study notes for the Certified Kubernetes Application Developer…
Bloom filters are a data structure developed by Burton Howard Bloom in 1970. You can…
Merkle trees, also known as binary hash trees, are a type of binary tree. They…