A General Note about Coding Interviews

As usual, I’d like to talk about the nature of coding interviews. They are very analogous to taking the SAT or GRE; sometimes they aren’t necessarily the best reflection of how you’ll perform at your job or in college, but more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

This is a common interview problem.
Asked by: Amazon, Google, Apple, Facebook, Netflix, Microsoft, and many more.

Problem Description

Given two sorted integer arrays A and B, merge B into A as one sorted array. Note, you may assume that A has enough space to hold additional elements from B, and the number of elements initialized in A and B are m and n, respectively.

Problem Solution

Let’s visualize our algorithm, below. By first moving items to the end of the first array, we can minimize the number of cells we need to move (i.e. time complexity) because the extra space is located at the end of the array. If we had started by moving items at the beginning of the first array, we would potentially have to move all of the items in the first array that came after that cell over by one.

A visual representation of merging to sorted arrays in place.

Now let’s take a look at the solution to the problem and break down the key aspects.

A solution to merging sorted arrays in place using pointers.

I chose to create three index variables i, j, and k to point to specific indices of interest. i corresponds to the current item index of the first array, starting with the last item. j corresponds to the current item index of the second array, also starting with the last item. Finally, k corresponds to the index of the cell that needs to be filled, starting with the last index of the first array.

After identifying our pointers, we can begin to iterate. We begin by traversing backwards through the first array. For each iteration, we compare the values at i and j from their respective arrays, and the larger item gets assigned to the cell at k. Each iteration we need to update the appropriate pointers. We decrement k on each loop and also decrement either i or j, depending on which array we took an item from. We also handle edge cases on line 7. If j is less than 0, that means the second array is empty and we only need to draw from the first array. Similarly, if i is less than 0, we only need to draw from the second array.

Conclusion

The main challenge of this problem is to identify the usefulness of moving items to the back of the array where the available space is. You can do it starting from the front, but it makes the logic and code much more complicated. Spending some time to think about time complexity implications like this will save you even more time when it comes to coding it out.