Data Structures and Algorithms: 20 Problem-Solving Techniques

This is the article I wish I had read when I started coding. 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 explaining how to , with examples. step-by-step guide learn data structures and algorithms Furthermore, I recommend you read , where I outlined a high-level strategy to prepare for your next coding interview as well as the top mistakes to avoid. this post I have grouped these techniques in: Pointer based Recursion based Sorting and searching Extending basic data structures Miscellanea 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. 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 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. Pointer based techniques 1. Two Pointers This technique is very useful on and arrays whose elements we want to . sorted arrays group The idea is to use two (or more pointers) to split the array into different areas or groups based on some condition: Elements smaller than, equal to and greater than a certain value Elements whose sum is too small or too large Etc. The following examples will help you understand this principle. Two sum 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: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. Solution Since the array is sorted, we know that: a The largest sum is equal to the sum of the last 2 elements The smallest sum is equal to the sum of the first 2 elements For any index in [0, a.size() – 1) => a[i + 1] >= a[i] i With this, we can design the following algorithm: We keep 2 pointers: , starting at the first element of the array, and starting at to the last. l r If the sum of a[l] + a[r] is smaller than our target, we increment l by one (to change the smallest operand in the addition for another one equal or larger than it at ); if it is larger than the target, we decrease r by one (to change our largest operand for another one equal or smaller at ). l+1 r-1 We do this until a[l] + a[r] equals our target or l and r point to the same element (since we cannot use the same element twice) or have crossed, indicating there is no solution. Here is a simple C++ implementation: twoSum( & a, target) { l = , r = a.size() - ; sol; (l sum) { ++l; } { --r; } } sol; } vector int const vector int int int 0 1 vector int while const int if 1 1 break else if else return 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. Challenges Here are two variations of this exercise: and . They can be solved similarly by them to this very same problem. three sum four sum reducing This is a very common technique: . transform a problem whose solution you don’t know to a problem that you can solve Remove duplicates from array 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: Given nums = [1,1,2], Output = 2 Example 2: Given nums = [0,0,1,1,1,2,2,3,3,4], Output = 5 It doesn’t matter what values are set beyond the returned length. Solution The array is and we want to move duplicates to the end of the array, which sounds a lot like . How would you solve this problem using two pointers? sorted grouping based on some condition You will need one pointer to iterate through the array, . i And a second pointer, , one to define the area that contains no duplicates: [0,n]. n The logic is as follows. If the values of the elements at index (except = 0) and are: i i i-1 The same, we don’t do anything – this duplicate will be overwritten by the next unique element in . a Different: we add to the section of the array that contains no duplicates – delimited by , and increment n by one. a[i] n { (nums.empty()) ; n = ; ( i = ; i & nums) vector int if return 0 int 0 for int 0 if 0 1 return This problem has linear time complexity and constant space complexity (it is usually the case for problems solved using this technique). Sort colors 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: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Solution The groups this time are: Smaller than 1 Equal to 1 Larger than 1 What we can achieve with 3 pointers. This implementation is a bit tricky, so make sure you test it thoroughly. { smaller = , eq = , larger = nums.size() - ; (eq & nums) vector int int 0 0 1 while if 0 else if 2 else 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 problem described by Dijkstra. National Dutch flag Remove the n-th node from the end of a linked list 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. Solution This is one of the most common variations of the two-pointer technique: introducing so that one of the pointers reaches a certain condition, the other one is in the position you are interested in. an offset In this case, if we move one of the pointers, , n times and then start advancing both at the same time by one node, when reaches the end of the list the other pointer, , will point to the node right before the node we want to delete. f f s 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’. 2. Pointers moving at different speeds Now, you will have two pointers moving at different : at every iteration, one of the pointers will advance one node and the other will advance two nodes. We can use this variation to: speeds Get to the middle element of a linked list Detect cycles in a linked list Etc As usual, it will become clearer once I present some examples. Find the middle node of a linked list of unknown size 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: Input: [1,2,3,4,5] Output: Node 3 from this list Solution Solving this problem in 2 passes is easy: on the first pass we compute the size of the list, , and on the second pass we only advance nodes to find the element at the middle of the list. This approach has linear complexity in time and constant in space. L L/2 How can we use 2 pointers to find the middle element in one single pass? If one of the pointers, , moves twice as fast as the other one , when reaches the end, will be in the middle of the list. f s f s 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. { ListNode* slow = head; ListNode* fast = head; (fast != && fast->next != ) { slow = slow->next; fast = fast->next->next; } slow; } ListNode* middleNode (ListNode* head) while nullptr nullptr return Detect cycle in a linked list 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: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the second node. Solution 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 the length of the list, and space complexity of O(L), since in the case – no cycles – we need to add all the elements of the list to the hash set. L worst 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? If fast reaches the end of the list, the list does not contain any cycles. If there is a cycle, since fast moves twice as fast as slow, it is just a matter of time (iterations, to be more precise) that the fast node catches the slow one, pointing both to the same node, which indicates the existence of a cycle. Now, let’s translate this solution into code: { ListNode* slow = head, *fast = head; (fast){ slow = slow->next; fast = fast->next; (!fast) ; fast = fast->next; (slow == fast) ; } ; } bool hasCycle (ListNode *head) while if break if return true return false Find the duplicate number 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: Input: [1,3,4,2,2] Output: 2 Solution This is the same problem/solution as the previous problems, for arrays instead of linked lists. { slow = nums[ ], fast = slow; { slow = nums[slow]; fast = nums[nums[fast]]; } (slow != fast); slow = nums[ ]; (slow != fast){ slow = nums[slow]; fast = nums[fast]; } slow; } int findDuplicate ( & nums) const vector int int 0 do while 0 while return Challenges Here are more problems that can be solved using this technique: Detect if two linked lists have elements in common Happy numbers 3. Sliding Window The sliding window technique eases the task of finding optimal that meet a certain condition: chunks of contiguous data Longest subarray that … Shortest substring containing … Etc 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, r Create variable to keep track of the Iterate until condition A is satisfied: Based on condition B: update l, r both Update res Return res and result (res) or Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. Example 1: Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3 Solution sounds a lot like that meet a certain condition.* Find the length of the longest substring without repeating characters finding optimal *chunks of contiguous data Based on the recipe I described above, you will need: Two pointers, and , to define our substring . l r s A variable, , to store the length of the longest substring we have seen so far. sol A way of keeping track of the characters that form : a set, , will be perfect for this. s seen While iterating through the string: If the current character is in to start removing elements from the beginning of our . seen*you have to increment *l s Otherwise, add the character to , move forward and update . seen r sol { sol = ; l = , r = ; seen; (r < s.size()) { find = seen.find(s[r]); (find == seen.end()) { sol = max (sol, r - l + ); seen.insert(s[r]); ++r; } { seen.erase(s[l++]); } } sol; } int lengthOfLongestSubstring ( & s) const string int 0 int 0 0 unordered_set int while const auto if 1 else return Challenges For more practice, you can try the following problems: Permutation of a string Max consecutive ones There might be simpler solutions but focus on using this technique to get a better grasp of it. Recursion based techniques 4. Dynamic Programming I already published a long and detailed article on this topic that you can find . here 5. Backtracking 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 to a previous state and tries the next candidate. backtracks Backtracking problems present you with a list of choices. Should you: Place in ? this piece this position Add to the set? this number Try in next? this number this position Etc 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: { (isLeaf(n) { (isSolution(candidate)){ sol.add(candidate); ; } { ; } } (child in n) { (backtracking(child)) ; } ; } boolean backtracking (Node n) if if return true else return false //Explore all children for if return true return false This can of course change depending on the problem: If you need solutions, the helper function returns nothing (void) to avoid stopping when we find the first solution. all To backtrack, you may have to bring your program to a previous state before you can move forward After you choose a child, you need to detect if the candidate solution is viable or not: the definition of viable depends on the problem Etc 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. N queens 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: Input: 4 Output: [ [“.Q..”, “…Q”, “Q…”, “..Q.”], [“..Q.”, “Q…”, “…Q”, “.Q..”] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above. Solution This is a classic backtracking problem: We need all solutions here, which is why the recursive function returns nothing as I explained in the introduction of this section. Do not worry too much about the function for now. Try to see the recipe I gave (slightly modified) you in action. isViableSolution : > solveNQueens( n) { > solutions; board(n, (n, )); solveBoard(solutions, board, , n); solutions; } { (col == n){ solutions.push_back(board); ; } ( row = ; row = && col >= x; x++){ (board[row-x][col-x] == ) ; } ( x = ; row + x = x; x++){ (board[row+x][col-x] == ) ; } ; } }; { class Solution public vector vector string int vector vector string /** This is usually solved with a vector of integers, where each integer represents the position of the queen in that column. This particular problem expects strings. Each string represents a column */ vector string string '.' 0 return void solveBoard ( >& solutions, & board, col, n) vector vector string vector string int int if return for int 0 if 'Q' 1 //Backtracking - we bring our board to the previous state '.' bool isViableSolution ( & board, row, col) vector string int int int for int 1 if 'Q' return false for int 1 0 if 'Q' return false for int 1 if 'Q' return false return true Letter combination 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: Input: “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. Solution 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. : 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 . Note last step My solution, in C++: letterCombinations( &digits) { (digits.empty()) {}; letters { , , , , , , , , , }; sol; ; h(sol, , candidate, letters, digits); sol; } { (idx == digits.size()){ sol.push_back(candidate); ; } ( &c : letters[digits[idx] - ]) { candidate[idx] = c; h(sol, idx + , candidate, letters, digits); } } vector string const string if return const vector string "" "" "abc" "def" "ghi" "jkl" "mno" "pqrs" "tuv" "wxyz" vector string string candidate (digits.size(), ) ' ' 0 return void h ( &sol, idx, &candidate, &letters, &digits) vector string int string const vector string const string if return for const char '0' 1 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: candidate; … ( &c : letters[digits[idx] - ]) { candidate.push_back(c); h(sol, idx + , candidate, letters, digits); candidate.pop_back(); } string //instead of string candidate (digits.size(), ' '); for const char '0' 1 Sudoku solver 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. Solution In an interview, unless you have plenty of time, you will not need to implement , just to sketch it. I know a colleague who got this question in an on-site. isViableSolution Even though the code is long, it is mostly because of . Otherwise, it is not very different from other backtracking problems. isViableSolution { helper(board); } { (col == size){ col = ; ++row; (row == size){ ; } } (board[row][col] != ){ helper(board, row, col + ); } ( i = ; i >& board) vector vector char bool helper ( >& board, row = , col = ) vector vector char int 0 int 0 if 0 if return true if '.' return 1 for char '1' '9' if if 1 return true '.' return false bool isViableSolution ( >& board, row, col, c) const vector vector char int int char for const auto if return false for int 0 if return false const int const int for int 0 for int 0 if 3 3 return false return true Challenges N queens II Generate parenthesis Palindromic partitioning Letter tile possibilities 6. Subsets I have created a generic separate section for: Subsets Combinations Permutations Etc 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. Subsets Given a set of distinct integers, nums, return all possible subsets ( ). the power set Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Solution For every index , you need to generate two solutions: i One that contains a[i] One that does not contain a[i] Until you get to the end of the array. Here’s a simple implementation of what we have discussed. > subsets( & nums) { > sol; partial; h(sol, partial, nums); sol; } { sol.push_back(partial); (idx == nums.size()){ ; } ( i = idx; i >& sol, & partial, & nums, idx = ) vector vector int vector int const vector int int 0 if return for int 1 Subsets – containing duplicates 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! Solution > subsetsWithDup( nums) { > sol; partial; sort(nums.begin(), nums.end()); h(sol, partial, nums); sol; } { sol.push_back(partial); (idx == nums.size()){ ; } ( i = idx; i >& sol, & partial, & nums, idx = ) vector vector int vector int const vector int int 0 if return for int if 1 continue 1 Permutations Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] Solution 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. > permute( & nums) { > sol; p (nums); h(nums, sol, p); sol; } { (idx == nums.size()){ sol.push_back(p); ; } ( i = idx; i &nums, > &sol, &p, idx = ) const vector int vector vector int vector int int 0 if return for int 1 Permutations with repetitions Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1] ] Solution 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. { (pos == nums.size()) { res.push_back(nums); ; } ( i = pos; i > permuteUnique( & nums) { (nums.empty()) {}; sort(nums.begin(), nums.end()); > sol; helper(sol, , nums); sol; } void helper ( >& res, pos, & nums) vector vector int int vector int if return for int if continue 1 1 vector vector int vector int if return vector vector int 0 return 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 Challenges For extra practice: , and . Combination sum Combination sum II Combination sum III Sorting and searching algorithms 7. Sorting 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 example, sometimes you have to return indices, therefore sorting is not an option Can I sort the input? How would this problem change if the elements were sorted? . The best sorting algorithms have a complexity of O(n log n) – sorting integers can be done in O(n) How does sorting affect the overall complexity? 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. Valid anagram Given two strings s and t, write a function to determine if t is an anagram of s. Example 1: Input: s = “anagram”, t = “nagaram” Output: true Example 2: Input: s = “rat”, t = “car” Output: false Solution By definition, two strings are anagrams if they contain . Therefore, we can simply sort both strings and compare them. The overall time complexity is O(n log n). the same characters in different order { (s.size() != t.size()) ; sort(s.begin(), s.end()); sort(t.begin(), t.end()); s == t; } bool isAnagram ( s, t) string string if return false return Intersection of two arrays Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Solution 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: A = [1,2,4,5] B = [2,3,5,7,9,11] And two pointers, for A and for B, starting at index 0 in each array. l r A[l] = 1 B[r] = 2 We need to increment to see if A has a 2: B can’t contain a 1 to the right of , because it is sorted. l r In short, we compare both elements: If they are the same, we include them to the array representing the intersection of both arrays and advance pointers both If they are different, we move the pointer pointing to the smallest of the two elements. intersect( & nums1, & nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); sol; i = , j = ; ( i nums2[j]) { ++j; } { ++i; } } sol; } vector int vector int vector int vector int int 0 0 while if else if else return 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)). Challenges . In another section, I will present a different solution, slightly faster. K closest points to origin Largest number 8. Intervals Most interval related problems I have seen boil down to: as an array of two elements, a pair/tuple or a custom class (this is the cleanest option) Modeling the interval the input Sorting Iterating through the sorted array and deciding what to do based on the starts/ends of the intervals 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. Merge intervals Given a collection of intervals, merge all overlapping intervals. Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Solution > merge( >& intervals) { sort(intervals.begin(), intervals.end(), []( & i1, & i2){ i1[ ] > sol; curr( ); (i < intervals.size()){ curr = intervals[i++]; (i < intervals.size() && intervals[i][ ] <= curr[ ]){ curr[ ] = max(curr[ ], intervals[i][ ]); ++i; } sol.push_back(curr); } sol; } vector vector int vector vector int const auto const auto return 0 0 int 0 vector vector int vector int 2 while while 0 1 1 1 1 return Interval list intersections Given two lists of closed intervals, each list of intervals is pairwise disjoint and in . Return the intersection of these two interval lists. sorted order Solution > intervalIntersection( >& A, >& B) { > sol; i = , j = ; (i < A.size() && j < B.size()){ lo = max(A[i][ ], B[j][ ]); hi = min(A[i][ ], B[j][ ]); (lo <= hi){ sol.push_back({lo, hi}); } (A[i][ ] < B[j][ ]) ++i; ++j; } sol; } vector vector int const vector vector int vector vector int vector vector int int 0 0 while const int 0 0 const int 1 1 if if 1 1 else return 9. Variations on 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. Binary search 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: m = (l + r) / ; const int 2 Can you spot the problem here? This line can overflow. The safe way of computing this middle element is: m = l + (r - l) / ; const int 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 problems in disguise. binary search { l = , r = v.size() - ; (l v[m]) { l = m + ; } { r = m - ; } } ; } template typename int binary_search ( & v, k) const vector int int 0 1 while const int 2 if return else if 1 else 1 return -1 Integer square root 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: Input: 4 Output: 2 Solution 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: If is 0 or 1, its square root is . This lets us start testing numbers from 2. The upper bound of the range can be reduced to x/2, since (x/2)^2 = x^2/4 >= x => x >= 4, which is true for any integer in the range [2,…] x x With this, we can search in [2, x/2] and speed things up a bit. { (x == || x == ) x; sol = ; l = , r = x / ; (l x){ r = m - ; } { sol = m; l = m + ; } } sol; } int mySqrt ( x) int if 0 1 return int 1 int 2 2 while const long 2 if return else if 1 else 1 return Challenges Have fun! Search insert position Random pick with weight Minimum in rotated sorted array Minimum in rotated sorted array 2 10. Breadth-First Search This is one of the techniques you need to know to explore trees and graphs. Since many problems can be modeled as graphs, you this technique. To implement it, we just need to use a queue and add to this same queue the children of the nodes we process from . must know q 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. Word ladder 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: Only one letter can be changed at a time. Each transformed word must exist in the word list. Notes: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. Example 1: Input:beginWord = “hit”,endWord = “cog”,wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] Output: 5 Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5. Solution I got asked this question during my on-site interview at Amazon. The idea is to model this problem using a graph: Nodes represent wordsEdges connect words that only differ by one letter 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. { (beginWord == endWord) ; dict(wordList.begin(), wordList.end()); todo; todo.push(beginWord); dict.erase(beginWord); ladder = ; (!todo.empty()) { ladder++; n = todo.size(); ( i = ; i & wordList) const string const string const vector string if return 1 unordered_set string queue string int 1 while int for int 0 string for int 0 char for int 0 26 'a' if if return return 0 : After you visit the DFS section What would happen if we use DFS instead? Do you see any benefits/drawbacks? Order level tree traversal 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. Solution 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. > levelOrder(TreeNode* root) { (!root) {}; > sol; q; q.push(root); partial; (!q.empty()){ size = q.size(); (size--> ){ n = q.front(); partial.push_back({n->val}); q.pop(); (n->left) q.push({n->left}); (n->right) q.push({n->right}); } sol.push_back(partial); partial.clear(); } sol; } vector vector int if return vector vector int queue vector int while int while 0 auto if if return Challenges 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: using BFS to explore all the links on a website. Web crawler Minesweeper 11. Depth-First Search 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. Number of islands 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: Input: grid = [ [“1″,”1″,”1″,”1″,”0”], [“1″,”1″,”0″,”1″,”0”], [“1″,”1″,”0″,”0″,”0”], [“0″,”0″,”0″,”0″,”0”]] Output: 1 Solution 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: Iterate through the matrixFor every 1 you find, increase the counter and the island sink To sink the island, you need to visit all the surrounding 1s in the matrix, which is equivalent to , which sounds a lot like a recursive problem. visit all the neighbors of that node and of all its neighbors You can try to solve this using BFS too, but DFS is much shorter. { numIslands = ; ( r = ; r > dirs {{ , }, { , }, { , }, { , }}; { m[r][c] = ; ( &d : dirs){ nr = r + d[ ]; nc = c + d[ ]; (isValid(m, nr, nc)){ sinkIslands(m, nr, nc); } } } { r >= && r = && c >& grid) vector vector char int 0 for int 0 for int 0 0 if '1' return const vector vector int 1 0 -1 0 0 1 0 -1 void sinkIslands ( > &m, r, c) vector vector char int int '0' for const auto const int 0 const int 1 if bool isValid ( > &m, r, c) vector vector char int int return 0 0 0 '1' Symmetric tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). Solution 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. { (!root) ; helper(root->left, root->right); } { (!p && !q) ; (!p || !q) ; p->val == q->val && iS(p->left, q->right) && iS(p->right, q->left); } bool isSymmetric (TreeNode* root) if return true return bool helper (TreeNode* p, TreeNode* q) if return true if return false return Challenges 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: Path sum Path sum 2 Validate BST 12. Topological sort 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. Course schedule II 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: Input: 2, [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]. Example 2: Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3]. Solution 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 . From the problem description, we can see that the graph is directed. We can detect if it contains any cycles compute a topological sort in the same pass. directed and acyclic and 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. findOrder( numCourses, >& prerequisites) { > adj(numCourses, ( )); ( &p : prerequisites){ u = p[ ]; v = p[ ]; adj[u].push_back(v); } white(numCourses, ), grey(numCourses), black(numCourses); sol ( ); ( i = ; i < numCourses; ++i){ (white[i] && hasCycle(adj, i, white, grey, black, sol)){ {}; } } sol; } { white[i] = ; grey[i] = ; ( & n : adj[i]){ (black[i]) ; (grey[n] || hasCycle(adj, n, white, grey, black, sol)) ; } grey[i] = ; black[i] = ; sol.push_back(i); ; } vector int int vector vector int vector vector int vector int 0 for const auto int 0 int 1 vector bool true vector int 0 for int 0 if return return bool hasCycle ( >& adj, i, &white, &grey, &black, & sol) const vector vector int int vector bool vector bool vector bool vector int //We have started exploring this node false true for const auto if continue if return true false true return false Challenges you can find a few more problems to practice. Here Have fun! Extending basic data structures 13. Dequeues 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 of the queue. both ends That’s it. Simple. Let’s see how such a minor change can simplify some kind of these problems. Sliding window maximum 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: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Solution We will use the dequeue to store , 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. indices Remove elements in the dequeue which are outside of the current sliding window (one per iteration) Remove elements in the dequeue which are smaller than the current element we are at since they cannot represent the max of that sliding window all Add the current element to the deque Once we have completed the first sliding window, we can start adding elements to our solution. By design, the element at the front of our dequeue will contain the maximum of the sliding window, which is what we are interested in. This technique can be applied to find the minimum or other properties of a contiguous block of data in an array. maxSlidingWindow( & nums, k) { sol; dq; ( i= ; i = k ) sol.push_back(nums[dq.front()]); } sol; } vector int const vector int int vector int deque int for int 0 // Step 1 if // Step 2 while // Step 3 // Step 4 if -1 return Challenge Design your own , to fully grasp the internals of this data structure. circular dequeue 14. Trie 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: Auto-complete Spell checkers IP routing Longest prefix/suffix matching Etc Implement a trie Implement a trie with insert, search, and startsWith methods. Solution Here is a simple implementation (for an interview, of course) of a trie. Compared to a tree, you just: An extra boolean to indicate whether that node marks the end of a wordA data structure to store pointers to the node’s children: a hash table, an array of characters, etc. : isWord; children; Node() : isWord( ) {} }; { Node* curr = root; ( i = ; i children[word[i] - ]; curr; } : Node* root; Trie() { root = Node(); } { Node * curr = root; ( i = ; i children[c]){ Node* newChild = Node(); curr->children[c] = newChild; } curr = curr->children[c]; } curr->isWord = ; } { Node* curr = findNode(word); curr ? curr->isWord : ; } { Node* curr = findNode(prefix); curr ? : ; } }; { class Trie private { struct Node bool unordered_map int false Node* findNode ( &word) const string for int 0 'a' return public /** Initialize your data structure here. */ new /** Inserts a word into the trie. */ void insert ( &word) const string for int 0 const char 'a' if new true /** Returns true if the word is in the trie. */ bool search ( &word) const string return false /** Returns true if there is any word in the trie that starts with the given prefix. */ bool startsWith ( &prefix) const string return true false Word search II 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: Input: board = [ [‘o’,’a’,’a’,’n’], [‘e’,’t’,’a’,’e’], [‘i’,’h’,’k’,’r’], [‘i’,’f’,’l’,’v’] ] words = [“oath”,”pea”,”eat”,”rain”] Output: [“eat”,”oath”] Solution 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 at this point. backtrack 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. > dirs {{ , }, { , }, { , }, { , }}; isWord; children; Node() : isWord( ){} }; Node* root; Trie(){root = Node();} { Node* cur = root; ( &c : w){ (cur->children.find(c) == cur->children.end()){ cur->children[c] = Node(); } cur = cur->children[c]; } cur->isWord = ; } { Node* cur = root; ( &c : prefix){ (cur->children.find(c) == cur->children.end()){ ; } cur = cur->children[c]; } lastNode = cur; cur != ; } { (lastNode){ res = lastNode->isWord; res; } Node* cur = root; ( &c : w){ cur = cur->children[c]; (!cur){ ; } } lastNode = cur; lastNode->isWord; } { lastNode->isWord = ; lastNode = ; } Node* lastNode; }; Trie t; : findWords( >& board, & words) { ( & w : words) t.insert(w); sol; ( row = ; row = && nrow = && ncol < board[ ].size() && board[nrow][ncol] != && t.hasPrefix(candidate + board[nrow][ncol])){ candidate.push_back(board[nrow][ncol]); addWords(board, nrow, ncol, sol, candidate); candidate.pop_back(); } } board[row][col] = old; } const vector vector int 1 0 -1 0 0 1 0 -1 { struct Trie { struct Node bool unordered_map char false new void insert ( & w) const string for const auto if new true bool hasPrefix ( &prefix) const string for const auto if return false return nullptr bool isValidWord ( &w) const string if bool return for const auto if return false return void deleteWord () false nullptr public vector string vector vector char const vector string for const auto vector string for int 0 for int 0 0 string candidate ( , board[row][col]) 1 if return void addWords ( > &board, row, col, &sol, &candidate) vector vector char int int vector string string if const char '-' for const auto const int 0 const int 1 if 0 0 0 '.' Challenges Design your own ! autocomplete 15. Two instances of the same data structure 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: Queues Stacks Arrays Do not limit yourself to these. Find median from a stream of data 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, [2,3,4], the median is 3[2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) – Add an integer number from the data stream to the data structure.double findMedian() – Return the median of all elements so far. Solution priority_queue , less > L; priority_queue , greater > H; : MedianFinder() { } { (L.empty() == && x > L.top()) { H.emplace(x); } { L.emplace(x); } (H.size() > L.size() + ) { L.emplace(H.top()); H.pop(); } (L.size() > H.size() + ) { H.emplace(L.top()); L.pop(); } } { (H.size() == L.size()) { (H.top() + L.top()) * ; } { H.size() > L.size() ? H.top() : L.top(); } } }; { class MedianFinder int vector int int int vector int int public void addNum ( x) int if false else if 1 else if 1 double findMedian () if return 0.5 else return Challenges In increasing order of difficulty: Implement a queue using two stacks Tree zigzag order traversal Media from data stream Miscellanea 16. Bit manipulation This section deserves a separate article. Here I will list some basic and common bit manipulation problems. tricks This is I have found on this topic. Use it as a reference. the most comprehensive site Missing number Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array. Example 1: Input: [3,0,1] Output: 2 Solution This problem can be solved just by using the XOR operator: Any bit XORed with itself produces a 0 -> a ^ a = 0 Any bit XORed with 0 produces the original bit -> a ^ 0 = a XOR is associative = a ^ (b ^ c) = (a ^ b ) ^ c 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 and the missing number will be XORed with 0 (resulting in itself), solving our problem. zeroes { res = nums.size(); ( i = ; i & nums) const vector int int for int 0 return Power of two Given an integer, write a function to determine if it is a power of two. Solution I got this one in an interview. Powers of two can be expressed in binary as a leading 1 and some 0s: 2: 1 4: 10 8: 100 16: 1000 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. { n > ? (n & (n - )) == : ; } bool isPowerOfTwo ( n) int return 0 1 0 false Number of 1s 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: Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits. Solution 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). { sum = ; (n != ) { sum++; n &= (n - ); } sum; } int hammingWeight ( n) uint32_t int 0 while 0 1 return Challenges These are for you to practice the previous techniques: Single number Gray code Hamming distance Power of 4 17. Top ‘K’ Elements This is another very frequent type of problem. You are given a list of elements and have to return the top K, defining as: top The largest/smallest The closest/furthest to a point The most frequent in the list Etc 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: Hash table Priority queue Sorting (the input or as an intermediate step) Priority queues usually provide a better complexity. Top k frequent words 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: Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2 Output: [“i”, “love”] Explanation: “i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order. Solution Pretty straightforward: count how many times each word appears (using a hash table) and return the k most common elements. somehow For this last part, you either: Put all the elements with its frequencies in an array and sort it Or Use a priority queue 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. topKFrequent( & words, k) { freq; ( &w : words) freq[w]++; l = []( pair & p1, pair &p2){ (p1.first == p2.first) p1.second p2.first; }; priority_queue , >, (l)> pq(l); ( it = freq.begin(); it != freq.end(); ++it){ (pq.size() second, it->first}); } { top = pq.top(); (top.first second){ pq.pop(); pq.push({it->second, it->first}); } } } sol (k); (!pq.empty()){ sol[--k] = pq.top().second; pq.pop(); } sol; } vector string const vector string int map string int for const auto auto const int string const int string if return else return int string vector int string decltype for auto if else auto if vector string while return Variation K closest points to origin 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: Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Solution 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 , 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. max heap pair > pivi; : > kClosest( >& points, K) { l = [] ( pivi& p1, pivi &p2) { p1.first , (l)> pq(l); ( &p : points){ d = p[ ] * p[ ] + p[ ] * p[ ]; (pq.size() d){ pq.pop(); pq.push({d, {p[ ], p[ ]}}); } } > sol; ( i = ; i <= K; ++i){ sol.push_back(pq.top().second); pq.pop(); } sol; } typedef int vector int public vector vector int const vector vector int int auto const const return vector decltype for const auto //Avoid taking the square root. Won't change the result and it's faster const int 0 0 1 1 if 0 1 else if 0 1 vector vector int for int 1 return 18. K-way merge 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 2 sorted lists 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->4 Output: 1->1->2->3->4->4 Solution 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. { = &dh; (l1 && l2){ (l1->val val) { curr->next = l1; l1 = l1->next; } { curr->next = l2; l2 = l2->next; } curr = curr->next; } (l1){ curr->next = l1; } (l2) { curr->next = l2; } dh.next; } ListNode* mergeTwoLists (ListNode* l1, ListNode* l2) ListNode , *curr dh ( ) 1 while if else if else if return Merge k sorted lists 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 Solution 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: The head of that list An index to remember to which list that element belongs 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. { pair pni; comp = []( pni & p1, pni& p2) { p1.first->val > p2.first->val; }; priority_queue , (comp)> pq (comp); ( i = ; i next; } } = &dh; (!pq.empty()){ p = pq.top(); pq.pop(); curr->next = p.first; curr = curr->next; ListNode* next = lists[p.second]; (next){ idx = p.second; pq.push({next, idx}); lists[p.second] = lists[p.second]->next; } } dh.next; } ListNode* mergeKLists ( & lists) vector typedef int auto const const return vector decltype for int 0 if ListNode , *curr dh ( ) -1 while const auto if int return 19. Rolling hash 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 in a text . Rabin Karp s t The basic ideas that you need to remember to be able to reconstruct this algorithm are the following: This is an improvement over the brute force method, where you compare and every candidate substring, , which is inefficient. s c If two strings are the same, they will produce the same hash. The inverse is not true: two different strings may produce the same hash. Using a rolling hash function we can compute the hash of a new string in O(1) If we put all this together, we will efficiently compute hashes and only compare and 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). c s Find string in text 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: Input: haystack = “hello”, needle = “ll” Output: 2 Example 2: Input: haystack = “aaaaa”, needle = “bba” Output: -1 Solution Based on the above paragraphs, try to code the Rabin-Karp algorithm on your own to solve this problem. { nsize = needle.size(); (nsize == ) ; hsize = haystack.size(); (nsize > hsize) ; msbPower = ; nhash = ; hhash = ; mod = ; ( i= ; i<nsize; i++) { (i != ) { msbPower *= ; msbPower %= mod; } nhash = nhash* +needle[i]; nhash %= mod; hhash = hhash* +haystack[i]; hhash %= mod; } (nhash == hhash && haystack.compare( , nsize, needle) == ) ; ( i= ; i<=hsize-nsize; i++) { hhash -= haystack[i ]*msbPower; hhash %= mod; (hhash < ) hhash += mod; hhash = hhash* +haystack[i+nsize ]; hhash %= mod; (nhash == hhash && haystack.compare(i, nsize, needle) == ) i; } ; } int strStr ( & haystack, & needle) const string const string int if 0 return 0 int if return -1 int 1 int 0 int 0 const int 10000009 //A big prime number for int 0 if 0 26 26 26 if 0 0 return 0 for int 1 -1 if 0 26 -1 if 0 return return -1 20. How to learn data structures and algorithms 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 . If you understand the basic data structures and can turn your ideas into code, you can also code these algorithms. understand the algorithms If you are wondering how to learn data structures and algorithms, I already showed how to do it when I described Rabin-Karp: : Here, learning where other alternatives fall short is helpful. Understand what problem this algorithm or data structure is trying to solve . Understand them individually and how they connect. Break it down to the key elements or steps that define the algorithm . From this, code the algorithm Example 1: Binary search Binary search is an improvement over a linear search for . It reduces the size of the array in half at every step, achieving a complexity of O(logN) instead of N. sorted arrays Two points: a)Since the array is sorted, lets us discard half of the array at every step (the half containing elements that are too large or too small compared to the . b)If the pointers cross, this is > , there is no solution. comparing our target to the middle element of the array target l r { l = , r = v.size() - ; (l v[m]) { l = m + ; } { r = m - ; } } ; } template typename int binary_search ( & v, k) const vector int int 0 1 while const int 2 if return else if 1 else 1 return -1 Example 2: Quad-tree 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. What is a quad-tree? From Wikipedia: A quadtree is a tree data structure in which . Quadtrees are the two-dimensional analog of octrees and are … each internal node has exactly four children most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions What problem is it trying to solve? 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 (the problem we are trying to avoid in the first place)? Here is where quadtrees come in handy. without iterating through all the particles 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. What are the key elements of a quad-tree? Let’s go back to the definition: A quadtree is a tree data structure in which . each internal node has exactly four children They decompose space into adaptable cells Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits The tree directory follows the spatial decomposition of the quadtree. 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: An integer representing its maximum capacity A boolean indicating whether it is a leaf or not (which means, the node has been divided because it reached its maximum capacity) Pointers to it 4 children An array of containing the points included in that node 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 . 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. remember what the data structure is about and when it can be used Putting it all together You can try to implement it in your favorite language . here : { flag = grid[x][y]; ( i = x; i < x + len; i++) ( j = y; j < y + len; j++) (flag != grid[i][j]) { Node *tl = constructHelper(grid, len / , x, y); Node *tr = constructHelper(grid, len / , x, y + len / ); Node *bl = constructHelper(grid, len / , x + len / , y); Node *br = constructHelper(grid, len / , x + len / , y + len / ); Node( , , tl, tr, bl, br); } Node(grid[x][y] == , , , , , ); } : { n = grid.size(); (n == ) ? : constructHelper(grid, n, , ); } }; { class Solution private Node * constructHelper ( > &grid, len, x, y) vector vector int int int int int for int for int //if not a leaf, go deeper if 2 2 2 2 2 2 2 2 return new true false return new 1 true nullptr nullptr nullptr nullptr public Node * construct ( > &grid) vector vector int int return 0 nullptr 0 0 If you want to learn more about this data structure, I recommend videos to see a quadtree in action. these two Nice to know 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. Conclusions 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. Previously published at https://www.yourdevopsguy.com/how-to-learn-data-structures-and-algorithms-20-problem-solving-techniques-you-must-know/