A General Note about Coding Interviews

Algorithm design is often a key part of a coding interview for a software engineering position. Some companies rely on them more than others, but for the larger tech companies, they are paramount. So even though they might not be the best reflection of how you’ll perform at your job and in your career, you still need to practice them, understand the underlying patterns and principles, and be able to discuss their performance.

Problem Source / Inspiration

Cracking the Coding Interview
Asked by: FAANG

Problem Description

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Problem Solution

When solving any algorithm problem, the first thing you should do is build a strong mental model. If your mental model is flawed, your code will be, too. So we’ll be solving this problem in a “layers” approach. We’re going to start on the outside and work our way in until we’ve rotated every cell appropriately. Take a look at the illustration below to help build your mental model.

I’ve color-coated the various layers to help distinguish them. We’ll first work our way through the red layer until we’ve rotated all of the elements. Then we’ll rotate do the same for the orange layer. And finally, we’ll arrive at the green layer and a rotation here would actually produce the same result so we’ll leave it as is. This pattern will work for all size matrices and both even and odd side lengths. Go ahead and test out this algorithm logic with a few different cases to help bolster your mental model. Try visualizing how this would play out with a 6 x 6 matrix, a 2 x 2 matrix, and even a 1 x 1 matrix for completeness’ sake.

This layered approach is just the beginning of our algorithm. Let’s now visualize how we’ll approach rotating each cell within each layer.

The illustrations above show how we’ll start iterating through the length of each side and transfer the cells to their respective locations. These two illustrations are just the first and second steps of this process. We’ll continue to swap cells until we complete the layer, and then we’ll continue through the rest of the layers with the same subroutine.

If you’re like me, you will get to this point and think that your mental model is solid and you’re ready to code. However, it turns out that there’s a small, fixable problem with this pattern. Can you spot it?

Let’s say we’re at the 2 cell. We want that value to be where the 10 cell is, so we overwrite the 10 cell, and now it reads 2. Next, we want the 24 cell to read 10, but we already overwrote the 10 cell (remember, now it reads 2). This is a small, fixable problem. We need to keep a reference to some of our numbers so that we can overwrite them in place. I’ll illustrate that below to help solidify your mental model.

The left matrix illustrates us keeping reference to the top row. Then, on the right side, we show how we’ll actually replace each cell. We’ll start at the 16 cell and replace the 2 cell value. Notice our problem from before is solved because we still have reference to the original value that was there. Then we can replace the 16 cell value with the 24 cell and the 24 cell value with the 10 cell. Finally, we’ll grab the 2 value from our stored reference and replace the 10 cell with it.

Now that you have a good mental model in place, I’ll show you how I codified my algorithm into JavaScript.

The code isn’t too complex once you have a strong understanding of what we’re trying to do. The outer loop iterates through the layers while the inner loop iterates through the cells in the current layer. There are a couple of small things to note here:

1. We make a copy of the values of the top row and store them in a new row array, rather than just storing a reference to the entire row. I do this because we are overwriting the matrix in place, so if we don’t store a new copy and simply store a reference, we’ll run into the same overwriting problem we talked about before.
2. We copy over the cells in a specific order so that we don’t overwrite a cell before we need to copy it over. We start at the left side and work counterclockwise through the sides.

Conclusion

A key aspect to most problems where you need to modify a data structure “in place” comes down to keeping a reference to information in a way that uses less memory (i.e. space complexity) than if you were to just create a whole new copy of the data structure. In our case, we stored reference to one row instead of the entire matrix.

These problems can seem daunting at first, but once you break them down into smaller chunks and clarify your mental model, the code practically writes itself. Take a minute to make sure you fully understand what we did here and let me know if you have any questions in the comment section.