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

Priority Queues

Well, I love priority queues (heap). They are used in a?big variety of applications?and in my mind they are a very elegant data structure.

Use priority queues when:

• you have to find?the smallest range covering elements from k lists?— in a question like that, you need to keep track of?min and max?values: that is why priority queues match well.
• you need to find the?k-th largest value in an array?— you don’t need sorting for all the array in this case, you just can handle a heap of size k and you’ll get your result at the top of the heap itself (is it max or min heap? Try to think about it)
• you are in a maze?and you apply Dijkstra together with a heap data structure to decide what is the next node to explore in the graph?(Keep a separate matrix to measure the cost / gain. So the same matrix will be useful to avoid repeating the same steps.)

There are so many places where you can use a Priority Queue (CPU allocation algorithms work on similar logic). To do some practice, try to think where else you can use them (and let me know!)

Pattern #7: Divide and Conquer

Usually you can split the problem into smaller problems with a divide and conquer strategy: smaller problems are easier to solve and when combined together they give you the solution.

For example,?converting a number into its word representation?consists of repeating the same strategy to group of 3 numbers each?(divide), and for each group you apply the same pattern?(conquer)

Pattern #8: Binary search

The key on how/when to apply?binary search?is to find the proper search space (a bit like the Fourier transform does).

Most of the times the search space is done with the indexes, in the more tricky cases you do it by searching?through the values of the array/matrix.

Let’s say you want to find a range of the same values in a sorted array.?You can apply a binary search twice: in the first case you consider “as if” the target was “bigger than..”, so you keep moving?hi?down until you are effectively being stopped by the?lo < hi?condition. In the next loop you are going to treat the position with value?== target?“as if”?it was smaller so you keep incrementing?lo?until you are effectively blocked by the?lo < hi?condition

The trick is: you can treat the?arr[mid] == target?as if?it was smaller or bigger than the target so that you can reach the leftmost?arr[mid] == target?or the rightmost.

Sometimes you have to stop when?lo < hi?OR?lo <= hi.?Some other times you don’t have to find a target (i.e. compare arr[mid] with the target) but you have to compare arr[mid] with either arr[lo] or arr[hi] (For example?https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii)

In these cases you actually stop when the condition between lo and hi is not met anymore.

Remember: the final condition can either be when?lo?and?hi?do not respect the while condition OR when the target is met with arr[mid]. This affects a series of decisions like:

• How to update lo and hi
• What if statements to check (arr[mid] < arr[hi] OR arr[mid] < arr[lo] OR …)
• What?while?condition to use

Look at these example and see how can you apply binary search:

• https://leetcode.com/problems/find-the-duplicate-number?(think about the values, not the indices)
• https://leetcode.com/problems/the-skyline-problem/
• https://leetcode.com/problems/k-th-smallest-prime-fraction/

Pattern #9: Domain conversion

This reminds me a lot the?Fourier transform: you can model the same problem in different domains — in one of them it will likely be easy to solve in linear time.

Pattern #10: Trees

Exploring trees is a classic in software development. Especially when you have to solve hard real problems, modelling into trees it’s one of the most common practices. But let’s get to what are some of the (non-classic) questions about trees.

Exercises like finding the max diameter (or longest path) usually get easier if you use external/global variables. For example you explore the subproblem created from its children, for every subproblem you check if you have improved the max (or the min or whatever — sitting in the global variable) but at the same time you?return?the best result you can to the calling problem as well.

Imagine you have to explore a tree as if it was a graph: one thing you can do is that you can first explore the tree in dfs and store the parent relation (in a Map). That way you can then use a bfs as if every node would be connected to n+1 nodes (its n children + its parent).

Imagine you have to find the longest distance of a node inside a tree that is not the root. This would be like using a graph theory in a tree which can be a bit tricky and not intuitive. One approach is the one I’ve just mentioned. Alternatively, you can divide the problem into subproblems:

1. You explore the tree in dfs (in search mode)
2. You call the dfs on left and right children and you expect an integer returned. As soon as you find the target, you know from that point on you can start a subproblem as if that target was the root of a tree (so you find the longest path from himself to its children)
3. Once finished, update the longest path if needed and return 1 (to indicate that the target was found and it will have distance 1 from its parent). In the remaining cases (say you are in a generic node x in the tree):
4. If the target is in the left side of x and the value returned is?dist, then you can switch in “find-longest-path” more by exploring the right path and get its longest distance to which you can add?dist
5. Update the longest distance (if needed — as a separate property) and then return the?dist?from the target (something like dist+1). Same is valid for the right side (just dual problem).
6. If it’s not in any of them, you just return -1 and you don’t go further (because you are?in search mode)

The concept of?finding a path?can be useful. To find a path one way is to dfs the tree until you find the node and then you update the list (passed as a parameter) with that node. You return from that recursive function and from now on all the nodes (who will check that the list is not empty anymore) will put themselves.

If you have to match two paths and?find the place where they intersect, you can treat them as a list: you can start from the start/end (depending on where you know for sure that there will be a starting element in common —?a.k.a. The root) and then you keep incrementing the indices until the values diverge.

Stacks?can be used to explore a Tree (even in DFS mode). Sometimes it does not matter how you explore the tree, so you just keep adding elems/children in the stack as soon as you find them.

To get the diameter of an undirected tree?it is just about going to the furthest node you can starting from a random node, and from there repeating the call to go again to the furthest node.. This way you’ll get the diameter (because you checked the “two farthest” nodes).

Note: Avoid revisiting!?Almost every time, you need to avoid revisiting the same node. So you use an array/map/set that keeps track of what nodes you have visited. Other times you need to only avoid visiting the same path, but you can go through the same node multiple times; in this case you keep track of an array of array (emulate the adj list) to store whether you’ve used that path or not.

Horizontal/Width/BFS

Remember that when trying to traverse a tree in BFS a node at?pos i?will have its children at position?2*i + 1?and?2*i + 2. This comes handy the moment you have to compute length, distances at the same level of the tree. BFS is usually done with a queue: to use the queue in BFS it comes handy having a while?queue is not an empty?loop and an inner for that iterate for the?size?of the nodes in that layer.

An important note is that?if the tree is complete?then once you try to put the nodes in the list, its size should match the value of the node (computed based on the 2*i + 1or2 rule) of the last elem.

Serialization

You can convert a tree to a string by using null and using the layered BFS exploration (Only one note about?avoiding?the full last line of nulls — that can be caught with a boolean flag).

On deserialize feel free to “greedily” assign the next token of the string to the next left, the next right, and so on.

Exploring trees

Having intervals (max, min) passed to the recursive function can help in:

• Search for items
• Build tree from a given array with known order (preorder,inorder)

Find target sum in a Binary Tree (any path that goes downwards)

Convert the problem as if you were looking for a target in any continuous subarray in an array. That problem is solved with a hashmap that contains the cumulative sum and checks if the current sum — target sum is a number that exists in the hashmap (and how many times it exists).

The tricky part is to create all the paths: we know that they have to be downwards, so at any node we can split the existing path (passed from the parent) to two paths (by exploring the left and right). Once we are done exploring left and right we just?get rid?of the information coming from the current node (we remove its?runningSum?from the hashmap).

Return next sorted value from a BST (Iterator mode)

This can be done with a stack by taking into account that we traverse the tree in in-order mode.

Alternatively, by being able to point to the parent, we can understand what is the next value to print with the following rules:

• If the node I am coming from is my parent then go left
• If the node I am coming is my left child then print myself
• Then Go right
• If the node I am coming is my right child then go back to my parent

Pattern #11: Graphs

You can represent them with nodes and a List<Node> for every node. Or an array of edges (where an edge is just an Integer[] of size 2). Or an array of LinkedLists (every elem of the array is a LL and it lists the nodes to which the node represented by the array index value is connected to).

Or however you want or make the problem easier to handle.

Detect Cycles / Topological sort

You can implement DFS and use two Sets: one to track if in the current depth exploration you don’t visit the same node, and another set used for optimization and avoid exploring again the same paths.

An alternative is to use in-degree order traversal, i.e. traverse first the nodes with 0 indegree and then decrement the indegree of the adjacent nodes once you explore the nodes with 0 indegree.

Class course schedule exercises

You can use DFS with tracking visited. By using topological sort based on the indegree, you are making sure to explore first nodes that have no dependencies (i.e. can start anytime) and by traversing them, you are “unblocking” the ones who depend on it (unblocking == decrementing by 1 their dependencies).

Minimum Height Trees

It’s about topological sort again. find the nodes that are leaf and traverse them back until you find the intersecting point.

Alien Dictionary (here)

This uses topological sort to find the letters that come first (indegree = 0) and then it iteratively decrements the indegree of the related nodes by finding new?indegree=0?until all nodes are visited.

The other key point here is?how the graph is built:

• Word list is provided in a?sorted?manner based on the alien dict
• So by comparing words in pair you can get all the possible information:
• To be more precise, the useful info you get by comparing two words happens as soon as the two chars at the same index?i?is different (example:?wfrt?and?wfbg?tells you?only?that?r < b?and nothing more — this will be translated in the graph as r → b

Exploring a matrix

Exploring a matrix is usually like exploring a graph: the adjacent cells are the adjacent nodes.

You can explore it in multiple ways: DFS, BFS or by applying Dijkstra to determine what comes next for optimization purposes.

BFS

One exercise whose only solution would be to use BFS is the?minimum knight moves, because other similar choices would lead to infinite non-stop result.

Keypoints here are:

• Use queue with a double?for?loop to implement BFS
• Use a visited DS that stringify the pair i — j
• (specific to this problem)?— the 4 quadrants can actually be reduced to only 1 quadrant (there is a trick of checking if newX and newY are both >= -1 and not >= 0 because of some edge case…)

BFS with Path storage

2 approaches:

• The content of the queue can store the path itself instead of the node
• You can track the parent and so once you reach the?solution?you can backtrack by using the parent mechanism

Pattern #12: Tries

Tries are fancy just because few talk about them. They are used typically when?prefixes are important?and need to be checked / compared.

Implement it as if it was a tree. Use a node with children, whose value is usually a char and then a flag to indicate that it is the?endWord?or not.

Tries can be used to find words in a?graph?of letters (or simply a matrix). If you build a trie about the known words, the moment you explore the matrix you can?fail?fast as soon as you realize there is no prefix like that.

Pattern #13: Segment Trees

Segment trees are useful for getting the sum of a range of elems in an array.

The root of ST represents the sum of all the arr. If left and right children contain a portion of the total sum (the sum of the left side and the sum of the right side).

Building the ST can be done in a bottom up approach by storing it in an array of 2N + 1 elems.

You use a?divide and conquer strategy: by having?lo and hi, you get the mid and you solve the subproblems [lo, mid] and [mid+1, hi], whose sum gives the value of the current node.

Query a range means understanding the intersection between the requested range and the range of the current node (it can be fully included, not included or partially included).

Practice here with some exercises:

• https://leetcode.com/problems/range-sum-query-immutable
• https://leetcode.com/problems/range-sum-query-mutable/
• https://leetcode.com/problems/range-sum-query-2d-mutable/
• https://leetcode.com/problems/range-addition/
• https://leetcode.com/problems/range-sum-query-mutable/

Thanks TO : Marco Suma