DEV Community: Your DevOps Guy

SPL - Structured Programming Language

Your DevOps Guy — Wed, 29 Mar 2023 12:33:04 +0000

Do you know there is live beyond SQL? In this post I'm going to show you an interesting alternative.

An alternative to SQL

Let's understand first what a database does. A database can achieve two main functions: perform calculations and process transactions, which are what we often call OLAP and OLTP. When it comes to databases, we want systems that run fast and make interacting with the databases (writing queries) easy.

Have you ever thought about SQL's limitations when it comes to these two characteristics?

SQL Limitation 1: Easiness of writing/reading queries

Let’s start with easy in writing.

When solving real life problems (not textbook problems), SQL statements can be ugly very quickly. Here's a relatively simple example, to calculate the maximum number of consecutive days that a stock price keeps rising:

select max (consecutive_day)
from (select count(*) (consecutive_day
      from (select sum(rise_mark) over(order by trade_date) days_no_gain
            from (select trade_date,
                         case when closing_price>lag(closing_price) over(order by trade_date)
                              then 0 else 1 END rise_mark
                  from stock_price ) )
      group by days_no_gain)

If writing this sort of queries is not easy, but reading them (whether you or a colleague wrote them) is not easy either.

SQL Limitation 2: Speed

Let's consider a simple task, often used as an example: take the top 10 items in a dataset containing 100 million pieces of data. This task is not complicated to write in SQL:

SELECT TOP 10 x FROM T ORDER BY x DESC

However, the execution logic corresponding to this statement is to perform the big sorting for all the data first, and then take the top 10, and discard the remaining data. As we all know that sorting is a very slow action, and will traverse the data many times. If the amount of data is too large to be loaded into memory, it also needs to buffer the data in external storage, resulting in a further sharp decrease in performance. If the logic embodied in this statement is strictly followed, the operation will not run fast anyway. Fortunately, many programmers know that this operation does not need the big sorting, nor the external storage to buffer since it can be done by traversing only once and only occupying a little memory space, it means a higher performance algorithm exists. Regrettably, such algorithm can't be implemented in SQL. We can only hope the database optimizer is smart enough to convert this SQL statement to a high-performance algorithm to execute, but the database optimizer may not be reliable when the situation is complicated.

It seems that SQL is not doing well in both aspects. Although these two examples are not very complicated, SQL does not perform well in either example. In reality, the difficult-to-write and slow running situation abounds in SQL codes with thousands of lines.

Why these limitations?

To answer this question, we need to analyze what exactly the implementation of calculation with program code does.

Essentially, the process of programming is the process of translating problem-solving idea into a precise formal language executable by the computer.

For the formal language used to describe calculation method, its core lies in the algebraic system adopted. To put it simply, the so-called algebraic system includes two key elements: data types and corresponding operation rules. For instance, the key elements of arithmetic we learned in primary school is the integer and the operations including the addition, subtraction, multiplication and division. Once we get both key elements, we can write the operation we want with the symbols stipulated in the algebraic system to something, i.e., the code, and then the computer can execute.

At present, the mainstream database is the relational database, and the reason why it is called this way is because its mathematical basis is called relational algebra. SQL is exactly a formal language developed from the theory of relational algebra.

Now we can answer why SQL is not competent in both aspects we expect. The problem lies in relational algebra, and the relational algebra is just like an arithmetic system with only addition and no multiplication. Therefore, it is inevitable that many things cannot be done well.

And, unfortunately, this problem is at the theoretical level, and it won't help no matter how optimized it is in practice, it can only be improved in a limited way, not eradicated.

Why SPL is competent

SPL's theoretical basis is no longer the relational algebra, but something called discrete dataset. The formal language designed based on this new algebra is named SPL (structured process language).

SPL redefines and extends many operations of structured data, specifically, it adds the discreteness, enhances ordered computation, implements a thorough set orientation, supports object references, and advocates stepwise operation.

Recoding the previous problems in SPL will give you a direct feeling. To calculate the maximum consecutive days that a stock keeps rising:

stock_price.sort(trade_date).group@i(closing_price<closing_price[-1]).max(~.len())

Although the calculation idea is the same as the previous SQL, it is easier to express and no longer confusing, because of the introduction of ordering characteristic.

Take the top 10 out of 100 million pieces of data:

T.groups(;top(-10,x))

SPL has richer set data types, it is easy to describe the efficient algorithm that implements simple aggregation on a single traversal, without involving big sorting action.

Conclusion

In addition to theoretical differences, SPL has many engineering-level advantages such as: easier to write parallel computing code, large memory pre-association to improve foreign key join performance, unique column storage mechanism to support arbitrary segmentation and parallel computing, etc.

For more details, check out their Github repo.

Merkle Trees and Bitcoin

Your DevOps Guy — Mon, 08 Feb 2021 19:22:35 +0000

This post was originally published at https://www.yourdevopsguy.com/merkle-trees-and-bitcoin.

Merkle trees, also known as binary hash trees, are a type of binary tree. They can be used to efficiently verify the integrity of large sets of data. They are used in both blockchain and non-blockchain-related projects.

Merkle trees are build from the bottom up:

The leaves of the tree contain the hash of each element in our dataset. This dataset could represent a list of transactions, parts of a file, etc.
Each internal node is the result of hashing the concatenation of the hashes of its two children.

Outline

Hash functions
Properties of a Merkle tree
What problems can a Merkle tree solve?
Implementing a Merkle tree in JavaScript
Known vulnerability
Sparse Merkle Trees
Conclusions

Hash functions

Hash functions take as input any piece of data (a string, an image, etc.) and produce a fixed-length output. An example of a hash function is SHA-256, which takes data of arbitrary size and produces an output that is 256 bits long.

Good hash functions have the following properties:

Uniformity. They produce evenly distributed outputs in the possible output range. In the SHA-256 example, this range would go from 0000...0000 to 1111...1111.
Deterministic. The same input will always generate the same output.
Fast to compute.

Cryptographic hash functions need additional properties to make them more secure:

One-way functions. Given an input x, they generate an output h(x). From an output h(x), it is computationally infeasible to find the input it came from, x.
Collision resistant. The likelihood of 2 different inputs x, y producing the same output h(x)=h(y) should be negligible.
Resistant to preimage attacks. Given an output h(x), it is infeasible to find an input y such as h(x) = h(y).
A minor modification in the input will produce a completely different output. This is known as the avalanche effect.

Properties of a Merkle Tree

The properties of a Merkle tree derive from its structure and its use of hash functions:

Data integrity. The root of the tree will change if any node in the tree is modified. Even the same dataset, with its elements presented in a different order (ex: [T2, T1, T3, T4] instead of [T1, T2, T3, T4]) will produce a different tree.
Partial verification. We do not need the full tree to verify whether a transaction belongs to it. We only need a path that starts in one of the leaves and goes all the way up to the root (proof of inclusion).
The height of a tree of N leaves is ceil(log2(N)). The function ceil(x), known as ceil, maps x to the smallest integer greater or equal than x. Ex: ceil(3.14) = 4 and ceil(3) = 3.

What problems can a Merkle tree solve?

Introduction to Blockchain

I will use Bitcoin to illustrate how Merkle trees can verify if a transaction belongs to a block. In case you aren’t familiar with blockchains, we can oversimplify things imagining that:

A blockchain is a distributed linked list of elements called blocks.
Blocks contain:
- A list of transactions.
- A header that stores metadata.
- Part of this metadata is the root of the block’s Merkle tree, called Merkle root.
Each block points to the hash of its predecessor, to ensure immutability. If the previous block in the chain changes, even by one bit, its hash would change and it would break the chain.

Imagine you are running an app that needs to verify if a transaction T belongs to a block B. In Bitcoin, full nodes store a block’s Merkle root along with all its transactions. For them, it is easy to verify if T belongs to B. Also, they can generate proofs for any transaction in a block on demand.

What if the app runs on a device with limited disk, computing power, and bandwidth? To determine whether T belongs to B, the device needs information. It can retrieve this information from other participants in the network.

Problems

The following problems arise:

How can we trust that the data we receive from other nodes is correct? Data might be corrupted and other nodes in the network can send fake data.
Given the limited resources, how can we minimize the amount of information we need to receive from the network?

Merkle trees can help to solve these problems. From the properties of Merkle trees we covered above:

Data integrity solves problem 1. Let’s assume we receive different pieces of information from a series of participants in the network. We have B, which contains its Merkle root. The data we receive from the network is used to build a Merkle tree whose root must be the same as B‘s Merkle root. Otherwise, we cannot trust the data that others have shared with us.
Partial verification and having a height of ceil(log2(N)) solve problem 2. Hashing all the transactions would also work to verify data integrity. However, that does not scale well, because proof generation and verification would be O(N) operations.

Simplified Payment Verification(SPV) nodes, commonly known as lightweight nodes or light clients, do not store full blocks. They interact with the network to request the information they need to verify transactions. They can assess whether a transaction belongs to a block requesting an inclusion proof and the block header, where the Merkle root is stored.

Implementing a Merkle Tree in JavaScript

The algorithm to generate a Merkle root from a list of transactions is as follows:

The leaves of a Merkle tree contain the hashes of the transactions that belong to a block. In the image above, [T1, T2, T3, T4, T5, T6] represent transactions.
From them, we generate the leaves of the Merkle tree using a hash function. If the number of transactions is odd, we duplicate the last node.
We take 2 consecutive leaves and hash the concatenation of their hashes. This generates their parent. In the image, T1’s and T2’s parent is equal to hash(hash(T1) + hash(T2)).
We keep repeating this process with all the transactions at the same “level”. These parents will be siblings that will form a new level in the tree hierarchy.
We keep repeating this process until we only have one element left, the root of the tree.

You can find here my implementation of a Merkle tree. It can verify a Bitcoin block’s Merkle root and generate and verify proofs of inclusion.

Known vulnerability

Bitcoin’s Merkle tree duplicates the last node in levels with an odd number of nodes. Also, if Bitcoin finds a block that is not valid, it caches its root to avoid trying to mine it again. This combination makes the tree susceptible to second preimage attacks: for an input x, we can find a second input y, different from x, such that h(x) = h(y).

How does this design suffer from this? Let’s go back to our first example, based on the tree represented on the image below:

The leaves of the tree come from a block B1 containing these transactions [T1, T2, T3, T4, T5, T6]
The level right above the leaves is [hash(hash(T1) + hash(T2)), hash(hash(T3) + hash(T4)), hash(hash(T5) + hash(T6))]
Since we have an odd number of nodes, we duplicate the last one. Hence, the next level changes to [..., ..., hash(hash(T5) + hash(T6)), hash(hash(T5) + hash(T6))]
This is equal to the level produced by a block B2 with the following transactions [T1, T2, T3, T4, T5, T6, T5, T6].

B2 contains duplicate transactions, making the block invalid. Nodes would cache this root so that next time they find a block with this root they discard it. Both B1 and B2 produce the same root. Thus, nodes will reject B1, even though B1 might be a valid block.

For more details, have a look at this post and this comment in Bitcoin’s source code.

There is another known vulnerability in Bitcoin’s original Merkle trees (already fixed). Understanding it requires more knowledge of how Bitcoin builds transactions. Since this is an introductory article, I have decided to leave it out. However, I might cover transactions in more depth in future articles and revisit this vulnerability.

Sparse Merkle Trees

A Sparse Merkle Tree (SMT) is a variation of a Merkle Tree, where every leaf node has an index along with its value. All leaves are initialized to an empty (null) value. By design, SMTs have 2^256 leaves.

The Merkle tree I described above can verify that a transaction is part of the block by exploring the path from its corresponding leaf to the root of the tree.

However, they cannot be used to prove that a transaction does not belong to a block. And in general, to prove that elements do not belong to a dataset. SMTs can do this.

SMTs can produce proofs of non-inclusions in an efficient manner. The idea is that we know the index of every element. Thus, you know which leaf contains an element. If an element is not part of the tree, the leaf where the element would be stored will be null. Therefore, to produce a proof of non-inclusion, we produce a proof of inclusion generated from that node initialized to null.

Proofs of inclusion work in the same way as Merkle trees’.

Updating a leaf an SMT is also efficient because we only need to modify the path that goes from that leaf to the root. Since SMTs have 2^256 leaves, only 256 nodes need modification.

SMTs deserve their own article, but I wanted to at least introduce the basic idea behind them.

Conclusions

Now you should have a clearer idea of what Merkle trees are and what they are used for. If you want to learn more, I suggest you investigate how:

Git uses them to keep track of changes in files.
DynamoDB uses them to identify any inconsistencies between nodes.

I hope you found this article helpful. Share it, because you could help someone pass their exams or get a job.

6 Hard Dynamic Programming Problems Made Easy

Your DevOps Guy — Tue, 19 Jan 2021 12:54:41 +0000

In this article, I gave you an introduction to Dynamic Programming with several examples. Here I will solve 6 harder Dynamic Programming problems to show you how to approach them.

Unique Paths

A robot is located at the top-left corner of a m x n grid

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

Solution

Given that the robot can only move to the right or down, we can reach the position {m,n} (bottom-right corner) in two different ways:

Going to the right from (m, n -1)
Going down from (m -1, n)

Therefore, the total number of paths to (m, n) will be the number of paths to (m, n-1) plus the number of paths to (m-1, n). These two new problems are just instances of the original problem. Therefore we can use recursion to generate a solution.

Let's call f(m,n) the number of ways to reach the position (m, n).

f(0,0) = 1\
f(m,n) = 0 if n or m are outside the grid\
f(m,n) = f(m-1, n) + f(m, n-1)

Recursive solution

Line 5 represents the number of paths to reach any position in the first column or row of the grid (we can only reach them by going all the way right or down, therefore we return 1).

We can improve upon this if we notice that many problems will be computed more than once:

To compute f(m,n) we need f(m-1, n) and f(m, n-1).
For f(m-1, n) we need f(m-2, n) and f(m-1, n-1).
For f(m, n-1) we need f(m, n-2) and f(m-1, n-1).

If you suspect a problem might be solved via Dynamic Programming problems, I recommend drawing a tree with all possible paths to see if there are repeated subproblems. If you can derive a recursion and prove that there are repeated subproblems and optimal substructure, you can apply Dynamic Programming.

Top-down Dynamic Programming

Going from the recursive solution to a top-down DP solution is very straightforward. We just need to:

Check if the results are already in our cache. If so, we return them.
If they're not, cache them before we return.

In line 8, I check if (-1 == dp[n]) to avoid bugs like if(dp[n] = -1).

Bottoum-up Dynamic Programming

Now, let's take a different look at the problem. From (0,0) we can go right to (0,1), (0,2), etc. There is only one way to reach these positions. Similarly, there is only one way to reach all the positions in the first column: going down from (0,0). We can start building a table with this information:

dp[0][0] = 0 // Empty grid
dp[i][0] = 1 for i in 1:m // first row
dp[0][i] = 1 for i in 1:n // first col
dp[i][j] = dp[i-1][j] + dp[i][j-1] // Any other position follows the same logic as in the top-down approach

This approach will build the full m*n table with all possible results. We return the one we are interested in: the most bottom-right position.

Complexity

Computing the complexity of the bottom-up approach is trivial. There are two nested loops in which the amount of work is constant, giving an overall time complexity of O(mn). The space complexity is O(m*n*) as well.

For the top-down, it seems a bit trickier, but the logic is the same. We do constant work for every call (because we cache results) and there are O(mn) calls. Therefore, the time complexity is O(mn).

Note:

This problem can be solved in O(m+n) using basic mathematics. You have m rows, n columns and you can only move to the right and down (states). You can code a path using R to symbolize right and D for down. Then, for m rows and n columns you need to generate a string of (m-1) + (n-1) elements that have 2 states: R or D. In this string, there will be m-1 Ds and n-1 Rs. This problem is equivalent to find all permutations of an array of m+n-2 elements (taking into account all the repetitions):

Unique Paths 2

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Solution

Try to solve this one without looking at my solution. The code (for any of the approaches I described for the previous problem) is almost the same. You only need to take into account that cells have values and some of them can be blocked. If a cell is blocked, the robot cannot visit it and therefore there are 0 ways in which the robot can reach, from a cell where the is an obstacle, the cell to its right or down.

To avoid duplication, here is the code only for the bottom-up approach.

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Solution

Recursive solution

Imagine you need to solve this problem by hand. At every step, you have an amount of money and a few coins to choose from. Let's say the coins are 1,2 and 5, and the amount is 11. You can take three different paths:

Take the coin with value 1. You're facing now with the problem of computing the fewest number of coins that you need to get to 10.
Choose the coin with value 2. You're facing now with the problem of computing the fewest number of coins that you need to get to 9.
Take the coin with value 5. You're facing now with the problem of computing the fewest number of coins that you need to get to 6.

Which one will produce the desired output (minimum number of coins)? At this stage, we don't know. We need to explore each path in full and return the minimum.

It is pretty obvious now that we can use recursion to solve this. It should look something like this, with f(n) representing the minimum number of coins to reach n

f(0) = 0
f(n) = -1; for n<0 // No solution
f(n) = for c in coins, return 1 + min(f(n-c)), for n>0

In C++:

Top-down Dynamic Programming

From this it is trivial to get a top-down solution. You only need to add a cache, as we did in the previous problem:

Bottom-up Dynamic Programming

The bottom-up solution takes a different path. The idea is to fill a table with the minimum amount of coins needed to generate the values [0, amount], starting from the "initial conditions":

f(0) = 0
From 0, we can use one coin to get to all the values in the array coins. We initialize them to 1.

Important note:

You may have noticed that I have created arrays that seem to have an extra element. The entry sol[0] represents the problem of reaching the amount 0. This is why it seems there is an offset of 1 in the code (we return sol[amount] instead of sol[amount -- 1] because indices represent quantities). You will see this pattern in more places in this article.

Variation:

How would you solve this problem if there there wasn't an infinite number of each kind of coin.

Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount.

You may assume that you have infinite number of each kind of coin.

Solution

Let's review our previous example: amount = 11 and coins = [1,2,5]. Again, we have the same three choices.

Take the coin with value 1. You're facing now with the problem of computing the fewest number of coins that you need to get to 10.
Choose the coin with value 2. You're facing now with the problem of computing the fewest number of coins that you need to get to 9.
Take the coin with value 5. You're facing now with the problem of computing the fewest number of coins that you need to get to 6.

In this case, instead of getting the minimum of the three, we return the sum of the three paths. If we arrive to an instance where amount = 0, we return 1 (it is a solution we need to count). If amount is negative, that path doesn't lead to a solution and we return 0.

Since this is just a variation on the previous problem, I will only write the C++ implementation of the bottom-up approach. You have the tools to generate recursive and top-down solutions.

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example:

Input: word1 = "horse", word2 = "ros"
Output: 3

Solution

Recursive solution

This problem seems tricky at first, so we need to be systematic and try to work our way into a solution from a good example. Let's take "horse" and "ros", and focus on the last character of each word:

If "e" and "s" were the same, we could "forget about them" and keep working with "hors" and "ro"
Since "e" and "s" are different, we need to make them equal. We have 3 choices:
- Replace "e" with "s" (or "s" with "e"), and now they're the same
- Delete "e" (or "s") and see and continue with the rest of the string "hors" and "ros" to see
- Insert a character ("s" or "e" respectively) to make the last characters equal

Each possibility will generate another subproblem of smaller size, therefore we can code this recursively. We need to find the minimum of these 3 branches and return it (plus 1, since taking any of these paths indicates that there is at least one edit operation).

Top-down Dynamic Programming

If you play around with this example you'll see that this problem has optimal substructure, so I'll just show you the code for the solution top-down here:

Bottom-up Dynamic Programming

And bottom-up here:

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Solution

Recursive solution

This problem has a relatively straightforward solution. If we were to solve this by hand, we would start taking prefixes of our input and see if they belong to our dictionary. As soon as we find one, we repeat the process with the remaining of the string. In other words, we solve a smaller instance of the same problem. Let's try to define the recursion first and later see if there are overlapping subproblems.

f("") = true // if the string is empty, it can be decomposed using the words in wordDict\
f(s) = for every prefix p (and correspondent suffix x) in s:\
    if any f(p) == true, f(s) = f(x)\
    if all f(p) == false, f(s) = false

Let's use the following example to illustrate this algorithm:

s=dogsandcats
dict=[and,dog, dogs, cats]

We start taking prefixes of s until we find one that belongs to dict. In this case, the first prefix that meets this condition is dog.
Our new string s' is "andcats". Repeating 1 we get to sand.
Now, s" is "cats". The prefix cats belongs to the dictionary.
Since s"' is empty, we return true.

This snippet of code solves this problem recursively:

Top-down Dynamic Programming

Coming back to the example, you can see that bot "dogs" + "and" and "dog" + "sand" produce the same suffix: "cat". There are overlapping subproblems and we can use memoization.

Bottom-up Dynamic Programming

The bottom-up approach builds a table, where the empty string is initialized to true and every other entry to false. From there, the logic is the same:

We build the solution for all the substrings of s, from length 0 to the length of s. This is why we have a loop in the range 1,n and another internal loop in the range [i-1,0] to move around all prefixes for that length
If the problem has a solution for the prefix s0,j, we "follow the recursion" on the suffix s[j+1,:): if this is a valid word, there is a solution for the problem represented by dp[i]

This is harder to explain in words than in code, so here it is:

Conclusions

As we have seen, dynamic programming problems can be solved in a systematic way:

Start with small examples and see if their solution can be derived from smaller instances of the same problem. If so, recursion is a natural choice.
Draw a tree with the possible paths you can take depending on the available choices. If you reach the same parameters more than once, you can improve your solution using a cache.
From the recursion, arriving at a top-down solution is mechanical: you just need to add a cache.
The bottom-up approach generates a table based on "the initial conditions" for the recursion.

I hope you found this article helpful. I recommend sharing it with a friend or the rest of the community because you could help someone pass their exams or their next job interview.

For more content, visit my blog, and connect with me on Twitter.

Recursion vs Iteration: 13 Ways to Traverse a Tree.

Your DevOps Guy — Fri, 16 Oct 2020 06:06:13 +0000

To understand recursion, you must understand recursion. I will show you 13 different ways to traverse a tree to compare recursive and iterative implementations. This way, we will kill two birds with one stone: recursion and data structures and algorithms.

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

Linus Torvalds

Recursion, iteration and how to traverse a tree are useful skills to have and common in interview questions. Do not risk failing your next job interview because you didn't take the time to read one article.

I assume you have basic coding skills and are familiar with stacks, queues, recursion, and loops. If this seems too advanced for you, check this article where I have listed some resources to get you started.

For every problem, I will provide also a link to Leetcode so that you can play around with my solution or write your own in your preferred programming language.

My code examples will be in C++. If you are not familiar with the APIs or syntax, that is fine. I am sure you will understand the ideas. That is the goal of this article.

What Is a Tree?

N-ary tree

Trees are data structures that organize data hierarchically. They are defined recursively from a root node, that contains the data that needs to be stored and pointers to its children.

There are many types of trees well-suited for specific applications:

Binary search trees, for efficient searches on sorted data.
B-trees to store database indexes.
Heaps to implement priority queues.
General trees to implement filesystems.
Etc.

There is no point in storing information if you do not know how to access it.

For simplicity, I will focus on binary trees. You will take the code and generalize to trees with up to N children per node.

I will present you with 13 ways to traverse a tree and discuss them in detail. As usual, there will be challenges for you to cement your knowledge. I strongly recommend solving each problem on your own before reading my solution.

You are going to learn infinitely more by doing than by reading or watching.

13 Ways To Traverse a Tree

Most of the problems in this section will be on binary trees. We will define a node as follows:

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 }

Using a struct makes the fields public by default, which is enough for our purposes.

For the complexity analysis, we will assume that we will traverse a tree of height H that contains N nodes.

1. Pre-order Traversal - Recursive

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Pre-order traversal

You can play around with this problem here.

Solution

The pre-order, in-order, and post-order traversal of a tree are defined by the order in which we visit the root, left, and right children of a tree. The pre in pre-order refers to the root. In a preorder traversal of a tree, we first visit the root node, then the left node, and finally the right node.

You can translate this into recursive code very easily. Your function will receive a node, starting with the root of the tree. You need to define:

Base condition: As long as the node is not null,
Recursive relationship: you process it (for instance, print its value), and then call the same function in the left and right children.

For the base condition, you have two alternatives. I have called them A and B in my code. Have a look at the code and try to figure out the pros and cons of each before you look at my comments.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        // helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            sol.push_back(n->val);
            helperA(n->left, sol);
            helperA(n->right, sol);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        sol.push_back(n->val);
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);
    }
};

Alternatives

Option A. Every function call will test whether the node it receives is null or not. Then, it will trigger two recursive calls. This option will result in a larger stack.
Option B. The function assumes that the node is not null. It will generate a recursive call only if the left/right child is not null. The function will execute more if statements but make less recursive calls.

There is no right or wrong solution here without more context. In an interview setting, discuss both options. It will show that you care about your code and think of the implications of what you write.

Your priority should be writing readable and maintainable working code. Only focus on this level of detail when you have profiled your code and have proof that these lines of code make a big impact on the overall performance. Don't guess. Remember.

"Premature optimization is the root of all evil."

Donald Knuth

Complexity

This algorithm visits every node once and adds an element to the end of a vector, which is constant work - amortized. Therefore, the time complexity is O(N).

Can you try to figure out the space complexity? Try to visualize the algorithm on the tree above. How many nodes will be stored in the stack in the "worst-case"?

I am sure you found the correct answer. The maximum number of nodes that you need to store will be equal to the height of the tree, H. Consequently, the space complexity is O(H).

In the next problem, I will show you a non-recursive implementation of the same algorithm to traverse a tree. But before that, I have a little challenge for you.

Challenge

Given an n-ary tree, return the preorder traversal of its nodes' values.

You can code your solution here.

To make you think

A natural follow-up to this problem is to generalize it to trees with N children. Before opening the link to Leetcode, try to first model the nodes yourself. Some interesting questions are:

What data structures are suitable to store at most N children?
If you don't know the maximum number of children a node can have, can you still use this data structure? What other options do you have?
What if you want to make a generic tree that works for different data types? The answer to this question will depend on your programming language: templates for C++, Generics for Java, etc.

For now, focus only on the recursive solution. Even if "it is trivial", we have seen that you can still ask questions and discuss different alternatives.

2. Pre-order Traversal - Iterative

Traverse a tree using pre-order traversal. No recursion allowed.

Give it a try here.

Solution

Now we will see that recursion is not the only way to traverse a tree.

We need to mimic everything that happens under the hood when we use recursive functions. We know that:

First, we visit the root of the tree - add it to the solution.
Then we process the left child, and finally the right child.
We will need to create and handle the stack ourselves instead of relying on recursive calls.
A stack is a Last-In-First-Out data structure. Therefore we have to push the items in the reverse order we want to extract them.

We can turn this description into the following algorithm:

The iterative algorithm begins by adding the root of the tree to a stack s.
As long as s is not empty, we pop elements from it. We add them to the data structure that represents the solution because we want to process the parent node before its children.
We push the children to s. First the right child and then the left child. This way, we will pop the left one before the right one, which is exactly the order in which we want to process them.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            auto t = s.top(); s.pop();
            sol.push_back(t->val);

            if(t->right)
                s.push(t->right);
            if(t->left)
                s.push(t->left);
        }
        return sol;
    }
};

Complexity

The complexity analysis does not change with respect to the recursive version. We still need to visit the N nodes and do constant work per node. Therefore the time complexity is O(N).

Regarding the space complexity, the stack will have to store at most a number of nodes proportional to the height of the tree, O(H).

Challenge

It is time for you now to generalize this solution to work with a tree of N nodes. You can test your solution here.

3. In-Order Traversal - Recursive

Given the root of a binary tree, return the inorder traversal of its nodes' values.

In-order traversal

Give it a try here.

Solution

In-order traversal is a way to traverse a tree where you first visit the left child, then the root and then the right child. In a binary search tree (like the one above), it will visit the nodes in increasing order.

The recursive solution is straightforward. The only difference with the pre-order recursive solution is the order in which we visit the root and the children. It is a minor change. Go ahead and implement it yourself.

Everything we discussed about the extra if statements applies to this problem, as well as the discussion about stack vs RAM. Here is a solution with the same options A and B as before.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            sol.push_back(n->val);
            helperA(n->right, sol);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);

        sol.push_back(n->val);

        if(n->right)
            helperB(n->right, sol);        
    }
};

Complexity

The complexity analysis is the same as the previous recursive example. We are doing exactly the same, just in a different order.

4. In-Order Traversal - Iterative

Traverse a tree using in-order traversal. No recursion allowed.

Test your solution here.

Solution

I know what you are thinking. You are right. We need a stack.

Let's visualize the in-order traversal of the previous tree.

We call the helper function on the root.
This calls itself on the left child of the root.
This calls itself on the left child of the left child of the root.
This process of moving to the left child repeats until we get to a node k that has no left child. It is only then when we process k that we continue by exploring its right child.
The implicit stack has stored all the nodes between the root and k. Once we are done with k's right child, the next node to process will be extracted from the implicit stack.

We need to mimic this with our stack. Let's call it s.

To kick-off the tree traversal, we add the root of the tree to s.
If the root does not have a left child or we have finished exploring the root's left subtree, we process the root and move to its right child.
Otherwise, this is the case where we keep moving left:
1. We add the root to the stack - to process it later
2. We move to the left

From this algorithm, it looks like we need a stack and a pointer n to mark the node we are currently at. If n becomes null, it means we are done exploring a subtree and need to query the stack for the next node to process. If the stack is empty, we have processed all nodes.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        TreeNode* n = root;
        while(n || !s.empty()) {
            const bool hasToGoRight = !n;
            if(hasToGoRight){
                auto top = s.top(); s.pop();
                sol.push_back(top->val);
                n = top->right;
            } else {
                s.push(n);
                n = n->left;
            }
        }
        return sol;
    }
};

Complexity

The complexity analysis is exactly the same as before: O(N) time complexity and O(H) space complexity.

5. Post-Order Traversal - Recursive

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Check your implementation here.

Solution

In a post-order traversal, we first visit the left child, then the last child and finally the root of the tree, hence the name post-order. This algorithm requires a minimal change with respect to the pre-order and in-order traversals that we have just seen.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            helperA(n->right, sol);
            sol.push_back(n->val);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);        
        sol.push_back(n->val);
    }
};

Complexity

Same as pre-order's and in-order's.

Challenge

Try to generalize this to work with N nodes. Code your solution here.

6. Post-Order Traversal - Iterative

Traverse a binary tree using post-order traversal. No recursion allowed.

Try your solution here.

Solution

If you are thinking that we need a stack again, you are right.

I am familiar with relatively complex solutions based on one stack. This solution can be implemented with two stacks or just one stack and one vector. This can be done with a second stack. The space complexity is still O(N).

If you remember correctly, for iterative pre-order traversal we added the root to the solution and then pushed the left and right child. I know this comes out of nowhere, but let's see what happens if we first push the left child and then the right child.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();

            sol.push_back(top->val);

            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }

        for(auto x : sol)
          cout<<x<<endl;
        return sol;
    }
};

You can verify that we obtain [18, 21, 22, 20, 16], which is the same as reversing the pre-order traversal of this tree: [16, 20, 22, 21, 18]. We only need to add an extra step at the end of the algorithm to reverse the solution - or use two stacks.

I don't have an intuition for this algorithm. I must admit I had to look up this solution on the internet because I did not want to present more complex alternatives.

Above all, it is worth noting is that sometimes it is useful to play with similar problems to try to get a solution to the problem you are trying to solve.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();

            sol.push_back(top->val);

            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }

        reverse(sol.begin(), sol.end());        
        return sol;
    }
};

Complexity

The complexity is linear both in time and space:

Time: we are doing constant work per element. Reversing a vector is also a linear-time operation.
Space: the space complexity is linear, whether we use one or two stacks.

7. Morris Traversal - How to Traverse a Tree Using Constant Space

Traverse a tree using pre-order and in-order traversal. Your space complexity must be O(1) - you cannot use recursion or use any data structures to store information about the nodes.

Solution

You are right. You still need to store some information about the nodes to visit them. This algorithm modifies the nodes to be able to traverse the tree without explicit data structures. At the end of the algorithm, the nodes is back to their original state.

Let's focus on the in-order traversal. Pre-order just needs a minor modification.

We will have two pointers: current and explorer. We will use explorer to move around the tree and build links from some leaves back to current. Current can only move left if we have previously built a link from its predecessor back to current. This is the only thing I have "memorized" about Morris. From this, I can draw a tree and rebuild the algorithm every time.

This image has all the links that we will need to build. However, we do not need to keep any of them: as soon as we are done using a bridge, we destroy it.

The algorithm goes as follows:

First, we set current to root.
If current does not have a left child, we add current to the solution and move to its right child.
Otherwise:
1. We find curren*t's predecessor, using *explorer.
2. If there is already a link between explorer and current, we break it, add current to the solution and move to current's right child.
3. Otherwise, we build a link between explorer and current and move current to its left child.
Go back to 2 until *current* becomes null.

Example

Let's run the algorithm step by step on the tree above:

Current starts at 7.
Using explorer, we find its predecessor, 6, and link it back to current.
We move current to 4.
Using explorer, we find its predecessor, 4, and link it back to current.
We move current to 2.
Current has no left child, so our solution becomes: [2].
We move to current's right, 4.
Using explorer, we find its predecessor, 2.
Since explorer (2) is already linking to current (4), we break this link and add 4 to our solution: [2, 4]
We move current to its right child, 5.
Current has no left child, so we add it to our solution [2, 4, 5] and move to its right child
We are in the same situation as step 9. Our solution becomes [2, 4, 5, 6] and current is back at 7.
Etc.

This is my C++ implementation of this algorithm.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> sol;
        auto current = root;
        while(current){
            if(!current->left) {
                sol.push_back(current->val);
                current = current->right;
            } else {
                TreeNode* explorer = current->left;
              //Find currents predecessor
                while(explorer->right && explorer->right != current) {
                    explorer = explorer->right;
                }

              //Is it linking back to current?
                if(explorer->right == current) {
                    explorer->right = nullptr;
                    sol.push_back(current->val);
                    current = current->right;
                } else {
                    explorer->right = current;
                    current = current->left;
                }
            }
        }
        return sol;
    }
};

The difference between in-order and pre-order is in the last block, where we check if there is an existing link or not. We just need to move around the line in which we add current to the solution.

For pre-order:

//Is it linking back to current?
if(explorer->right == current) {
  explorer->right = nullptr;
  current = current->right;
} else {
  sol.push_back(current->val);
  explorer->right = current;
  current = current->left;
}

Morris post-order traversal is a bit trickier, so I will leave it out of this section.

Complexity

The time complexity is an exercise for you.

The space complexity is O(1). We are implicitly using more since we are modifying the tree, but technically we do not need extra space to execute this algorithm.

Challenge

Can you find some potential issues with this algorithm? For example, if multiple threads had to perform this algorithm on the same tree.

8. Level Order Traversal - Iterative

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For this tree, the solution looks like: [[15], [10, 21], [5, 20, 23], [6]].

Try to solve it here.

Solution

This time I will start with the iterative solution because I find it simpler to code. We can solve this problem by applying BFS. The only trick is how to know when to start a new level. We can do this in two ways:

After we push all the nodes in a level, we introduce a special type of node that indicates that we need a new level - for example, a nullptr.
Before we start processing the queue, we take note of its size s - the elements at that level. We create a new level after we have process s elements.

Here I have taken the second approach.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();
            vector<int> partial;
            while(size-->0){
                auto n = q.front();
                partial.push_back({n->val});
                q.pop();
                if(n->left)
                    q.push({n->left});
                if(n->right)
                    q.push({n->right});
            }
            sol.push_back(partial);
        }
        return sol;
    }
};

Complexity

We visit N nodes and do constant work per node. In other words, the time complexity of this approach is O(N).

The space complexity is the maximum size of the queue. Since we store elements by level, it is a function of the width of the tree.

In the case of a full tree (every node has two children except for the leaves) of height H, the maximum number of nodes in a level will occur at the last level (the leaves), being this 2^H. For this type of tree, H = log2(N).

In conclusion, the space complexity is O(N) too.

Challenge

Try to solve this variant.

9. Level-order Traversal - Recursive

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For this tree, the solution looks like: [[15], [10, 21], [5, 20, 23], [6]].

Try to solve the problem here.

Solution

Always keep in mind the three basic ways to traverse a tree: pre-order, in-order and post-order. This problem is a pre-order tree traversal in disguise.

The only extra is that you want to put nodes that are at the same depth together. This can be easily achieved using a variable to keep track of the current level you are exploring.

Using a hash table, you can store every node you process at the right depth. Since we are exploring the left child first, the relative order of the elements at each level will be preserved.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};

        //Here is where the magic happens
        map<int, vector<int>> levels;
        helper(root, levels);

        //Here we create the solution in the expected data structure
        vector<vector<int>> sol;
        for(auto it = levels.begin(); it != levels.end(); ++it){
          sol.push_back(it->second);
        }
        return sol;
    }

    void helper (TreeNode* n, map<int, vector<int>> &levels, int depth = 0){
        levels[depth].push_back(n->val);

        if(n->left)
            helper(n->left, levels, depth + 1);

        if(n->right)
            helper(n->right, levels, depth + 1);
    }
};

Complexity

We visit N nodes doing constant work per node (adding an element to a hash table has constant amortized time). Therefore, the time complexity is O(N).

This implementation stores all the nodes in a hash table. Consequently, the space complexity is O(N).

10. Level-Order Zigzag Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Tree for levellevel-order zigzag traversal

For this tree, the solution looks like [[8], [14, 4], [2, 5,12,19]].

Give it a try here.

Solution

This problem might seem challenging at first, but you have the tools to solve it. One of the problems above is very similar to this one. I will give you a minute to find it.

You are right. This is a level-order traversal. The only extra is that we have to process some levels from left to right and others from right to left. We can achieve this easily with two stacks, s1 and s2.

Imagine we have completed a level from left to right. The last element we pushed to the stack s1 will be the rightmost element at that level of the tree.

Firstly, we create a new partial solution - the solution for the new level.
We pop the stack s1 and add this element to the partial solution.
The next level will be explored from right to left. Therefore, we add first the left child and the right child to the other stack s2.
We keep processing elements from s1 until it is empty.
In the next iteration, we will process elements from s2 to complete the next level from left to right.
When we process nodes from s2, we first add their right child and then the left child - LIFO for the next level.
We do this until both stacks are empty.

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(root);
        while(!s1.empty() || !s2.empty()){
            vector<int> partial;
            while(!s1.empty()){
                auto top = s1.top();
                partial.emplace_back(top->val);
                s1.pop();
                if(top->left)
                    s2.push(top->left);
                if(top->right)
                    s2.push(top->right);
            }
            if(!partial.empty()){
                sol.push_back(partial);
                partial.clear();
            }
            while(!s2.empty()){
                auto top = s2.top();
                partial.emplace_back(top->val);
                s2.pop();
                if(top->right)
                    s1.push(top->right);
                if(top->left)
                    s1.push(top->left);
            }
            if(!partial.empty()){
                sol.push_back(partial);
            }
        }
        return sol;
    }
};

Complexity

Both the time and space complexity are linear. Can you see why?

Challenges

Here I have several variants of this problem for you to keep practicing:

Zigzag tree traversal II
Generalize to N nodes

11. Side View of a Tree

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

The solution for this tree is [16, 19, 18, 13]. Looking from the right side, you cannot see the other nodes because the nodes in the solution "block their view".

Try coding it here.

Solution

This may look like a challenging problem, but you have the tools you need to solve it. You need to print the rightmost node of each level. Some of the previous problems look very similar o this one.

You can solve this problem by modifying the level-order traversal and printing only the last node at each level.

This is one possible implementation.

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> sol;
        while(!q.empty()){
            int size = q.size();
            for(int i = 1; i <= size; ++i){
                auto top = q.front();
                if(i == size){
                    sol.push_back(top->val);
                }
                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
                q.pop();
            }
        }
        return sol;
    }
};

Complexity

The analysis is the same as the level-order traversal's.

Challenges

Here are two variants you can try:

Solve this problem recursively
Print the left side instead of the right side
Print the leaves

12. Vertical-order traversal - Recursive

Given a binary tree, return the vertical order traversal of its nodes' values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return a list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

The solution for this example is [[4], [6], [12], [21, 14, 23], [20], [24], [25]].

Code your solution here.

Solution

I bet you are already seeing a solution.

Every time you move left or right, you can keep track of your X position. This is easy to implement recursively. Every time you move to the left node, the X position decreases by 1. If you move to the right, the X position increases by 1.

Using a hash table, you can store all the nodes at a certain X position to build the solution.

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root)
        return {};

        map<int, vector<pair<int, int>>> distances;
        helper(root, 0, 0, distances);

        vector<vector<int>> sol;
        for(auto x : distances){
          //Using a lambda function to ensure nodes appear in the expected order
            sort(x.second.begin(),
                 x.second.end(), 
                 [] (pair<int,int> &a, pair<int,int> &b) {
                    if(a.first==b.first)
                        return a.second<b.second;
                    else
                        return a.first<b.first;
                    }
                );
            vector<int> v;
            for(auto y : x.second){
                v.push_back(y.second);
            }
            sol.push_back(v);
        }
        return sol;
    }

  void helper(TreeNode* root, int hd, int c, map<int,vector<pair<int,int>>> &distances){
        if(!root)
            return;
        distances[hd].push_back({c, root->val});

        helper(root->left, hd-1, c+1, distances);
        helper(root->right, hd+1, c+1, distances);
    }
};

Complexity

We visit every node once and do constant work per node. However, at the last step where we need to order the nodes at each level. This brings the complexity up. It is not trivial to calculate this new complexity but it is clearly bounded by O(NLogN).

Since we store all nodes in a hash table, the space complexity is O(N).

13. Vertical-order traversal - Iterative

Given a binary tree, return the vertical order traversal of its nodes' values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

The solution for this example is [[4], [6], [12], [21, 14, 23], [20], [24], [25]].

Test your solution here.

Solution

Based on my explanation for the previous problem and your understanding of BFS, you will be able to write the iterative version of the algorithm that solves the problem.

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int,int>>> distances;
        queue<pair<TreeNode*, int>> q;
        int level = 0;
        q.push({root, 0});
        distances[0].push_back({level, root->val});

        while(!q.empty()) {
            const int size = q.size();
            level++;
            for(int i = 0; i < size; i++) {
                auto node = q.front().first;
                int sd = q.front().second; q.pop();

                if(node->left) {
                    distances[sd-1].push_back({level, node->left->val});
                    q.push({node->left,sd-1});
                }

                if(node->right) {
                    distances[sd+1].push_back({level, node->right->val});
                    q.push({node->right,sd+1});
                }
            }
        }

        vector<vector<int>> sol;
        for(auto it : distances) {
            vector<int> partial;
            sort(it.second.begin(), it.second.end());

            for(int i= 0; i < it.second.size(); i++) {
                partial.push_back(it.second[i].second);
            }
            sol.push_back(partial);
        }

        return sol;
    }
};

Complexity

I will leave this as an exercise for you. If you need hints, check the previous problems.

Conclusions

This was supposed to be an article on how to traverse a tree. It ended up being an excuse to work on recursive and iterative solutions to the same problem. We can extract a few learnings from this:

In general, it is not trivial to translate a recursive algorithm into an iterative. However, this is trivial for tail-recursive functions.
Recursive solutions can lead to stack overflow. Always consider iterative solutions (limited by RAM size).
Some problems have straightforward recursive solutions and complicated iterative implementations.
Recursive solutions tend to be slower because of the stack calls. However, your focus should be on having a working code that is maintainable and readable. Only optimize after using a profiler and finding the real bottlenecks

As I have said before, it is not about solving a million problems or spending a million hours. What is important is what you get out of each hour. We have also seen that from a seemingly simple problem we have been able to extract a lot.

“No problem is too small or too trivial if we can really do something about it.”

Richard Feynman

The aim of this entry is to make you think about each problem. We have seen 13 ways to traverse a tree. We have work on recursive and iterative implementations. You have become smarter by going through this article. As the next logical step, I invite you to read my article on dynamic programming.

If you found this article helpful, please share it. Chances are more people will find it useful too. You can help someone pass their exams, a job interview, or get them unblocked at work.

Feel free to have a look at my blog www.yourdevopsguy.com and connect with me on Twitter.

What is the difference between a junior and a senior software developer? 15 things I wish I had known sooner

Your DevOps Guy — Sun, 13 Sep 2020 06:26:00 +0000

This article was originally published in my blog www.yourdevopsguy.com.

What is the difference between a junior and a senior developer?

When I first started coding I also felt lost and overwhelmed. I thought I needed to focus only on my coding skills to get promoted to senior. Over time, I realized the difference between a junior and a senior developer.

Senior software engineers design solutions to complex, open-ended problems, with no guidance. They gather requirements, design solutions, tasks, code, deploy and maintain the system. They care about the system's performance, security, testing, extensibility, scaling, instrumentation, and maintainability.

This is something I later learned as part of a training session at Amazon on how to move to the next level. They expect seniors to figure out how to solve problems on their own, while juniors need guidance. This does not mean they know everything. This includes knowing when and how to ask questions, which takes experience. Senior engineers take tasks that no one else wants to do and that cannot be solved with a simple Google search.

Do not equate years of experience with wisdom. There are people with 10 years of experience and people who have experienced the same year ten times. I recommend never getting too comfortable with what you are doing to keep growing.

This is a list of tips I wrote during my first year as a software developer. They come mostly from making mistakes and observing team leaders and principal engineers.

15 things I wish I had known sooner

How to work more efficiently

1. For every task you work on have a clear definition of done

This helps with planning, keeps you focused on what you need to do, and makes it easier to document your work. Even for open-ended tasks, there should be a clear goal: for instance, a decision to use technology A or B.

2. Define the scope

Make sure the scope of the task is well defined too. Do not waste time on things out of your or your team's scope.

3. Time estimates are hard

I have usually overlooked at the time I needed to:

Design and choose a solution.
Change or add new tests.
Get my colleagues to approve my pull request.

4. Mindset

Have a look at the Amazon Leadership principles. They provide a good mindset for your transition to a senior level, especially:

Ownership
Bias for action
Dive deep
Earn trust
Disagree and commit

Sometimes principles may contradict, so take make a decision based on your situation. A senior developer does not just write code but is a leader that takes impactful decisions.

How to optimize your work

5. Automate

Automate as much as you can. It is obvious that you gain a lot of time in the medium and long term, but this has to do with the number of iterations, not time. You need to have a rule to decide when to automate a task. Personally, if I find myself doing twice something that I can automate, it is time to write a script.

6. Work incrementally

Do not write 1000 lines of code before you start testing it. Work and verify your changes incrementally. Check if the code can compile, or you forgot to import a library (good IDEs with this). Doing things right from the start is easier than redoing sloppy work. From the outset, write readable code, unit tests, do small refactors, etc.

7. Premature optimization is the root of all evil

Avoid premature optimization. This is not the same as not using the most appropriate data structures and algorithms from the beginning. Your focus should be to write code that works and later make it efficient. Write code, use a profiler to find the real bottlenecks and focus on optimizing them.

8. Get a rubber duck

Before you ask for help, get a rubber duck. It can be a virtual one. Before you ask for help, explain the problem to your rubber duck and how you are trying to solve it. Go through your code line-by-line. Chances are you will find the solution. If not, you will be able to better articulate your question to your colleague.

9. Revise your assumptions

When things go wrong, check your assumptions. I wasted long hours debugging issues that came from:

reading the wrong configuration file
using outdated information from an internal wiki page
problems with someone else's code
copy-paste related errors

Logging and quick chats can speed things up.

10. Read the documentation

I have also avoided reading the documentation out of pure laziness. If your team's documentation is unclear or lacks information, improve it.

11. Beware of comments

"Code never lies, comments sometimes do." — Ron Jeffries

The best comment is the one you don't have to write. Comments, like code, can rot and be misleading. If you are going to write a comment, make sure it is the best comment you can write

Do not state the obvious
Be brief and precise
Check your grammar and punctuation
Remove comments that produce noise

12. Learn to communicate

Coding has more human interaction that people think. You need to interact with people to define tasks and ask questions. Also, when you read and write documentation and comments.

Consider clear and effective communication as part of your job requirements.

How to approach complex, open-ended tasks

13. Ask questions

It is key to clarify the problem before you start working on it. Some of the following questions can help you gather better requirements:

What are the inputs your system expects?
What is an invalid input and what to do when you receive one?
What output do you need to produce?
What is our service level agreement (SLA)?
How many users do we expect?
How many requests per second?
Do we need to deal with internationalization?
Do we need strong consistency in our database or is eventual consistency enough?

Sometimes you will not have all the information you need to start solving the problem. Chances are no one will and it is your responsibility to figure it all out. The moment you start taking this type of task you will know you are operating at a senior level.

14. Design on paper first

Use pen and paper or a whiteboard to sketch a solution before you start coding. Unless you are solving a trivial problem, try to come up with different alternatives. Then, try to break your own design. Ask yourself questions like:

Where can the system break?
What are the bottlenecks?
Are we relying on third parties? What happens when something goes wrong on their end?
Can we use a cache to improve performance?
- What is an appropriate TTL?
- What is the worst thing that can happen if we temporarily serve stale content?
How can we log and monitor the system?

Document your choices, the rationale behind them, and potential risks.

Bonus tip

I think I read this somewhere in an internal wiki page, but it helped me see where I was falling short.

15. Do not be a one-trick pony

If you only know how to do only one thing, it is likely that you have gaps in other areas. Learn other programming languages. Create some machine learning prototypes, even if you are an Android developer. If you are a front-end developer, learn about backend or dive into the internals of Linux.

You don't need to become an expert, but you will an appreciation of how the different pieces fit together. You may learn a thing or two from other areas that you can apply in your career. You may find that you love something new you had never tried and change careers!

PS: I hope you found this useful. If so, like and share this article, visit my blog www.yourdevopsguy.com, and let's connect on Twitter.

How to learn data structures and algorithms. 20 problem-solving techniques you must know

Your DevOps Guy — Thu, 03 Sep 2020 16:28:00 +0000

This article was originally published in my blog www.yourdevopsguy.com.

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 (not memorize) any algorithm or data structure, with 2 examples.

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.

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.

Pointer based techniques

1. Two Pointers

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:

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 a is sorted, we know that:

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 i in [0, a.size() - 1) => a[i + 1] >= a[i]

With this, we can design the following algorithm:

We keep 2 pointers: l, starting at the first element of the array, and r starting at to the last.
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 l+1); if it is larger than the target, we decrease r by one (to change our largest operand for another one equal or smaller at 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:

vector<int> twoSum(const vector<int>& a, int target) {
        int l = 0, r = a.size() - 1;
        vector<int> sol;
        while(l < r) {
            const int sum = a[l] + a[r];
            if(target == sum){
                sol.push_back(l + 1); 
                sol.push_back(r + 1); 
                break;
            } else if (target > sum) {
                ++l;
            } else {
                --r;
            }
        }
        return sol;
    }

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: 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.

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 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?

You will need one pointer to iterate through the array, i.
And a second pointer, n, one to define the area that contains no duplicates: [0,n].

The logic is as follows. If the values of the elements at index i (except i = 0) and i-1 are:

The same, we don’t do anything - this duplicate will be overwritten by the next unique element in a.
Different: we add a[i] to the section of the array that contains no duplicates - delimited by n, and increment n by one.

int removeDuplicates(vector<int>& nums) {
    if(nums.empty())
        return 0;
    int n = 0;
    for(int i = 0; i < nums.size(); ++i){
        if(i == 0 || nums[i] != nums[i - 1]){
            nums[n++] = nums[i];
        }
    }
    return n;
    }

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.

void sortColors(vector<int>& nums) {
    int smaller = 0, eq = 0, larger = nums.size() - 1;
    while(eq <= larger){
        if(nums[eq] == 0){
            swap(nums[smaller], nums[eq]);
            ++smaller; ++eq;
        } else if (nums[eq] == 2) {
            swap(nums[larger], nums[eq]);
            --larger;
        } else {
            eq++;
        }
    }
}

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.

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 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'.

2. Pointers moving at different speeds

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:

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, 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.

ListNode* middleNode(ListNode* head) {
       ListNode* slow = head;
       ListNode* fast = head;

       while (fast != nullptr && fast->next != nullptr) {
           slow = slow->next;
           fast = fast->next->next;
       }
       return slow; 
    }

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 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?

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:

bool hasCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(!fast)
                break;
            fast = fast->next;
            if(slow == fast)
                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.

int findDuplicate(const vector<int>& nums) {
    int slow = nums[0], fast = slow; 
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);

    slow = nums[0];
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];            
    }

    return slow;
}

Challenges

Here are more problems that can be solved using this technique:

3. Sliding Window

The sliding window technique eases the task of finding optimal chunks of contiguous data that meet a certain condition:

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, 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 res

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

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:

Two pointers, l and r, to define our substring s.
A variable, sol, to store the length of the longest substring we have seen so far.
A way of keeping track of the characters that form s: a set, seen, will be perfect for this.

While iterating through the string:

If the current character is in seen*you have to increment *l to start removing elements from the beginning of our s.
Otherwise, add the character to seen, move r forward and update sol.

int lengthOfLongestSubstring(const string& s) {
    int sol = 0;
    int l = 0, r = 0;
    unordered_set<int> seen;
    while(r < s.size()) {
        const auto find = seen.find(s[r]);
        if(find == seen.end()) {
            sol = max (sol, r - l + 1);
            seen.insert(s[r]);
            ++r;
        } else {
            seen.erase(s[l++]);
        }
    }
    return sol;
}

Challenges

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.

Recursion based techniques

4. Dynamic Programming

I already published an 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 backtracks to a previous state and tries the next candidate.

Backtracking problems present you with a list of choices:

Should you place this piece in this position?
Should you add this number to the set?
Should you try this number in this position next?
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:

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:

If you need all solutions, the helper function returns nothing (void) to avoid stopping when we find the first solution.
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..", // Solution 1 "...Q", "Q...", "..Q."],

["..Q.", // Solution 2
"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 isViableSolution function for now. Try to see the recipe I gave (slightly modified) you in action.

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;

        /** 

        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> board(n, string(n, '.'));

        solveBoard(solutions, board, 0, n);   

        return solutions;
    }

    void solveBoard(vector<vector<string>>& solutions, vector<string>& board, int col, int n){
        if(col == n){
            solutions.push_back(board);
            return;
        }

        for(int row = 0; row < n; row++){
            if(isViableSolution(board, row, col)){                
                board[row][col] = 'Q';
                solveBoard(solutions, board, col + 1, n);
                //Backtracking - we bring our board to the previous state
                board[row][col] = '.';  
            }
        }        
    }

    bool isViableSolution(vector<string>& board, int row, int col){
        int n = board.size(); 

        for(int x = 1; x <= col; x++){
            if(board[row][col-x] == 'Q')
                return false;
        }

        for(int x = 1; row - x >= 0 && col >= x; x++){
            if(board[row-x][col-x] == 'Q') 
                return false;
        }

        for(int x = 1; row + x < n && col >= x; x++){
            if(board[row+x][col-x] == '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.

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++:

vector<string> letterCombinations(const string &digits) {
    if(digits.empty())
        return {};
    const vector<string> letters {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> sol;
    string candidate (digits.size(), ' ');
    h(sol, 0, candidate, letters, digits);
    return sol;
}

void h(vector<string> &sol, int idx, string &candidate, const vector<string> &letters, const string &digits){
    if(idx == digits.size()){
        sol.push_back(candidate);
        return;
    }

    for(const char &c : letters[digits[idx] - '0']) {
        candidate[idx] = c;
        h(sol, idx + 1, candidate, letters, digits);            
    }
}

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:

string candidate; //instead of string candidate (digits.size(), ' ');
…
for(const char &c : letters[digits[idx] - '0']) {
    candidate.push_back(c);
    h(sol, idx + 1, candidate, letters, digits);            
    candidate.pop_back();
}

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 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.

void solveSudoku(vector<vector<char>>& board){
        helper(board);
    }

    bool helper(vector<vector<char>>& board, int row = 0, int col = 0) {
        if(col == size){
           col = 0;
           ++row;
            if(row == size){
                return true;
            }
        }

        if(board[row][col] != '.'){
            return helper(board, row, col + 1);
        }

        for(char i = '1'; i <= '9'; ++i){
            if(isViableSolution(board, row, col, i)){
                board[row][col] = i;
                if (helper(board, row, col + 1))
                    return true;
            }
        }
        board[row][col] = '.';
        return false;
    }

    bool isViableSolution(const vector<vector<char>>& board, int row, int col, char c){
        for(const auto& n : board[row]){
            if(n == c)
                return false;
        }

        for(int r = 0; r < size; ++r){
            if(board[r][col] == c)
                return false;
        }

        const int br = row / nsize;
        const int bc = col / nsize;

        for(int i = 0; i < nsize ; ++i){
            for(int j = 0; j < nsize; ++j){
                if(c == board[3 * br + i][3 * bc + j])
                    return false;
            }
        }

        return true;
    }

Challenges

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 i, you need to generate two solutions:

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.

vector<vector<int>> subsets(const vector<int>& nums) {
        vector<vector<int>> sol;
        vector<int> partial;
        h(sol, partial, nums);
        return sol;
    }
    void h(vector<vector<int>>& sol, vector<int>& partial, const vector<int>& nums, int idx = 0){
        sol.push_back(partial);
        if(idx == nums.size()){
            return;
        }

        for(int i = idx; i < nums.size(); ++i){
            partial.push_back(nums[i]);
            h(sol, partial, nums, i + 1);
            partial.pop_back();
        }        
    }

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

vector<vector<int>> subsetsWithDup(vector<int> nums) {
        vector<vector<int>> sol;
        vector<int> partial;
        sort(nums.begin(), nums.end());
        h(sol, partial, nums);
        return sol;
    }
    void h(vector<vector<int>>& sol, vector<int>& partial, const vector<int>& nums, int idx = 0){
        sol.push_back(partial);
        if(idx == nums.size()){
            return;
        }

        for(int i = idx; i < nums.size(); ++i){
            if(i != idx && nums[i] == nums[i - 1])
                continue;
            partial.push_back(nums[i]);
            h(sol, partial, nums, i + 1);
            partial.pop_back();
        }        
    }

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.

vector<vector<int>> permute(const vector<int>& nums) {
        vector<vector<int>> sol;
        vector<int> p (nums);
        h(nums, sol, p);
        return sol;
    }
    void h(const vector<int> &nums, vector<vector<int>> &sol, vector<int> &p, int idx = 0){
        if(idx == nums.size()){
            sol.push_back(p);
            return;
        }
        for(int i = idx; i < nums.size(); ++i){
            swap(p[idx], p[i]);
            h(nums, sol, p, idx + 1);
            swap(p[idx], p[i]);
        }
    }

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.

void helper(vector<vector<int>>& res, int pos, vector<int>& nums) {
        if(pos == nums.size()) {
            res.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); ++i) {
            if(i != pos && nums[i] == nums[pos])
                continue;
            swap(nums[i], nums[pos]);
            helper(res, pos + 1, nums);
        }
        rotate(nums.begin() + pos, nums.begin() + pos + 1, nums.end());
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if(nums.empty())
            return {};

        sort(nums.begin(), nums.end());

        vector<vector<int>> sol;
        helper(sol, 0, nums);

        return sol;
    }

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:

Sorting and searching

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:

Can I sort the input?. For example, sometimes you have to return indices, therefore sorting is not an option
How would this problem change if the elements were sorted?
How does sorting affect the overall complexity?. The best sorting algorithms have a complexity of O(n log n) - sorting integers can be done in O(n)

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 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).

bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;

        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return  s == t;
}

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, l for A and r for B, starting at index 0 in each array.

A[l] = 1
B[r] = 2

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:

If they are the same, we include them to the array representing the intersection of both arrays and advance both pointers
If they are different, we move the pointer pointing to the smallest of the two elements.

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> sol;
        int i = 0, j = 0;
        while( i < nums1.size() && j < nums2.size()) {
            if(nums1[i] == nums2[j]) {
                sol.push_back(nums1[i]);
                ++i;
                ++j;
            } else if(nums1[i] > nums2[j]) {
                ++j;
            } else {
                ++i;
            }
        }
        return sol;
    }

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

K closest points to origin. In another section, I will present a different solution, slightly faster.
Largest number

8. Intervals

Most interval related problems I have seen boil down to:

Modeling the interval as an array of two elements, a pair/tuple or a custom class (this is the cleanest option)
Sorting the input
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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& i1, const auto& i2){
           return i1[0] < i2[0];
        });
        int i = 0;
        vector<vector<int>> sol;
        vector<int> curr(2);
        while(i < intervals.size()){
            curr = intervals[i++];
            while(i < intervals.size() && intervals[i][0] <= curr[1]){
                curr[1] = max(curr[1], intervals[i][1]);
                ++i;
            }
            sol.push_back(curr);
        }
        return sol;
    }

Interval list intersections

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.

Solution

vector<vector<int>> intervalIntersection(const vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> sol;
    int i = 0, j = 0;

    while(i < A.size() && j < B.size()){
        const int lo = max(A[i][0], B[j][0]);
        const int hi = min(A[i][1], B[j][1]);
        if(lo <= hi){
            sol.push_back({lo, hi});
        }
        if(A[i][1] < B[j][1])
            ++i;
        else
            ++j;
    }
    return sol;
}

9. Variations on binary search

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.

template<typename T>
int binary_search(const vector<T>& v, int k) {
    int l = 0, r = v.size() - 1;
    while(l<=r) {
     const int m = l + (r - l) / 2;
     if(k == v[m]) {
         return m;
     } else if (k > v[m]) {
         l = m + 1;
     } else {
         r = m - 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 1:

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 x is 0 or 1, its square root is x. 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,…]

With this, we can search in [2, x/2] and speed things up a bit.

int mySqrt(int x) {
        if(x == 0 || x == 1)
            return x;
        int sol = 1;
        int l = 2, r = x / 2;
        while(l <= r){
            const long m = l + (r - l) / 2;
            if(m * m == x)
                return m;
            else if(m * m > x){
                r = m - 1;
            } else {
                sol = m;
                l = m + 1;
            }
        }
        return sol;
    }

Challenges

Have fun!

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 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.

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.

Note:

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 words
Edges 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.

int ladderLength(const string &beginWord, const string &endWord, const vector<string>& wordList) {
        if(beginWord == endWord)
            return 1;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        dict.erase(beginWord);
        int ladder = 1;
        while (!todo.empty()) {
            ladder++;
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                string word = todo.front();
                todo.pop();
                for (int j = 0; j < word.size(); j++) {
                    char c = word[j];
                    for (int k = 0; k < 26; k++) {
                        word[j] = 'a' + k;
                        if (dict.find(word) != dict.end()) {
                            if (word == endWord) {
                                return ladder;
                            }
                            todo.push(word);
                            dict.erase(word);
                        }
                     }
                    word[j] = c;
                }
            }
        }
        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.

vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> partial;
        while(!q.empty()){
            int size = q.size();
            while(size-->0){
                auto n = q.front();
                partial.push_back({n->val});
                q.pop();
                if(n->left)
                    q.push({n->left});
                if(n->right)
                    q.push({n->right});
            }
            sol.push_back(partial);
            partial.clear();
        }
        return sol;
    }

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:

Web crawler using BFS to explore all the links on a website.
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 matrix
For every 1 you find, increase the counter and sink the island

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.

int numIslands(vector<vector<char>>& grid) {
        int numIslands = 0;
        for(int r = 0; r < grid.size(); ++r){
            for(int c = 0; c < grid[0].size(); ++c){
                if(grid[r][c] == '1'){
                    ++numIslands;
                    sinkIslands(grid, r, c);
                }
            }
        }
        return numIslands;
    }

    const vector<vector<int>> dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    void sinkIslands(vector<vector<char>> &m, int r, int c){
        m[r][c] = '0';
        for(const auto &d : dirs){
            const int nr = r + d[0];
            const int nc = c + d[1];
            if(isValid(m, nr, nc)){
                sinkIslands(m, nr, nc);
            }
        }
    }

    bool isValid(vector<vector<char>> &m, int r, int c){
        return r >= 0 && r < m.size() && c >= 0 && c < m[0].size() && m[r][c] == '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.

bool isSymmetric(TreeNode* root) {
        if(!root)        
            return true;
        return helper(root->left, root->right);
    }
    bool helper(TreeNode* p, TreeNode* q){
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;
        return p->val == q->val && iS(p->left, q->right) && iS(p->right, q->left);
    }

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:

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 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.

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses, vector<int>(0));

        for(const auto &p : prerequisites){
            int u = p[0];
            int v = p[1];
            adj[u].push_back(v);
        }

        vector<bool> white(numCourses, true),
                     grey(numCourses), 
                     black(numCourses);
        vector<int> sol (0);        
        for(int i = 0; i < numCourses; ++i){
            if(white[i] && hasCycle(adj, i, white, grey, black, sol)){
                return {};
            }
        }
        return sol;
}

    bool hasCycle(const vector<vector<int>>& adj, int i, vector<bool> &white, vector<bool> &grey, vector<bool> &black, vector<int>& sol){
        //We have started exploring this node
        white[i] = false;
        grey[i] = true;

        for(const auto & n : adj[i]){
            if(black[i])
                continue;
            if(grey[n] || hasCycle(adj, n, white, grey, black, sol))
                return true;
        }

        grey[i] = false;
        black[i] = true;
        sol.push_back(i);
        return false;
    }

Challenges

Here you can find a few more problems to practice.

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 both ends of the queue.

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 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.

Remove elements in the dequeue which are outside of the current sliding window (one per iteration)
Remove all elements in the dequeue which are smaller than the current element we are at since they cannot represent the max of that sliding window
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.

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    vector<int> sol;

    deque<int> dq;
    for (int i=0; i<nums.size(); i++) {
        // Step 1
        if (!dq.empty() && dq.front() == i-k) 
            dq.pop_front();

        // Step 2
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        // Step 3
        dq.push_back(i);

        // Step 4
        if (i >= k-1) 
            sol.push_back(nums[dq.front()]);
    }
    return sol;
}

Challenge

Design your own circular dequeue, to fully grasp the internals of this data structure.

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 word
A data structure to store pointers to the node’s children: a hash table, an array of characters, etc.

class Trie {
private:
    struct Node{
        bool isWord;
        unordered_map<int, Node*> children;
        Node() : isWord(false) {}
    };

    Node* findNode(const string &word){
        Node* curr = root;
        for(int i = 0; i < word.size() && curr; ++i)
            curr = curr->children[word[i] - 'a'];
        return curr;
    }

public:
    Node* root;
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(const string &word) {
        Node * curr = root;
        for(int i = 0; i < word.size(); ++i){
            const char c = word[i] - 'a';
            if(!curr->children[c]){
                Node* newChild = new Node();
                curr->children[c] = newChild;
            } 
                curr = curr->children[c];
        }
        curr->isWord = true;
    }

    /** Returns true if the word is in the trie. */
    bool search(const string &word) {
        Node* curr = findNode(word);
        return curr ? curr->isWord : false;
    }

    /** Returns true if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string &prefix) {
        Node* curr = findNode(prefix);
        return curr ? 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 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.

const vector<vector<int>> dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    struct Trie{
        struct Node{
            bool isWord;
            unordered_map<char, Node*> children;
            Node() : isWord(false){}
        };

        Node* root;

        Trie(){root = new Node();}

        void insert (const string& w){
            Node* cur = root;
            for(const auto &c : w){
                if(cur->children.find(c) == cur->children.end()){
                    cur->children[c] = new Node();
                }
                cur = cur->children[c];
            }
            cur->isWord = true;
        }

        bool hasPrefix(const string &prefix){
            Node* cur = root;
            for(const auto &c : prefix){
                if(cur->children.find(c) == cur->children.end()){
                    return false;
                }
                cur = cur->children[c];
            }
            lastNode = cur;
            return cur != nullptr;
        }

        bool isValidWord(const string &w){
            if(lastNode){
                bool res = lastNode->isWord;
                return res;
            }
            Node* cur = root;
            for(const auto &c : w){
                cur = cur->children[c];
                if(!cur){
                    return false;
                }
            }
            lastNode = cur;
            return lastNode->isWord;
        }

        void deleteWord(){
            lastNode->isWord = false;
            lastNode = nullptr;
        }
        Node* lastNode;
    };    

    Trie t;
public:
    vector<string> findWords(vector<vector<char>>& board, const vector<string>& words) {
        for(const auto& w : words)
            t.insert(w);

        vector<string> sol;
        for(int row = 0; row < board.size(); ++row){
            for(int col = 0; col < board[0].size(); ++col){
                string candidate (1, board[row][col]);
                if(t.hasPrefix(candidate))
                    addWords(board, row, col, sol, candidate);
            }
        }
        return sol;
    }

    void addWords(vector<vector<char>> &board, int row, int col, vector<string> &sol, string &candidate){
        if(t.isValidWord(candidate)){
            sol.push_back(candidate);
            t.deleteWord();
        }

        const char old = board[row][col];
        board[row][col] = '-';
        for(const auto &d : dirs){
            const int nrow = row + d[0];
            const int ncol = col + d[1];
            if(nrow >= 0 && nrow < board.size() 
                && ncol >= 0 && ncol < board[0].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;
    }

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

class MedianFinder {
    priority_queue<int, vector<int>, less<int>> L;
    priority_queue<int, vector<int>, greater<int>> H;    
public:

    MedianFinder() { }

    void addNum(int x) {
        if(L.empty() == false && x > L.top()) {
            H.emplace(x);
        } else {
            L.emplace(x);
        }

        if(H.size() > L.size() + 1) {
            L.emplace(H.top());
            H.pop();
        } else if(L.size() > H.size() + 1) {
            H.emplace(L.top());
            L.pop();
        }
    }

    double findMedian() {
        if(H.size() == L.size()) {
            return (H.top() + L.top()) * 0.5;
        } else {
            return H.size() > L.size() ? H.top() : L.top();
        }
    }

};

Challenges

In increasing order of difficulty:

Miscellanea

16. Bit manipulation

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.

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 zeroes and the missing number will be XORed with 0 (resulting in itself), solving our problem.

int missingNumber(const vector<int>& nums) {
        int res = nums.size();
        for(int i = 0; i < nums.size(); ++i)
            res ^= (i ^ nums[i]);
        return res;
    }

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.

bool isPowerOfTwo(int n) {
        return n > 0 ? (n & (n - 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).

int hammingWeight(uint32_t n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;  
    }

Challenges

These are for you to practice the previous techniques:

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 top as:

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 somehow return the k most common elements.

For this last part, you either:

Put all the elements with its frequencies in an array and sort it

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.

vector<string> topKFrequent(const vector<string>& words, int k) {
        map<string, int> freq;
        for(const auto &w : words)
            freq[w]++;

        auto l = [](const pair<int, string> & p1, const pair<int, string> &p2){
            if(p1.first == p2.first)
                return p1.second < p2.second;
            else
                return p1.first > p2.first;
        };
        priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(l)> pq(l);

        for(auto it = freq.begin(); it != freq.end(); ++it){
            if(pq.size() < k){
                pq.push({it->second, it->first});
            } else {
                auto top = pq.top();
                if(top.first < it->second){
                    pq.pop();
                    pq.push({it->second, it->first});
                }
            }
        }
        vector<string> sol (k);
        while(!pq.empty()){
            sol[--k] = pq.top().second;
            pq.pop();
        }
        return sol;
    }

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 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.

typedef pair<int, vector<int>> pivi;
public:
    vector<vector<int>> kClosest(const vector<vector<int>>& points, int K) {

        auto l = [] (const pivi& p1, const pivi &p2) {
            return p1.first < p2.first;
        };

        priority_queue<pivi, vector<pivi>, decltype(l)> pq(l);

        for(const auto &p : points){
            //Avoid taking the square root. Won’t change the result and it’s faster
            const int d = p[0] * p[0] + p[1] * p[1];

            if(pq.size() < K)
                pq.push({d, {p[0], p[1]}});
            else if(pq.top().first > d){
                pq.pop();
                pq.push({d, {p[0], p[1]}});
            }
        }

        vector<vector<int>> sol;

        for(int i = 1; i <= K; ++i){
            sol.push_back(pq.top().second);
            pq.pop();
        }
        return sol;
    }

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->4Output: 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.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dh(1), *curr = &dh;
    while(l1 && l2){
        if(l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    if(l1){
        curr->next = l1;
    } else if(l2) {
        curr->next = l2;
    }

    return dh.next;
}

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.

ListNode* mergeKLists(vector<ListNode*>& lists) {
    typedef pair<ListNode*, int> pni;

    auto comp = [](const pni & p1, const pni& p2) { 
        return p1.first->val > p2.first->val; 
    };

    priority_queue<pni, vector<pni>, decltype(comp)> pq (comp);

    for(int i = 0; i < lists.size(); ++i){
        if(lists[i]){
            pq.push({lists[i], i});
            lists[i] = lists[i]->next;
        }
    }

    ListNode dh(-1), *curr = &dh;

    while(!pq.empty()){
        const auto p = pq.top(); pq.pop();

        curr->next = p.first;
        curr = curr->next;

        ListNode* next = lists[p.second];
        if(next){
            int idx = p.second;
            pq.push({next, idx});
            lists[p.second] = lists[p.second]->next;
        }
    }
    return dh.next;
}

19. Rolling hash

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:

This is an improvement over the brute force method, where you compare s and every candidate substring, c, which is inefficient.
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 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).

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.

 int strStr(const string& haystack, const string& needle) {
    int nsize = needle.size();

    if(nsize == 0) 
        return 0;

    int hsize = haystack.size();
    if(nsize > hsize)
        return -1;

    int msbPower = 1;       
    int nhash = 0; 
    int hhash = 0;

    const int mod = 10000009; //A big prime number

    for(int i=0; i<nsize; i++) {
        if(i != 0) {
            msbPower *= 26;
            msbPower %= mod;
        }
        nhash = nhash*26+needle[i];
        nhash %= mod;
        hhash = hhash*26+haystack[i];
        hhash %= mod;
    }

    if(nhash == hhash && haystack.compare(0, nsize, needle) == 0) 
        return 0;

    for(int i=1; i<=hsize-nsize; i++) {
        hhash -= haystack[i-1]*msbPower; 
        hhash %= mod;
        if(hhash < 0)
            hhash += mod;
        hhash = hhash*26+haystack[i+nsize-1];
        hhash %= mod;
        if(nhash == hhash && haystack.compare(i, nsize, needle) == 0) 
            return i;
    }
    return -1;
}

20. How to learn new algorithms and data structures

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.

Example 1: Binary search

Binary search is an improvement over a linear search for sorted arrays. It reduces the size of the array in half at every step, achieving a complexity of O(logN) instead of N.
Two points: a)Since the array is sorted, comparing our target to the middle element of the array lets us discard half of the array at every step (the half containing elements that are too large or too small compared to the target. b)If the pointers cross, this is l > r, there is no solution. 3.

template<typename T>
int binary_search(const vector<T>& v, int k) {
    int l = 0, r = v.size() - 1;
    while(l<=r) {
     const int m = l + (r - l) / 2;
     if(k == v[m]) {
         return m;
     } else if (k > v[m]) {
         l = m + 1;
     } else {
         r = m - 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 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...

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 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.

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 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.

Putting it all together

You can try to implement it in your favorite language here.

class Solution {
private:
    Node *constructHelper(vector<vector<int>> &grid, int len, int x, int y) {
        int flag = grid[x][y];
        for (int i = x; i < x + len; i++)
            for (int j = y; j < y + len; j++)
                //if not a leaf, go deeper
                if (flag != grid[i][j])
                {
                    Node *tl = constructHelper(grid, len / 2, x, y);
                    Node *tr = constructHelper(grid, len / 2, x, y + len / 2);
                    Node *bl = constructHelper(grid, len / 2, x + len / 2, y);
                    Node *br = constructHelper(grid, len / 2, x + len / 2, y + len / 2);
                    return new Node(true, false, tl, tr, bl, br);
                }
        return new Node(grid[x][y] == 1, true, nullptr, nullptr, nullptr, nullptr);
    }

public:
    Node *construct(vector<vector<int>> &grid) {
        int n = grid.size();
        return (n == 0) ? nullptr : constructHelper(grid, n, 0, 0);
    }
};

If you want to learn more about this data structure, I recommend these two to see a quadtree in action.

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.

Disjoin sets. Very handy to solve many problems and easy to implement using arrays or tree-like structures.
Shortest path algorithms. Dijktra’s algorithm, and at least knowing that there is a “heuristically-optimized version” A*. Also Bellman-Ford and Floyd-Warshall.
Minimum spanning trees. What they are and how to compute them. These two are the most common algorithms: Kruskal’s (essentially, sorting edges and computing connected components, which can easily be done using disjoint sets) and Prim’s (very similar to Dijkstra's shortest path algorithm).
Balanced trees. There are many types, but knowing red-black trees is enough.

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.

PS: I hope you found this useful. If so, like and share this article, visit my blog www.yourdevopsguy.com, and let's connect on Twitter.

All you need to know about Dynamic Programming

Your DevOps Guy — Wed, 12 Aug 2020 10:18:10 +0000

This article was originally published in my blog www.yourdevopsguy.com.

What is dynamic programming and why should you care about it?

In this article, I will introduce the concept of dynamic programming, developed by Richard Bellman in the 1950s, a powerful algorithm design technique to solve problems by breaking them down into smaller problems, storing their solutions, and combining these to get to the solution of the original problem.

The hardest problems asked in FAANG coding interviews usually fall under this category. It is likely that you will get tasked with solving one during your interviews, hence the importance of knowing this technique. I will explain what dynamic programming is, give you a recipe to tackle dynamic programming problems, and will take you through a few examples so that you can understand better when and how to apply it.

As I already did in my previous post about coding interviews, I will share my thought process when solving problems that can be solved using this methodology, so that you can do the same when you face one of them. I don't want you to memorize anything. You need to understand the technique and practice to acquire the skill of turning ideas into code. Coding is not about learning programming languages. It is about analyzing a problem, considering different solutions, choosing the best one, and then implementing it in some programming language.

Dynamic programming

Dynamic programming is a general technique for solving optimization, search and counting problems that can be decomposed into subproblems. To apply dynamic programming, the problem must present the following two attributes:

Optimal substructure.
Overlapping subproblems.

Optimal substructure

A problem has optimal substructure if the optimal solution to a problem of size n can be derived from the optimal solution of the same instance of that problem of size smaller than n.

For example, if the shortest path to go from Paris to Moscow goes through Berlin, it will be made of the shortest path from Paris to Berlin and the shortest path from Berlin to Moscow.

If a problem can be solved by combining optimal solutions to non-overlapping subproblems, the strategy is called divide and conquer. This is why merge sort and quick sort are not classified as dynamic programming problems.

Overlapping subproblems

Let's take an example you're probably familiar with, the Fibonacci numbers, where every number is the sum of the previous two Fibonacci numbers. The Fibonacci series can be expressed as:

F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)

They say a picture is worth a thousand words, so here it is (from Elements of programming interviews):

To solve F(n), you need to solve F(n-1) and F(n-2), but F(n-1) needs F(n-2) and F(n-3). F(n-2) is repeated, coming from two different instances of the same problem - computing a Fibonacci number.

This can be expressed in a recursive function:

To solve a problem of size n, you call the same function to solve an instance of the same problem, but of a smaller size.
You keep calling the function until you hit a base case, in this example, n = 0 or n = 1.

This leads us to the relationship between recursion and dynamic programming.

Recursion and dynamic programming

Conceptually dynamic programming involves recursion. You want to solve your problem based on smaller instances of the same problem, and recursion is a natural way of expressing this in code. The difference with a pure recursive function is that we will trade space for time: we will store the optimal solution to the subproblems to be able to efficiently find the optimal solution to the problem that we originally wanted to solve.

This is not to say that you must use recursion to solve dynamic programming problems. There is also an iterative way of coding a dynamic programming solution.

Bottom-up dynamic programming

You need to fill a table with the solution to all the subproblems (starting from the base cases) and use it to build the solution you are looking for. This is done in an iterative fashion, using one of the following:

A multidimensional array (1D too) - the most commonly used.
A hash table.
A binary search tree.

as your data structure to store the solutions to the subproblems.

Top-down dynamic programming

Code the recursive algorithm and add a cache layer to avoid repeating function calls.

This will all be much clearer when we start with the examples.

How to attack a dynamic programming problem

Optimal substructure and overlapping subproblems are the two attributes a problem must have to be solved used dynamic programming. You will need to verify this when your intuition tells you dynamic programming might be a viable solution.

Let's try to get a feel for what kind of problems can be solved using dynamic programming. Things that start like:

Find the first n elements ...
Find all ways...
In how many ways ...
Find the n-th ...
Find the most optimal way...
Find the minimum/maximum/shortest path ...

Are potential candidates.

Steps to solve a dynamic programming problem

Unfortunately, there is no universal recipe to solve a dynamic programming problem. You need to go through many problems until you start getting the hang of it. Do not get discouraged. This is hard. Maybe the hardest type of problems you will face in an interview. This is about modeling a problem with relatively simple tools - no need for fancy data structures or algorithms.

I have solved tons of them and still, sometimes I find it difficult to get to the solution. The more you practice, the easier it will be. This is the closest to a recipe to solve dynamic programming problems:

Prove overlapping subproblems and suboptimal structure properties.
Define subproblems.
Define recursion.
Code your top-down or bottom-up dynamic programming solution.

Complexity analysis varies from problem to problem, but in general, the time complexity can be expressed as:

Time ~ Number of subproblems * time per subproblem

It is straightforward to compute the space complexity for a bottom-up solution since it is equal to the space required to store solutions to the subproblems (multidimensional array).

Examples

I've categorized some problems according to the number of independent dimensions involved. This is not necessary, but something that I have found it useful to have a mental model to follow when designing a solution. You will see patterns, as you code more and more. This is one of them (which I have not found explicitly described anywhere else). Use it if you find it helpful.

1D problems

Fibonacci

Since by now you are very familiar with this problem, I am just going to present the recursive solution:

int fib(int n) {
  if (n == 0 || n == 1)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
  }

Going from recursive to top-down is usually mechanical:

Check if the value you need is already in the cache. If so, return it.
Otherwise, cache your solution before returning.

int fib(int n) {
  vector<int> cache(n + 1, -1);
  return fib_helper(n, cache);
}

int fib_helper(int n, vector<int> &cache) {
   if(-1 != cache[n])
     return cache[n];

   if (n == 0 || n == 1)
     cache[n] = 1;
  else
    cache[n] = fib_helper(n - 1, cache) + fib_helper(n - 2, cache);
  return cache[n];
  }

And here, the bottom-up solution, where we build a table (from the base cases) to form the solution to the problem we're looking for. This table is a 1D array: we only need to store the solution to a smaller version of the same problem to be able to derive the solution to the original problem.

int fib(int n) { 
    vector<int> f(n + 1, 0);  

    f[1] = 1; 

    for(int i = 2; i <= n; i++) 
       f[i] = f[i - 1] + f[i - 2]; 

    return f[n]; 
}

Extra space optimization

This approach could be further optimized in memory, not time (there are faster techniques to compute Fibonacci numbers, but that is a topic for another article), by using just 3 variables instead of an array since we only need to keep track of 2 values, f(n-1) and f(n-2), to produce the output we want, f(n).

int fib(int n) {  
    if (n == 0 || n == 1) 
      return 1;

    //Variables that represent f(n - 1), f(n - 2) and f(n)
    int n1= 1, n2 = 1, f = 0; 

    for (int i = 2; i <= n; i++) { 
        f= n1 + n2; 
        n2 = n1; 
        n1 = f; 
    }
    return f;
}

This is more advance, but a common pattern. If you only need to keep track of:

A few variables, you might be able to get rid of the 1D array and turn it into a few variables.
A few rows in a 2D matrix, you might be able to reduce it to a couple of 1D arrays.
Etc.

Reducing dimensions we improve our space complexity. For now, you can forget about this, but after you get some practice, try to come up with these optimizations yourself to increase your ability to analyze problems and turn your ideas into code. In an interview, I would just go for the simpler version, just discussing potential optimizations and only implementing them if there is enough time after coding your "standard" dynamic programming solution.

Climbing stairs

You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top: 1 step + 1 step and 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top: 1 step + 1 step + 1 step, 1 step + 2 steps and 2 steps + 1 step

Solution

Try to solve this problem on your own. You might be able to come up with a recursive solution. Go through my explanation and the previous examples to see if you can code a top-down solution.

A little hint: The fact that the question starts with "In how many ways", should already make you think of a potential candidate for dynamic programming.

In this case, you want to reach step N. You can reach step number N from step N - 1 or N - 2 because you can jump 1 or 2 steps at a time. If you can solve these two subproblems, you can find the solution to the general problem. Let's call f(N) the number of ways you can get to step N.

To get f(N), you need f(N - 1) and f(N - 2).
To get to f(N - 1), you need f(N- 2) and f(N - 3).
For f(N - 2), you need f(N - 3) and f(N - 4).

I don't need to continue. You can already see that:

This problem has overlapping subproblems: you'll need to compute multiple times f(N - 2), f(N - 3), f(N - 4), ...
This problem presents optimal substructure: with the optimal solution to f(N - 1) and f(N - 2), you can get the optimal solution to f(N).

which means dynamic programming can be used to solve it.

I will not write the code for this problem because ... I have already done it in the previous example!

You can write and test your solution here.

Longest increasing subarray

Given an unsorted array of integers, find the length of the longest increasing subsequence.
[10,9,2,5,3,7,101,18]

The output would be 4, for the sequence [2,3,7,101]

Solution

We need to find the length of the longest increasing subsequence for an array of size n. This sounds like an optimization problem, which could be a candidate for dynamic programming, so let's try. Imagine that you already have the solution for a problem of size N - let's call it s(n) - and you add an extra element to the array, called Y. Can you reuse part of the solution to X to solve this new problem? This mental experiment usually gives some good insight into the problem.

In this case, you need to know if the new element can extend one of the existing sequences:

Iterate through every element in the array, let's call it X.
If the new element Y is greater than X, the sequence can be extended by one element.
If we have stored the solution to all the subproblems, getting the new length is trivial - just a lookup in an array. We can generate the solution to the new problem from the optimal solution to the subproblems.
Return the length of the new longest increasing subsequence.

We seem to have an algorithm. Let's continue our analysis:

Optimal substructure: we've verified that the optimal solution to a problem of size n can be computed from the optimal solution to the subproblems.
Overlapping subproblems: To compute s(n), I'll need s(0), s(1), ..., s(n-1). In turn, for s(n-1), I'll need s(0), s(1), ..., s(n-2). The same problems needs to be computed multiple times.

Here's the code for the bottom-up solution.

int lengthOfLIS(const vector<int>& nums) {
        if(nums.empty())
            return 0;

        vector<int> dp(nums.size(), 1);
        int maxSol = 1;

        for(int i = 0; i < nums.size(); ++i){
            for(int j = 0; j < i; ++j){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxSol = max(maxSol, dp[i]);
        }
        return maxSol;   
    }

You can write and test your solution here.

How many BST

Given n, how many structurally unique BSTs (binary search trees) that store values 1 ... n?

Example:

Input: 5
Output: 42
Explanation: Given n = 5, there are a total of 42 unique BST's

Solution

Let's go through that example. Let's imagine we have numbers the numbers 1,2,3,4,5. How can I define a BST?

The only thing I really need to do is to pick one of the numbers as the root. Let's say that element is number 3. I will have:

3 as root
Numbers 1 and 2 to the left of 3.
Numbers 4 and 5 to the right of 3.

I can solve the same subproblem for (1,2) - let's call this solution L - and (4,5) - let's call this solution R - and count how many BST can be formed with 3 as its root, which is the product L * R. If we do this for every possible root and add all the results up, we have our solution, C(n). As you can see, being methodical and working from a few good examples helps design your algorithms.

In fact, this is all that needs to be done:

Pick an element as the root of the BST.
Solve the same problem for numbers (1 to root - 1) and (root + 1 to n).
Multiply both the results for each subproblem.
Add this to our running total.
Move to the next root.

In fact, we don't really care what numbers lie in each side of the array. We just need the size of the subtrees, i.e. the number of elements to the left and to the right of the root. Every instance of this problem will produce the same result. In our previous example, L is the solution to C(2) and so is R. We only need to compute C(2) once, cache it, and reuse it.

    int numTrees(int n) {
        vector<int> dp(n + 1, 0);

        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; ++i){
            for(int j = 0; j < i; ++j){
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp.back();
    }

You can code and test your solution here.

2D problems

These problems are usually a little harder to model because they involve two dimensions. A common example is a problem where you have to iterate through two strings or to move through a map.

The top-down solution is not much different: find the recursion and use a cache (in this case, your key will be based on 2 "indices")
For the bottom-up, a 2D array will suffice to store the results. This might be reduced one or a couple of 1D arrays as I mentioned before, but don't stress about this. I'm just mentioning it in case you see it when solving a problem. As I said in my other article, learning is iterative. First, focus on understanding the basics and add more and more details little by little.

Minimum path sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input: [ [1,3,1], [1,5,1], [4,2,1] ]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution

Minimizes should make you think of dynamic programming. Let's analyze this further. We can get from any cell C with indices (i,j) (that is not on the top or left border) from cells A = (i-1, j) and B = (i,j-1). From this, we can see that some problems are going to be computed multiple times. Also, we if know the optimal solution to A and B, we can compute the optimal solution to the current cell as min(sol(A), sol(B)) + 1 - since we can only get to the current cell form A or B and we need one extra step to move from these cells to the current cell. In other words, this problem presents optimal substructure and overlapping problems. We can use dynamic programming.

Here's the bottom-up solution.

    int minPathSum(const vector<vector<int>>& grid) {
        const int nrow = grid.size();

        if(nrow == 0)
            return 0;

        const int ncol = grid[0].size();

        vector<vector<int>> minSum(nrow, vector<int>(ncol, 0));
        minSum[0][0] = grid[0][0];

        for(int col = 1; col < ncol; ++col)
            minSum[0][col] = minSum[0][col - 1] + grid[0][col];

        for(int row = 1; row < nrow; ++row)
            minSum[row][0] = minSum[row - 1][0] + grid[row][0];

        for(int col = 1; col < ncol; ++col){
            for(int row = 1; row < nrow; ++row){
                minSum[row][col] = min(minSum[row - 1][col], minSum[row][col - 1]) + grid[row][col];
            }
        }
        return minSum[nrow - 1][ncol - 1];
    }

The boundary conditions are defined over the border of the matrix. You can only get to the elements in the border in one way: moving one square to the right or down from the previous element.

You can code and test your solution here.

Knapsack problem

Given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that the sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Solution

Try to come up with a recursive solution. From there, add a cache layer and you'll have a top-down dynamic programming solution!

The main idea is that, for every item, we have two choices:

We can add the item to the bag (If it fits), increase our total value, and decrease the capacity of the bag.
We can skip that item, keep the same value, and the same capacity.

After we've gone through every single combination, we just need to pick the max value. This is extremely slow, but it's the first step towards a solution.

Having to decide between two options (add an element to a set or skip it) is a very common pattern that you will see in many problems, so it's worth knowing it and understanding when and how to apply it.

// Recursive. Try to turn this into a piece of top-down DP code.
int knapSack(int W, int wt[], int val[], int n) { 
     if (n == 0 || W == 0) 
        return 0; 

    if (wt[n - 1] > W) 
        return knapSack(W, wt, val, n - 1); 
    else
        return max(val[n - 1] + knapSack(W - wt[n - 1],  wt, val, n - 1), knapSack(W, wt, val, n - 1)); 
}

A bottom-up solution is presented here:

// C style, in case you are not familiar with C++ vectors
int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[n + 1][W + 1]; 

    for (i = 0; i <= n; i++) { 
        for (w = 0; w <= W; w++) { 
            if (i == 0 || w == 0) 
                K[i][w] = 0; 
            else if (wt[i - 1] <= w) 
                K[i][w] = max( val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
            else
                K[i][w] = K[i - 1][w]; 
        } 
    } 
    return K[n][W]; 
}

Longest common subsequence (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Solution

Again, compute the longest X makes me think that dynamic programming could help here.

Since you already have some experience with dynamic programming, I'll go straight to the 2 properties, from the example. Let's call the strings A and B, and our solution to this problem f(A, B). The idea is to see whether the 2 last characters are equal:

If so, the LCS has at least length 1. We need to call f(A[0:n-1], B[0:n-1]) to find the LCS till that index, and add 1 because A[n] and B[n] are the same.
If not, we remove that last character from both strings -one at a time - and find which path produces the LCS. In other words, we take the maximum of f(A[0: n -1], B) and f(A, B[0:n-1])
Overlapping subproblems: Let's see what calls can we expect: ("abcde", "ace") produces x1 = ("abcd", "ace") and y1 = ("abcde", "ac"); x1 will produce x12 = ("abc", "ace") and y12= ("abcd", "ac"); y1 will produce ("abcd", "ac") and ("abcde", "a"). As you can see, the problems same problems need to be computed multiple times.
Optimal substructure: Very similar to the longest increasing subsequence. If we add one extra character to one of the strings, A', we can quickly compute the solution from all the cached results that we obtained from solving for A and B.

Using examples to prove things is not the way you start a mathematical demonstration, but for a coding interview is more than enough.

int longestCommonSubsequence(const string &text1, const string &text2) {
        const int n = text1.length();
        const int m = text2.length();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(text1[i-1] == text2[j-1]) 
                    dp[i][j] = dp[i-1][j-1]+1;
                else 
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }

You can code and test your solution here.

More resources

For more exercises, check the resources I listed in my previous article. For more dynamic programming specific content, the following videos are a great place to start. They get in more detail and cover other problems I have purposely not addressed here to give you more variety.

Also, check out the Wikipedia article for DP.

Conclusion

You need to become familiar with these problems because many others are just variations on these. But do not memorize them. Understand when and how to apply dynamic programming, and practice until you can easily turn your ideas into working code. As you have seen, it is about being methodical. You don't need advanced knowledge of algorithms or data structures to solve the problems. Arrays are enough.

I have not completed a time/space analysis. That is an exercise for you. Feel free to reach out with questions or comments.

PS: I hope you found this useful. If so, like and share this article, visit my blog www.yourdevopsguy.com, and let's connect on Twitter.

How to ace coding interviews. The ultimate guide.

Your DevOps Guy — Mon, 10 Aug 2020 18:57:38 +0000

This article was originally published in my blog www.yourdevopsguy.com.

Why should you read this guide?

I must have been in almost a hundred coding interviews. Sometimes as an interviewee and sometimes as an interviewer. I have struggled in front of the whiteboard and I have seen many candidates struggle.

Getting a job at a FAANG company (Facebook, Amazon, Apple, Netflix, Google) can provide you, among other things, the following benefits:

Great compensation
Fantastic working environment
Challenging work
Smart colleagues
An impressive CV

I did it and I can tell you it is absolutely worth it.

This will not be another 'How to crack the Google interview' guide, rehashing the same generic tips: study hard, practice, relax, and sleep well the day before the interview. This is based on years of experience, both as a candidate and as an interviewer.

You are not alone if you feel that coding interviews are far from perfect - I am there with you - but it is the game you have to play if you want the job. I have been rejected several times and I also have cracked the Amazon interview in just two months of study, while I had a full-time job. I have learned a lot in this process.

I do not have a degree in computer science. I had to start from scratch. This is the guide I wish I have had when I started my journey as a developer.

Not being at a FAANG (Facebook, Amazon, Apple, Netflix, Google) company does not mean you are not a great developer. It only means you haven't cracked the interviews yet. Keep reading if you want to get a step by step guide on how to prepare to get that job.

Outline

This is what I will cover in this article:

The right mindset before, during and after the interview
How to practice solving coding challenges
Technical knowledge required
Books and websites I used
Mistakes to avoid before and during the interview
Examples

How to prepare

Mindset

Developers at FAANG companies are not gods. They are regular human beings who went through the same process as you, with their own problems and insecurities. They also suffered from impostor syndrome - probably still do it. Do not put them on a pedestal. Keep this in mind at all times, especially when you get the job.

I have met interviewers who enjoyed torturing candidates. Some interviewers who would not hire some of their teammates. Luckily, they are a minority, but you might encounter one of them during your set of interviews. The only smart thing to do is to focus on what you can control: your preparation. Focus on the process. If you prepare well and are persistent, it will be a matter of time before you get the job you want. Once there, it will be easy to move to a different company if you feel like it.
You’ll have 4, 5, or 6 rounds of problems to help you, in case you fail in one - or find one of the psycho interviewers I talked about earlier. You can underperform in one of the rounds and still get the job.

Self-reflection is a great teacher. After every problem you solve and any interview to attend to, ask yourself:

What went well?
Where do I need to improve?

This will range from computer science and programming language related topics to how well you communicate with your interviewer.

Also, I do recommend applying to multiples companies at the same time, in reverse order of preference. This translates to having more options, which will put you in a better position to negotiate, reduce the pressure you put on yourself and give you more opportunities to practice.

People eventually leave these companies, be it after 1, 2, 3, or 5 years. It is not paradise, just another job, but this is something that I cannot teach you. You have to see it yourself.

How to practice

Emulate the interview set-up

Try to make your practice sessions as similar to the actual interview as possible. This includes:

Time yourself

Depending on the company, you will have around up to one hour to solve a problem. At Amazon, for instance, that hour includes a Leadership Principle related questions, which brings the time for the technical question down to around 40 to 45 minutes.

Once you start getting the grip of solving the challenges, train yourself to go much faster - 30 minutes tops. This way, the day of the interview, even if you get nervous you will be really well trained. Time flies in an interview.

No distractions

Mute your phone. No music. No internet. You want your practice sessions to be as realistic as possible.

If you get stuck, keep trying. Do not give up.

During an interview, you cannot just look at the solution. Some platforms and books provide hints. Having a look at these after a few minutes of being blocked is fine as you advance in your preparation since interviewers will likely give you some hints if you get stuck.

Think out loud

Interviewers need to know what you are thinking. Your problem-solving skills are being assessed, but your communication skills are under evaluation too. Furthermore, interviewers can steer you in the right direction and save you precious minutes if they see your approach will lead nowhere.

If you can, find a friend (virtually buddies work too), practice, and give each other constructive feedback.

Expand your toolbox

Write down anything new that you didn’t know. Functions you had never seen, cool tricks, new concepts, etc. Go through this list often until they become part of your arsenal and come naturally when you're solving problems on your own.

For instance, here is a trick to go through all the neighbours (horizontally and vertically) of a cell in a matrix with coordinates (row, col):

const vector<vector<int>> dirs = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
for (const auto& d:dirs) {
  const nextRow = row + d[0];
  const nextCol = col + d[1];

Even if C++ is not your main language, just understand the idea and try to translate it into your favourite language. If you want to use C++ in your interviews, make sure you understand every line in that short snippet of code.

Keep a log of common mistakes you make

This is one of the things that made a huge difference in my performance. You need to know where you usually underperform so that you can fix it. It can be anything: Big (O), dynamic programming problems, recursive functions, tree-related problems, etc.

Go through this list often. Review them and practice to make sure you do not make them during your interview.

Iterations

As I see it, there are two stages during your preparation.

You need to understand all the theoretical concepts and know:

When, how, and why to apply them.
When, and why not to apply them
How to connect them to solve a problem.

You need to be able to implement them and turn your ideas into code. This is what you get paid for.

Stage 1

Focus on quantity. You need to go through many problems until you start developing an intuition that gives you ideas to solve new problems you have never seen. For every new problem, ask yourself:

What algorithm and/or data structure is good for this type of problem?
Why?
Why this other approach is worse or wrong?
What are the time and space complexity of this approach?
Can I trade time for space?

This is not about memorizing solutions. I repeat. Do not memorize the solutions. It is useless and worse than a waste of time. Relying on it is buying a ticket to give the perfect solution to the wrong problem. The idea here is to learn to apply all the data structures and algorithms that you have studied. Putting the theory to practice.

At this stage, I do not write any code. I just do everything I would do before I start writing code:

Ask clarifying questions
Make sure I understand what the input and expected output are
Come up with a step by step plan to solve the problem combining (there are examples at the end of this guide)
Big(O) analysis

And then compare my approach to the solution in the book. If it is different (or worse), understand why and try to see why I couldn't come up with it: maybe I did not know the data structure, I never thought of applying it that way, etc. The idea is to change the way you think to a more elevated one where you can see the different pieces individually and how to combine them to get to a solution.

During your interviews, if you cannot pass this stage, it does not matter how good you are at Python. You are out.

Stage 2

Now, you can focus on writing the code for the problems you've "already solved". Some tips:

Do not use your IDE. During the interviews, you will not have it. It will be either a whiteboard or an online shared document. Make sure you understand the format of the interview so that you can focus
If you need to write code on a whiteboard, I'd recommend solving some problems in paper as you get close to the interview. Writing on a whiteboard is different from typing on a keyboard. It is a skill you will want to practice.

If a problem is too hard, save it for later. Focus on making progress. This will create positive momentum that will help you tackle harder problems later.

You can't afford to spend 5 minutes to write a while loop. You need to be in good coding shape. Be very comfortable in your preferred programming language (you can usually choose it). The better you know the language and the more fluent you are, the more time you will have during the interview to focus on the actual problem that you need to solve and to communicate your thoughts to the interviewer.

Tech knowledge

What you should know

I'll enumerate the main topics you should be familiar with. You must know them cold if you target at FAANG companies.

Data structures

Theoretically and how to use them in code

Arrays
Strings
Lists
Stacks and queues
Trees (and tries)
Binary search trees (balanced)
Hash tables
Sets (disjoint sets too if you can)
Graphs

Algorithms

Binary search
Sorting
Recursion
Divide and conquer
Dynamic programming
Greedy
Algorithms on strings

On graphs (very important):

DFS
BFS
Minimum spanning trees: Kruskal and Prim
Shortest path: Dijkstra and Floyd-Warshall

Some discrete math can help too.

Programming languages

I've always used C++, but the following good for interviews too:

Python
JavaScript
Java

Since most interviewers know them. Most candidates tend to go for Python. Whichever you choose, make sure you know it well.

More resources

MIT courses on algorithms

This course is a great introduction to most of the concepts you will need in an interview.

I would start here and only go to the next book for more in-depth explanations.

Introduction to algorithms

You do not need to go through the whole book, but it's a good complement to the previous course. It has everything you may need - and much more. Focus on the topics I have listed before. Everything else is nice to know but the chances of it coming up in an interview are slim.

Cracking the coding interview.

I did not start here though. I only completed the problems in the last 2 sections (medium and hard), after I finished the next book.

Elements of programming interviews

This is an excellent book. I keep coming back to it before every interview. The questions are hard, so you will be very well prepared. There are C++, Python, and Java versions.

For more problems, I only used https://www.leetcode.com. You'll have more than enough with the free problems.

Mistakes to avoid

Let me help you avoid the most common mistakes I have seen so that you can nail your coding interview.

1. Not preparing

Yes. People go unprepared. I’ve seen many people blank during an interview. I’ve had to cut interviews after 20 minutes. It happens more than you may think.

Just as a reminder, you need to be good at the following:

Algorithms
Data Structures
Language(s) of your choice
CS Fundamentals

I’ve previously covered resources for algorithms, data structures, and programming languages (through solving problems, a better way of learning than reading or watching tutorials). You should be able to assess what areas of computer sciences you need to brush up.

2. Not communicating what you think

We interviewers cannot read your mind. Make sure you think out loud. We can stir you in the right direction before you waste too much time on the wrong approach. We assess your problem-solving skills, but to do that we need to know what you are thinking. Make your interviewer’s life easier and you’ll have a higher chance of landing that job.

3. Not asking clarifying questions

The questions will be vague, on purpose. Make sure you state all your assumptions before you start solving the problem. For instance:

Is the input sorted?
Are there repeated elements?
If no solution, what should I return?
Do I need to check for invalid inputs?
How many users do we expect?
Trade-offs: increase space to be faster?

4. Solving the wrong problem

Gather all requirements before starting. One small change can make the problem completely different. Repeat the problem using your own words, to buy some time to think about the solution, and to ensure you’re solving the right problem.

5. Wasting time

If you don’t remember the API, just say: “Let’s assume the function is like this” and move on. You can assume you have the function you need and then come back to it and write it down in detail. An “imperfect” solution is better than nothing.

6. Not testing your code

This is a huge red flag, so make sure you don’t fail here. Come up with a few test cases (there is no need to write the actual code):

“Happy path”
Edge cases
Empty/null input
Repeated elements

7. Not debugging it

Take one or several of your previous test cases and run them through your code, line by line. Make sure you get the values you expect. Even if you miss something, the fact that you are doing this already gives a very good impression.

8. Poor time and space analysis

Learn how to analyze the time and space complexity of your solutions. It’s just a chapter in any of the books I have listed before.

9. Going for the optimal solution

First, come up with the brute force solution. No matter how slow or obvious it may sound. Having that is already a positive point. You don’t need to write code at this stage, but explain your solution in detail. If you cannot figure out a more optimized way of solving the problem, then you can start coding this solution.

From there, try to find bottlenecks and come up with an efficient solution (usually using a different data structure or after sorting the input). It’s better than having nothing at the end of the interview because you tried to find the O(1) solution.

10. Not being fluent enough in your language of choice

Usually, you can pick up the programming language you want for the interview. If you say you can code in Python, JavaScript or Java, make sure you don’t need 3 minutes to write a for loop (I’ve seen this many times). It is is not the end of the world if you forget API details or a semicolon.

11. Edge cases

Do not forget to test for edge cases. I cannot stress this enough. Most problems you will be given will be vague and have edge cases just to see if you think of them when you face a new problem.

12. Low-quality code

Write clean code. Not just for the interviews. Good naming, short functions that do one thing, etc. Read "Code complete" by Steve McConnell. This will increase the quality of your code.

13. "Hacking" mistakes away

If you find a bug in your code (an off-by-one mistake, for instance) do not try to hack your way into the correct code. Take a minute to read what you have written, not what you believe you have written. Jot down some small examples and try to come up with a solution from them. Be systematic. We assess this too, not just the end result.

14. Jumping straight into code

Do NOT jump straight into writing code.

Solve the problem "by hand".
Explain your solution
Analyze it (in Big O)
Find bottlenecks and try to come up with something more efficient

After all this, you can start coding.

15. Not managing space well enough

The whiteboard is limited. Leave some space between lines so that you can erase and modify your code easily if you need to. You can draw lines indicating where the new code would fit if you are running out of space.

16. Asking for feedback at the end

Do not ask for feedback at the end of your interview. Interviewers cannot give you the feedback (usually there are company policies to prevent this) and it gives a very bad impression: insecurity and inability to assess your performance.

Examples

Try to solve the following problems on your own. Here, I will not write a complete solution but I will show you my thought process. With a little practice, turning your ideas into code will be relatively easy.

Example 1

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

This is a very easy problem, but enough to focus on the process. Things that come to mind:

The input is an array of integers a. Is it sorted? b. What if it contains repeated elements? c. What if it contains negative elements? d. What if all the elements are negative/positive? e. What if the array is empty? f. How big is it?
Return indices a. What if there is no solution? b. What if there are multiple solutions?

You would need to ask some questions to the interviewer to clarify the most relevant points here. The questions about the array are pretty generic, created to make you think. In some cases, you may want to ask about the sign of the elements, if they are unique or repeated and if it is sorted. In other cases, ask what happens if the input is invalid - you may want to throw an exception or at least mention it even if you don't write the code for it.

Regarding the output, you need to clarify what happens if there is no solution and if there is more than one.

There are different approaches to this problem, with different time complexities. If you get stuck, try to mentally go through algorithms and data structures and see if they could help.

Usually sorting and hash tables can simplify many problems. This is one of them.

You can find the solution here.

Example 2

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.

Thoughts:

Count the number of islands. I need a counter (obvious)

2d grid map:

Can I model this as a graph? I know BFS and DFS
Islands are connected horizontally (same row) or vertically (same column), not diagonally
I can only visit an island once, so I need some mechanism to avoid counting the same island twice. For instance, change the '1's to '0's (be it in the matrix we receive or in a copy we create if we can't modify the input) or a hash set where you store a pair of indices that define visited cells. I would go for the first option, but the second one is good to know since it can be used in other problems.

After having these two pieces of information, it is just a matter of turning that into code. Choosing between DFS or BFS is something you want to discuss with your interviewer, depending on the constraints of the problem. If you can choose, DFS is shorter.

Make sure you consider the case of an empty matrix, a matrix full of ‘0’ - zero islands-, full of ‘1’ - just 1 island- and other test cases. What happens If you see a ‘2’ when you’re scanning the matrix? This is also something to discuss with your interviewer, like any other assumption. In case of doubt, it is better to overcommunicate your thoughts.

You can find the solution here.

Conclusion

As you have seen, there is little code here. This is because writing the code only comes after thinking and analyzing the problem. Turning it into code is kind of the easy part (it obviously varies from problem to problem). Also, you can see how I’ve followed the process described in the last section: clarify the problem, come up with solutions, communicated with the imaginary interviewer, thought of edge cases, etc. This is what you should do until it becomes second nature.

Prepare, be systematic, and patient. It is a lot of work to prepare for these interviews, but in life anything worth having requires effort.

PS: I hope you found this useful. If so, like and share this article, visit my blog www.yourdevopsguy.com, and let's connect on Twitter.