Software Engineer Interview Questions to Know (Entry Level) — Lowest Common Ancestor & Binary Search

If you’ve just stumbled onto this series, make sure to check out the introduction here.

Question 1: Find the lowest common ancestor (LCA) of two nodes in a binary search tree (BST).

Variants

• Given the root node of a BST, determine if a target node exists in a binary search tree.
• Given the root of a BST and a target node, return the path from the root node to the target node.
• Find the LCA of two nodes in a BST if the nodes contain references to their children and references to their parents.

What They’re Really Asking

• Do you understand the structure of binary search trees? Can you leverage the ordering property of a binary search tree to optimize search?
• One solution to this problem requires a recursive implementation. Can you work with recursive algorithms?
• Do you understand how the answer to this problem changes if the nodes have references to their parent nodes as well as to their child nodes?

Tools for Our Answer

• We will assume the reader has adequate knowledge of Trees and BSTs. For those who need a refresher, check out Question 2 of Part 3 of this series here.
• For our purposes, we will define the ordering property of a BST as follows: for every node n, the value of all left children < the value of n < the value of all right children. An example of some BSTs are below.

BST Examples

• Let’s look at the leftmost example from the above. Let’s pick the following two nodes: 4, 7. Beginning at the root node, we see both 4 and 7 are less than 8 so they must exist in the left subtree with root node 3. We then see 4 and 7 are both greater than 3 so they must both exist in the right subtree with root node 5. However, 3 and 7 are neither both greater nor both less than 5 so this is the LCA.
• We can visualize this below. We’ll let the square enclose the smallest subtree that contains both our nodes. The => symbol denotes the implication that “since 4,7 < 8, we can solely look at the left subtree”.

Successive Subtrees Based on Structure of BST

• Note that 4 and 7 need not be the direct children of the node with value 5. Since 4 < 5 < 7, we know that 4 will be a left child of 5 and 7 will be a right child of 5. This means they will have no lower common roots.
• This provides 3 basic cases for our algorithm. If the values of both our target nodes are less than the value of the current root node, we recursive down the left subtree. If both of these values are greater than the current root node, we recurse down the right subtree. Otherwise, we know one node exists in the left subtree and one node exists in the right subtree. In this case, we have found our LCA.
• This is implemented in the algorithm below.

Recursive Implementation for the LCA Problem. Code source here.

• This solution is fast but it is inefficient in terms of memory complexity since we are making calls to the Call Stack. We can improve it by using a Stack as shown below.

Iterative Solution to Solve the LCA Problem. Code source here.

• This is the optimal solution — both in terms of memory and runtime.
• We can use a similar approach when determining if a node exists or determining an optimal path. We move down the left or right subtree depending on if our target value is greater than or less than our current value.
• If the nodes in our BST contain references to their parent nodes, these question becomes very simple. We start with one node and store the path from this node to the root in HashMap. We then begin with the other node and for each parent of this node, we check if this value exists in our HashMap. If it does, we have found the LCA.

My Answer

When solving this problem, we can leverage the structure of a binary search tree (BST). A BST is a tree data structure with two keys properties. Every node has at most 2 children. And for any node n, the value of all left children < the value of n < the value of all right children.

We begin at the root node with our two targets nodes. We’ll compare the value of the target nodes to the root node. There are three possible cases. (1) Both values of the target nodes are greater than the value of the root node. (2) Both values of the target nodes are less than the value of the root node. (3) One target node value is greater than the root node and the other is not.

In case (1), we’ll move to the right child of the root node and repeat the process there. In case (2), we’ll move to the left child. In these cases, we know the target nodes exist in one of these subtrees so we are getting closer to finding the lowest common ancestor. In case (3), we have found the lowest common ancestor.

This problem can be readily solved using a recursive solution. However, we can implement the same functionality iteratively using a Stack. This reduces our memory complexity without reducing time complexity. This implementation is shown below.

Code source here.

Closing Note

The above solution makes many assumptions and it is always best practice to clarify these assumptions with your interviewer. If nodes in our BST contain references to their parents, the problem becomes much simpler. It is also possible the definition of the ordering property may change. These assumptions should be clarified before a solution is written or discussed.

Suppose you propose the recursive solution and your interviewer asks for the iterative solution. It can be daunting to develop this new solution. However, you can draw a BST, work through your algorithm, and keep track of the Call Stack. Replace the Call Stack with your own Stack, and find a way to mirror the calls to the Call Stack. There may be other necessary modifications but this general process can put you on the right track.

Question 2: Given a sorted array, find the number of elements greater than some integer k.

Variants

• Given a sorted array that has been rotated, find by how many places the array has been rotated.
• Given a sorted array, find the first missing number. For example, the first missing number of [0, 1, 2, 3, 5, 9, 14] would be 4.
• Explain binary search to a ten-year-old.

What They’re Really Asking

• Do you know binary search? Can you identify when binary search should be used?
• Do you understand how to modify binary search for different situations? Can you apply the concept to novel problems?
• Do you understand search algorithms? Can you provide solutions that are optimal?

Tools for Our Answer

• We’ll define a sorted array as an array with an ordering property and way to compare elements e.g [1, 4, 13, 29] or [a, b, c, f].
• Whenever we have a sorted array, we should think to use binary search. Binary search is an algorithm used to determine if an element exists in a sorted array that runs in O(log N).
• We’ll define binary search by means of an example. Let’s say your Professor gives you a stack of problem sets and you want to find yours. Your Professor tells you this stack is in alphabetical order. If my last name is Miller, I’ll go about halfway through the stack of papers. If I see I’m at Smith, I know I’ve gone too far and I’ll look at the first half. If I see I’m at Johnson, I know I haven’t gone far enough and I’ll look at the second half.
• This is the idea behind binary search. We begin at the middle element. If our target element is greater than the middle half, we know the target element is in the second half of the array. So, we can repeat the process with our new smaller array. The comparison between the target element and our middle element determines in which subarray we continue our search.

Visualization of Binary Search Algorithm

• It is intuitive to write a recursive implementation of binary search but it is more efficient to use a while loop. The generic implementation of binary search is below. This returns the index of the target element or -1 if the element does not exist.

Binary Search to Return Index of Element. Code source here.

• For those unfamiliar with the return statement, this is Java’s ternary operator. It is a clean way to write short if/else statements. For those interested, more information can be found here.
• Let’s return to our original question. Suppose we want to find the number of elements in our sorted array that are greater than some integer k. All we really need to do is find the first element greater than k. For example, consider the array [1, 2, 4, 6, 8, 10, 12, 23] with k = 3. Once we find the element 4 at index 2, we know all further indices are greater than 4. This is implemented below.

Binary Search to Find Num Elements Greater Than some k. Code source here.

• For finding the rotation count of a sorted array, GeeksForGeeks contributor Rakesh Kumar has a solution here. For finding the first missing element of a sorted array, GeeksForGeeks has a solution here.
• Both of the above problems are solved using a modified binary search approach and are good exercises for fully understanding binary search.

My Answer

A naive solution would be to traverse down the array and find the first element greater than k. All subsequent elements would be larger so we could simply return (array_length - current_index). This runs in O(n) time. However, we are given a sorted array. We can leverage a modified binary search approach to solve this problem in O(log N) time.

We begin by assuming all our elements are less than k. We then run binary search. Consider the first iteration. If we see the element in the middle index is greater than k, we know that the number of elements greater than k is at most the midpoint index. We repeat this process until we no longer can. At this point, we know we have found the index where all elements to the left are less than or equal to k and all the elements to the right are greater than k. This algorithm runs in O(log N) time and is implemented below.

Code source here.

Closing Note

We’ve seen the concept of binary search manifest itself before. In part 3, we looked at binary search trees. These data structures are implementations of the binary search algorithm. We can readily take a sorted array and transform it into a binary search tree. This is an excellent problem for those interested. It can be helpful to chart out these problems using binary search trees when developing a solution.

Binary search is an interesting algorithm because it is incredibly intuitive. This is why interviewers may ask you to explain it to a ten-year-old. There are real-world examples everywhere — consider a stack of papers or looking up names in an address book. If software engineers are debugging a piece of code, they often use binary search as well. They can see if they bug occurs before or after the midpoint of a program and debug accordingly from there. If you are ever having trouble with the implementation, think of a real-world example.

Check out Part 7 here!

Questions? Comments? Send me an email at andrew.oliver.medium@gmail.com! I’d love to hear from you.