How to learn to solve coding interview questions using Leetcode (Part I)

Introduction

I’ve been working as a software engineer for the last 8 years. I spent my last 5 years working for big companies (Amazon, Google and Facebook) and I am excited to have the opportunity every day to learn how to build software for big companies that scales up to millions of requests per minute (or even more).

As a software engineer, I believe there may be one thing that you will never feel ready to do without proper preparation (yes, even if you are a senior staff software engineer): a coding interview question.

In my experience, I’ve always had to spend many hours to practice on coding questions and some of the reasons are:

• You are on a stressful situation, you don’t usually write/solve a coding problem under similar constraints;
• You have to solve the problem in a limited amount of time;
• You don’t have an IDE (for many it does not matter, true)
• You don’t work on those type of problems on a daily basis (I am sorry, especially if you are a senior software engineer, you end up coding less time)
• As usually reminded by the recruiter, you have to make sure you focus a specific strategy: talk out loud, explain your thinking process, ask questions, don’t go straight to coding, show you can deal with ambiguity (I love this one…)

I mainly used Leetcode (Premium version) as the platform where I practiced. I think that Leetcode is enough to get a proper preparation — you don’t need to use multiple platforms because, as you may have heard before, the goal here is the quality, not the quantity (and Leetcode has a lot of good quality excercises).

I’ve personally found that I can deal with a behavioural or a system design interview without preparation, but a coding interview will always take me time to prepare (assuming I really want that job and I don’t want to fail).

Objective

This document will be quite technical: I’ll publish here all the notes that I took when studying the exercise I solved.

Yes, I did study the exercises and I focused on finding the patterns between different types of questions. I also focused in learning the thinking process so that starting from the question I can understand what are we talking about and how to solve it.

Interview questions usually originates from real problems but you have a big advantage: most of the times they are simplified and they are converted to an easy domain that can be understood in few minutes.

The strategy

The key point of your preparation is that in the end you need to be able to:

• quickly interpret a question
• understand what category that question belongs
• think about the right data structure
• outline the time and space complexity
• (if needed) implement the solution
• (if needed) find if there is a better solution

I got pretty good in solving coding question up to the point where some of the hard questions were easy for me: I have to admit though that there have been questions that definitely went over my limit and even nowadays I would not be able to solve them.

Remember: it’s rare that a question is so hard that it cannot be solved in 20–25 minutes; so if your algorithm seems to be very complicated and long I would really recommend to take a step back, ask for hints (it’s not a bad sign) and re-start.

Arrays, Maps and Sets

Let’s clarify something: a data structure is a way to model the access you have to memory in your computer. In the end, it’s all about memory, it’s just the way you interpret/model that memory so that your thinking process is easier and faster. This is why I’ve decided to put the three most important data structures altogether.

I assume for someone this section may be too intuitive, so feel free to go ahead if you are quite familiar on when/how to use them.

First thing first: ask yourself if by ordering an array given in input can help you find the solution. If so, you may have found a [sub]-optimal solution (I put sub- because in some cases your ordering solution will not be better than O(nlogn) but in reality there may be something better).

Use an array for linear or binary search.

Use an array and calculate the cumulative sum when you have to find the existence of some particular subsequences (e.g. continuous-subarray-sum).

Use an array when your input domain is [0.. n-1] so that the value themselves can be used to point to other places of the array itself. (e.g. the array contains 5 elements like 0 4 1 3 2 — you can use the values inside the array to jump from one position to the other). In this case you can also mark its values to verify if certain conditions are met. (e.g. if the input values [0.. n-1] of an unsorted array are all positive, then every time you meet a number i, you can negate its corresponding position in the array so that you know that you saw the number i before).

Use an array if the problem requires you to explore the entire input once — O(n) — and you can just verify that a condition has to be always met.

Use a set when you need to index things and check if something is present (e.g. find duplicates).

Use a set when you need to find the longest sequence of consecutive numbers (this may be not intuitive, an example is here).

Use a map if you need to index elements, for example if you want to know which position each element occupies.

Lists

Reversing a list

Reversing a list is one of the most common exercises. You can reverse a list by using recursion. Alternatively you can use a stack to model the recursion behaviour.

It gets a bit trickier when you want to reverse a portion of the list, but in this case you just adopt a well-common strategy of:

• Think of a simplified problem (the whole list) and try to solve it;
• Apply the constraints;
• Solve the algorithm as solving the subproblems altogether.

Here’s an exercise where you can practice this approach.

Note: perhaps you can consider adding a fake node at the start to help in case you have to reverse from the first real node.

Let me give you some inspirations for the linked exercise:

1. Think how to use two nested recursive functions;
2. Find the k elements to reverse and reverse them (note: detach the last node from its next so you actually have a list of k nodes that you can entirely reverse) and call the function recursively to attach the next node of the following reversed list
3. You need to save crucial nodes in variables, detach the “last” node from its next and save its next in another variable, because that next will actually be the next node from which the function will be called recursively (yes, very hard to tell that in words :))
4. Try to sketch the code in macro pieces…
5. You can reverse the entire list (in this case is of k elements) by using recursion

..and in case you are wondering how to reverse a linked list without recursion, here’s the code snippet:

Find the middle point of a list

Find the middle point in a list (not an array) requires a bit of thinking if you want to avoid exploring it twice.

In fact, to find the middle point you need to at least know the size of the list/array so you can count until the half. But a list does not necessarily come with its size: that is why a one-pass solution is to use a fast pointer that moves two by two and a slow pointer. The slow pointer will be in the middle when the fast reaches the end.

Matrices

Matrices are clearly an extension of arrays, this is intuitive. Hence you could apply the same strategy applied to an array, with the only difference that you are navigating in 2-dimensions.

When your input is a matrix, depending on the question you can consider the following:

• if locality is considered in the question, can you start applying your strategy to the first two rows, get the result and then iteratively apply it to each next row?
• Can you think the matrix as an histogram?
• Do you need to traverse the matrix diagonally? If so here’s a snippet that would let you do that (note: traversing diagonally is just a bit tricky, it requires to use one single index with an offset — but keep in mind the boundaries if a matrix is not squared)

• you can traverse a matrix recursively. You define the recursive function that takes in input (among the others) i and j and first increments i until the end of the row is reached and then it resets it while incrementing j.
• for sudoku’s like problems, you can calculate the index based on the quadrant of a matrix with a formula like (i/3)*3+(j/3)
• Rotate matrix: you can use a peel-the-onion strategy. For every “layer” of the matrix you pick the four elements altogether (one from each side) and you swap them. This should be somehow intuitive, you just need to pay attention to the stop-conditions.

Stacks and Queues

Use stacks when you have to “keep aggregating” elements until a certain condition is met and you start popping from it — you flush the stack. A cool exercise is the one to count the trapped raining water.

Similarly to the push, the process of popping from the stack happens until a certain other condition is met.

Two examples where stacks are used successfully are mentioned here.

To compute the largest rectangle area in the histogram (presented as an array whose values represent the height of each bar), you keep inserting in the stack until you find a histogram bar that is shorter than the one at the top: in that moment you understand that you will not have a rectangle at that height anymore, so you compute/check if you can improve the max by popping values.

Complex calculators (using parentheses, operators with precedence) can be solved with two stacks as well (one for operands and one for operators). Traverse the operation in order (not reversed).

Indexes

Indexes are surely well related to arrays but things get interesting when you start using more than one index.

You can use more than one index when there is a locality principle that drives to the solution of the problem.

Using a start and end index is useful when you have to find a group of consecutive elements that satisfy a condition. Such indexes can also be interpreted as sliding window. A sliding window can be implemented in different ways depending on what is the purpose:

• Greedy approach: you expand as much as you can, and after that you compress
• Fixed size: intuitively you advance start and end index at same time.

Use a slow/fast index (also known as the tortoise and the hare) when:

• You need to find a cycle
• You need to find the duplicate number (there are multiple ways to solve this, slow/fast index is not the most intuitive)
• You need to find the middle element in a list in O(n) (one index moves by 1, the other moves by 2)

You can also use a left/right index: the most common application is in the implementation for the quick-sort. These indexes start at opposite directions and moves one against each other.

To find the pair of elements whose diff equals to a certain value k in a sorted array, you also use two pointers. In this case the idea is that you keep i fixed and keep incrementing j until the either diff equals k or is bigger. If it is bigger, there is no point in keep increasing j; you can only increase i and you leave j where it is (you don’t reset j because you already know that diff < k for sure — remember the array is sorted).

Another nice trick you can learn when using pointers is in the National flag dutch problem.

Sliding Windows / Sequences

Sliding windows can solve different types of exercises and usually they are accompanied by using two pointers, so conceptually they are almost identical in the way you approach to a problem when using two or more pointers.

Use sliding windows when:

• You have to find a consecutive pattern in an array or a string
• You have a fixed number of things you can take (e.g. at most k types of fruits from a list of trees) and so you have to maximise it.

For more complicated questions, you may need to use a map to track the position/frequency of the things contained in the window.

For easier problems, you may actually need to just update the left pointer to the right every time you “fail” (i.e. you can’t go longer than that with the right pointer).

Some of the most common examples are:

• find the longest substring with at most k distinct characters
• find the minimum window substring

To find the contiguous max sum in an array with negative numbers, the trick is that you can use two pointers and keep a runningSum and max variables. You update the pointer i to the latest index j the moment you find the runningSum becomes negative (there is no sense in keeping that sum since it will make it worse for the future sums). In all the other cases, you just increment j.

Some exercises need an intuition: in the maximum product subarray for example you need to realise that if the amount of negative numbers is even, then all array is good, if they are odd you just need to exclude one (greedy approach): which one? It is convenient to either remove the leftmost or the rightmost, otherwise you would exclude many other numbers — so you either go from left or right and you compute the multiplication.

Finding sequences in the array

If sequence is related to adjacent numbers, then usually the problem can be solved linearly with more than one pointer (or at worst easily with O(n²))

When the subsequence is about numbers in different positions, then you need to jump from one place to the other and this would usually be O(n³)). So in this case an array of map can help. You can build a map for every element of the array: the map contains info about the current element with its previous. So this map can be used by the elements coming after. This recalls about dynamic programming.

Alternatively, I think it is possible to flatten and create another array whose index represents values of the original array and whose values represent the index of the original array. In this way the advantage is that you can jump from one position to another in constant time based on the values of the original array. (see the longest arithmetic sequence exercise).

The sliding window maximum problem can be solved in linear time with some observations (using an ArrayDeque — O(1) to poll from tail and start):

• You make sure to always leave in the queue only elements that are in the range of the window
• You make sure to always remove elements from the tail that are smaller than the new one being inserted because for sure they will not be needed for the answer
• You insert the element in the queue if it is smaller than the one in the tail (because in reality you don’t know…it may become the next bigger in the next window)

Exercises with sequences can have a lot of variations. The longest consecutive sequence asks to find the longest consecutive sequence of numbers (5,6,7,8,9,…) in an unordered array. That implies that either you order (which then makes it “trivial”) or you actually use some logic to understand that:

• You can create a set with all the numbers in the array
• You go through the set and from each number you try to keep looking for the next number until you don’t find it and stop — here you update the max if needed
• For the next number num you always check if num-1 was in the set as well, because if it is you actually don’t need to re-search again.

Pattern matching

Sliding windows, sequences, substrings have always something in common: they also relate to pattern matching.

A pattern matching usually uses two pointers that represent a sliding window.

Consider that when you need to find a pattern that contain repeated letters, it is convenient to transform the pattern itself into a map that also contains the frequency.

The idea behind pattern matching is to iterate over the string S to fill a map of letters of the same size of the map P with the same frequency. When you encounter a map that satisfies the criteria, you just update the result with the shortest length of the pointers l(eft) and r(ight) you are using to navigate in S.

General rule for pattern matching: When frequency is important, checking the size of a map or a set is not enough. So to meet the matching condition you also need to check the frequency: for these reasons, increment by 1 the variable that checks if a value is in both maps only when the frequency matches.

For example: you have a pMap that represents the pattern (“A”:1, “B”: 2, “C”: 1) and then you are building an sMap for the string s to navigate. Once you’ve found a char B in s, you don’t directly increment the foundCharacters variable but you wait until when the frequency also matches.

Some key points about pattern matching:

• Try to use an array where every position indicates a letter and its value the frequency
• Try to create a unique number for every unique string so that you can use a sliding window and search through the string in a linear time (e.g. DNA string matching — see Rabin-Karp algorithm below)
• Try to use two pointers: expand as long as you are going towards the goal, compress when any of the condition is broken again
• Some other times you need to create a class of equivalence that is represented by a value. For example the class of equivalence of shifted strings (e.g. “abc” == “bcd” == “xyz”) is represented by the string shifted by using an offset calculated from str.chatAt(0) — ‘a’. That way all those strings will be the same if they belong to the same class of equivalence.

Rabin-Karp Algorithm

This is a very famous algorithm used to, for example, search for ear in the sentence “Doe is hearing me” — in this case you have to find for an exact string (you know chars and length) so you can precompute a hash function for every substring of length 3 (in this case) and then you compute the next by subtracting the value of the char you are removing and adding the new value.

For example, if the current substring is hea → ‘h’ * 128² + ‘e’ * 128 + ‘a’ so to go to ear you just do this → (hash(hea) — ‘h’* 128²) * 128 + ‘r’

This problem can also be identified as “Find the needle in the haystack”.

Intervals

Sorting intervals usually helps solving problems with intervals. Flattening the interval into a single array also usually helps:

• Either you create an array whose indexes/size relates to the interval ranges
• Or you create an array that contains Integer[] — first value is the start/end of the range, second value is the value itself associated to that range (put it negative if end range).

Meeting Rooms II problem is something in between the interval concept and the allocation. In fact, a good strategy is either sorting and then flattening the array so then you count the max of the rooms you have to allocate (by +1ing or -1ing navigating through the flattened array) or you sort it again and then you use a min-PQ (Priority Queue) that contains the rooms used/created so far and putting as peek() the room that is going to be free first. So you know that if there is a room you can use, it will be the one at peek() otherwise no room can be used and you create a new one.

Find intersections between intervals

If you have to find the minimum number of rooms for lessons at different hours, or the minimum number of arrows to shoot balloons that are on a 2D space, you can use a greedy approach by sorting intervals based on the end value. With the greedy approach you take the best local decision that (since the intervals are sorted) leads to the best global result.

Conclusion

This is the end of the first part of my “let’s share my notes for the others” series. I am planning to write other 3 parts after this (I took more than 30 pages of notes).

Hope this may be helpful and inspirational for who is currently preparing for a coding interview :)