Must Know Coding and Problem-Solving Concepts to Ace Your Big Tech Interview
Here is a guide without any fluff on preparing for your Coding and Problem-Solving Interviews for a FAANG (Meta, Apple, Amazon, Netflix, Google, Microsoft).
In the beginnning, forget about the HARD questions in Leetcode (LC) if those do come up in the interview — Talk about your approach and ask for hints if you can’t proceed. But what you should do are as many EASY and MEDIUM questions in LC as you can per topic (given below). Then, read different problem statements and try to reason which algorithm best suits the problem.
Before you read the rest of the article, I wanted to point out the no. 1 reason why most people fail a coding test is because they can’t solve something that they think would be very easy to solve. e.g., Reversing a Linked List.
2D Matrix
You have to flip the image, traverse the matrix in a spiral order, or something similar. These questions require you to maintain 4 pointers: left, right, top, and bottom. As you traverse from left to right, you increment the top by 1, then traverse from top to bottom, then decrement the right pointer by 1, then traverse from right to left, then decrement the bottom pointer by 1, then traverse from bottom to top, and finally increment the left pointer by 1, and repeat till there left is equal to or greater than right, and the top is equal to or greater than the bottom.
Binary Search
2D Row and Column Sorted Matrix
You are given a 2D Matrix, sorted by row and column in an increasing or decreasing manner. You need to find certain element/s using Binary Search. In most cases, you would start at the Bottom-Left or Top-Right, which is unusual, and then move in a staircase way up-right or down-left through the matrix.
Median Finding
In this problem, you must find the median of the merged array of 2 arrays. The technique is to run a binary search till you have split the 2 arrays in such that the merged array is split into equal halves. This requires some practice, where you use the array to run a binary search and then see if the conditions are being met before choosing the left or right halves.
Monotonic Stack
You maintain a stack that contains elements in increasing or decreasing order, thus called a monotonically increasing or decreasing stack. The elements are pushed into the stack by first comparing, and if the element meets the criteria (should be greater or lesser), it is pushed on top of the existing element in the stack. If it doesn’t meet the criteria, the top element is popped off, and the new element is pushed on top of the stack. The problems generally require you to find the next highest or lowest in a list of numbers and do this for each number.
The problems where you have an array of elements, and as you iterate through the elements, you need to keep track of the minimum or the maximum, and once you find the minimum or maximum, you discard all elements that have come before till you find something that is smaller than the minimum or larger than the maximum should hint you to use a Monotonic Stack.
A very interesting problem that uses a Monotonically Increasing Stack with other data structures and is very common in the interviews is the Remove Duplicate Letters problem, where we need to find a lexicographically smallest sequence that contains all letters in the string by removing letters.
Monotonic Queue using Deque
It is generally rare to see a problem that requires a Monotonic Queue, or rather I should say it won't be easy to come up with a solution that involves a Monotonic Queue. Still, this data structure do exist and one of the most interesting question regarding this data structure is Jump Game IV. The way this data structure works is that you always compare the current element with the element on the top of the queue, while you add data from the end of the queue.
Quick Select
This algorithm aims to find what element would go at a particular position and uses a very similar approach to Quick Sort. You start with 2 pointers, left and right, and then partition the list by a particular pivot value chosen from the list and then finally put the pivot element at the position where all elements to its left are smaller than itself, and all elements to the right are greater than itself.
Prefix Sum
You create another array that calculates the cumulative sum as you move from the beginning to the end of the original array. Using this new array, you can solve several sub-array problems.
1D Vectors
As the name suggests, an array of integers are given, and to solve the problem, you need to create another array with their prefix sums.
2D Matrix
This is complex as you create the prefix sum of a 2D Matrix by walking down each element in the 2D Matrix by calculating the running sum by columns in the row and adding the prefix sum of the previous row. To get the range sum, you take the Prefix sum of the right bottom, then subtract the prefix sum of the top rows, then subtract the prefix sum of the left columns, and then finally add back the Prefix sum of the top left.
Two Pointer Techniques
Lead-Lag pointers
You have two pointers, most likely pointing to 2 separate nodes in a list so that you can keep track of nodes separated by a distance. e.g., current and previous pointers help reverse the Linked List (LL).
Fast-Slow pointers
You have two pointers, most likely starting from the same node, but one moves faster than the other as you change them. e.g., fast and slow pointer, which points to the same head node, but fast moves two times faster than the slow pointer, which is handy if you want to find the middle node of the LL or detect cycles.
One of the best article I have found to learn the concept:
https://towardsdatascience.com/two-pointer-approach-python-code-f3986b602640
Left-Right pointers — Greedy
You set two pointers, a left pointer at the beginning and a right pointer at the end of a list, and calculate the max or min, and then, based on the problem, you increase the left pointer or decrease the right pointer to find the max or min.
Sliding Window Techniques
These problems involve finding some or counting all subarrays/substrings. Subarrays/Substrings: These are contiguous and ordered chunks of elements from an array/string.
Fixed Sliding Window
In these types of problems, we take a fixed-sized window generally provided to us in the problem itself and move the window one element at a time. The optimization we do, as we move the window by one element, is that we compute the difference in the result by dropping the last element of the previous position sliding window contained and then adding in the new element that the new position sliding window will contain.
Dynamic Sliding Window
Note: This is one of the most trickiest types of problem. It can range from finding a valid solution to collecting all valid solutions (when the end goal is met by expanding and/or shrinking the window). You need a lot of practicing to get a decent understanding of these problems.
In these types of problems, the window size is not fixed, and we either expand the window or shrink the window based on some criteria given in the problem. We do a very similar optimization as the Fixed Size Window problem; we drop the last element of the previously sized window when we shrink the window or add the new element that gets added when we expand the window.
Kadane’s Algorithm
Note: There are problems that can take both Kadane’s Algorithm and Dynamic Sliding Window together. These are generally HARD problems, don’t expect these to just come up. Most likely just applying Kadane’s Algorithm will come up which can be solved by using Dynamic Programming (DP) too.
This is a special type of Dynamic Sliding Window, which breaks the rule that expanding the window should only take the value we are searching for in a single direction, i.e., positive or negative. This generally applies when we have both negative and positive numbers in a list, and we have to find a subarray with something like the desired sum. You keep a global maximum (or minimum) sum and the current maximum (or minimum) sum. Then, for each element, you take just the element or the current maximum with the element and set the current maximum to the max of these two values. Similarly, you compare the new current maximum with the global maximum and set it accordingly.
Maximum Sum of Subarrays ending at each Index
When applying just Kadane’s algorithm, we get the sum of the Maximum Sum of Subarrays ending at each index, and then we take a maximum on all these sums to get the Maximum Sum of Subarrays. But we can also store the Maximum Sums of Subarrays that end at each index so that we can use them to solve problems like the Maximum Sum of Subarrays with at least K elements. In this case, you take the sum of K elements from each Index of the Array and then add the Maximum Sum of Subarrays for the Index previous to this to get the Maximum Sum of Subarrays of K and above elements.
Backtracking
These problems generally involve finding some or counting all subsets from an array/string. Subsets: These are arrays/strings that can be formed by taking all or some elements from another array/string. They don’t have to be contiguous/ordered.
Combinations
In these types of problems, you either select the current element and then select or not select elements that come after it in a list. Generally, we also sort the list by some criteria before selecting and not selecting elements.
Permutations
In these types of problems, we would select all elements differently. So, in a list, we select the first, then the second, and finally the third, or we might first select the second, then the first, and finally the third.
Subsets
In these types of problems, we collect the result as we select or do not select the current element and the elements after that. These are similar to combination problems but where the resulting elements are collected as we try the next element.
Graph
Depth-First Search
You have a function that recursively calls itself with the next node; this is important to solve many from LL, Trees, and Graphs.
Breadth-First Search
You have to find the shortest path in an unweighted graph. You need a queue to store the following children to process.
Spanning Tree
Two separate algorithms use different data structures to find the minimum spanning tree. Prim starts from a node, adds the adjacent nodes in a min-heap, and takes the less weighted edge node. Kruskal requires a union-find and sorting the edges by weight, then keeping the nodes' union.
Shortest Path
This uses Dijkstra’s algorithm to solve problems where you must find the shortest path. You start from the starting node, drop edges in a min-heap, and select the less weighted edges till the final node is processed.
Post-Order DFS — Topological Sorting
This differs for Directed and Undirected graphs. In the case of Undirected graphs, you maintain a visited array, and as you run a DFS and run into a node already marked visited in the visited array, it has a cycle. In the case of a Directed graph, you need to do backtracking on top of the algorithm for an Undirected graph, which means you need to keep a visited and pathVisited array and keep marking both as you run the DFS. Still, in the post-order, you need to unmark the pathVisited array, and in case you run into a node with both visited and pathVisited array marked as visited for the node, then it has a cycle.
Kahn’s Algorithm — Topological Sorting
This uses Kahn’s algorithm to find the topological ordering of dependencies. Here, you calculate the indegrees and create the adjacency list-based graph. Then you put the nodes with 0 indegrees in a queue and keep removing the indegrees and adding the nodes with 0 indegrees in the queue. This only works in a DAG (Directed Acyclic Graph).
Union Find
This special data structure helps with Spanning Tree, Connected components related to graph problems. You track each node's parent and rank as you union them, and while doing a find operation, you do path compression.
BST
This is a particular type of graph, so everything in the graph section can be performed here, too. But the way it is structured, there are some exciting things you can do with BSTs that are impossible with any generic graph.
Binary Traversal
You traverse the tree with DFS by going down the left or the right node to calculate the result. This can solve problems like range sum, searching for an element, searching for the closest element, etc.
In-order Traversal
You traverse the tree with DFS by processing the left node, the current node, and finally, the right node. This can solve an interesting problem where you want to read the elements in increasing or decreasing sorted order without even sorting the tree.
Post-order Traversal
You will traverse the tree with DFS but will process the left and right nodes and most likely use their results to process the current node. This is very useful to solve problems like validating the BST.
Level-order Traversal
You will traverse the tree by levels; in this case, you would do a BFS with 2 separate queues. First, you would go through the 1st queue; then, for each unexplored child, you would drop it in the previous queue. Once you finish the 1st queue, you will copy over all the elements from the 2nd queue to the 1st queue and keep going. Every time you copy over the elements, you will be processing the tree by levels.
Vertical-order Traversal
You will traverse the tree by each level, where you consider vertical lines marking the root with (0, 0), while its left will be (-1, 1) and right (1, 1), and their children will be (-2, 2), (-1, 2) and (1, 2), (2, 2) respectively. This will help you solve several problems like top-level, right/left, vertical order views of the binary tree, etc.
Reverse Level/Vertical Order
This is one of the most exciting traversal as it is the reverse of Level/Vertical Order where rather than sending tuples of information down to the children and processing it at the children, you get data from the two children and process it in the parent. This can be elements you were searching for in the tree, the min and max values, or getting the costs of taking a path like in problems - Lowest Common Ancestor, Validating a Binary Search Tree, Making Costs of Paths Equal in a Binary Tree respectively.
Predecessor and Successor Nodes
You can find the predecessor of a node by running a DFS from the left child and only taking the right children from there on. The last right child will be the predecessor. Similarly, if you run a DFS from the right child and only take the left children from there on. The last left child will be the successor.
Count Nodes by Height
This is another exciting pattern where you calculate things on the left and the right with O(log n). Then, if it doesn’t meet the criteria, you repeat this process for the left and right nodes, i.e., again calculate the things on the left and right with O(log n) and send back the result up through the recursion. The best way to understand this is to count complete tree nodes; the most optimal solution is O(log n * log n).
Reverse PostOrder Traversal
This is another exciting way to solve a few problems, where you have to traverse the right node first, then the left node, and finally the original node. This is used in the problem Flatten a Binary Tree into a Linked List. The other thing to note in the problem is to keep track of the last node we saw so that it can be modified as we traverse through the tree.
Trie
You can represent any array of elements in this unique structure called the Trie. It is a particular type of tree where each node contains a list of pointers to the following nodes.
Integer Trie
An integer can be converted to its binary representation and stored in a Trie. This will help with any bitwise operation.
Dynamic Programming (DP)
These have already been categorized by Neetcode here: https://docs.google.com/spreadsheets/d/1pEzcVLdj7T4fv5mrNhsOvffBnsUH07GZk7c2jD-adE0. I will still add them here just for completeness.
Misc
These are problems that are generally 1D or Constant Space DP problems where the last few results are kept to calculate the next result. Classic Examples are Fibonacci Numbers, Climbing Stairs, etc.
1/0 Knapsack or Take or Not Take
These are problems where you are given a list and try to calculate the result by taking only one element in each iteration or skipping the element from the list.
Unbounded Knapsack
These are problems where you are given a list, but unlike 1/0 Knapsack, you can take an element as often as you would like or skip it. This technique can also be used to choose elements that will sum up to half the sum of the array.
Subsequences
These are problems where you take elements like 1/0 Knapsack but from 2 separate lists to achieve a goal.
Palindromes
These are different from typical DP problems as there is no space requirement in general, but you need a trick where you take each element as the center of a possible palindromic string or subsequence and achieve the goal.
Greedy
Note: This is the most trickiest of all algorithms. Some of the problems will make your brain melt, so hope that your interviewer doesn’t want to make you bleed and asks some brain-melting greedy optimizable problem. Do the brute force if you can, curse your interviewer in the back of your mind, and move on.
This is the most important and interesting topic, as a few problems can be solved using a Greedy approach. You need to know the types of problems that fit into this paradigm.
Intervals — Sort by start time
In these problems, you are trying to take only some elements by merging them. This technique is very useful in solving Interval Graph Coloring problems, where you must color/associate rooms to accommodate different intervals.
Intervals — Sort by asc end time, and then desc start time
In these types of problems, you try to avoid as many conflicts as possible. You sort by the end time and take the smallest if there is a tie. Then, take the sum of the non-overlapping intervals.
Intervals — Sort start times and end times separately
In these types of problems, you take two separate arrays and add all the start and end times. Then, you sort the arrays in non-decreasing order to process.
One of the best article I have found to learn this concept:
https://mecha-mind.medium.com/algo-pattern-recognition-interval-and-scheduling-problems-184df33f7cf1
Sorting both Increasing and Decreasing Order
Generally, Greedy problems require either sorting or counting. For sorting problems, you sort the input array and then pick elements as required. But a special type of problem is where you are given an array of tuples of 2 integers and need to find the optimal solution. As in the problem, The Number of Weak Characters in the Game, you will need to first sort the array in ascending order by the first integer in the tuple, then you need to sort the array in decreasing order by the second integer in the tuple for the optimal solution.
Segment Trees
You store the elements of an array into a binary tree, where it takes log n time to query or update the values and maintain their sum or anything else you would like to query for. This is very useful for problems like range queries.
Binary Maths
These problems require some understanding of Bit Manipulation. Most importantly, you need to understand XOR.
Bit Masking
You must create a mask and then apply and/or operator to set or clear a bit.
Integer to Binary
You keep dividing the number by 2; the reminders will make up the digits in binary representation.
XOR
There are specific properties you need to know about this fascinating operator.
- The XOR of 2 same number is 0. e.g. 1 ^ 1 = 0, 8 ^ 8 = 0.
- The XOR of any number with 0 is the same number. e.g. 1 ^ 0 = 1, 8 ^ 0 = 8.
- The maximum result of XOR of any number with a number from a range of 1…n will equal the number XOR with the maximum value in the range 1…n. e.g. max(8 ^ [1…n]) = 8 ^ n
One of the most interesting problems using XOR is Single Number III. This requires not only the knowledge of XORing numbers to remove duplicates, but if the 2 numbers differ by 2 bits, then bucketing all numbers into 2 separate buckets having that particular bit set or not set and then XORing them would actually give you the resulting numbers. This can also be generalized to as many numbers there are. Find the differing bits, group numbers having the differing bits recursively, and then XOR all numbers in each buckets.
