02 Aug 2016 05:00

Rather interesting, and perhaps atypical, questions tend to get asked in technical programming interviews. Often, the goal of the interviewer is to present a problem the job candidate has never seen before. In doing so, the candidate will be forced to genuinely think of a new solution on the spot rather than recite a memorized answer. Why do they ask these questions, and how can you better prepare?

# Why such weird questions?

The questions I'm talking about are a little more nuanced than your typical "find the nth Fibonacci number" or "implement a linked list" problems. Undergraduate computer scientists in university are specifically trained for problems like that, so to an interviewer, those problems aren't particularly interesting. Rather, we're talking about weird, nebulous things like:

• How do you insert into a singly-linked list when you do not know its ends?
• Implement an algorithm for determining if a point (x, y) is inside of a pentagon.
• How would you implement an infinite grid on a finite computer?

Answers are not immediately obvious. As a result, candidates tend to get nervous about technical interviews, mainly for any of the following reasons:

• What if I cannot solve the problem?
• What if I give a solution that works, but it's a bad solution?
• What if others give a better solution than me?
• What if it takes me too long to arrive at a solution?
• What if I need too many hints?

When I went through my first set of technical interviews, I asked myself these same questions, uncertain if my knowledge was going to be enough. In hindsight, these questions are actually all focusing on the wrong idea. Notice that they are all very solution-centric. What if I cannot *solve* the problem, or what if I give a bad *solution*?

The truth is, the interviewer is not so much interested in your solution. The interviewer is actually interested in the process, the type of problem-solving you employ to obtain a solution and the creativity it took to get there. That's why the questions they ask can be unfamiliar and honestly downright difficult. If the interviewers can force you out of your comfort zone, then your answer will be entirely from you and not from a professor or a website (or a silly blog like this blog).

# How to improve

My guess is that if you have been reading other advice columns, you have been told to practice, practice, and practice. In my experience, practice is definitely one of the best ways to prepare for technical interviews. If you find a number of different problems to practice, then even if the interviewer gives you a one-of-a-kind question, you might be able to relate to a previous problem you had already tried.

But if you want some different kind of advice, I suggest trying some divergent thinking when solving problems. What on earth is that?

Divergent thinking is a creative process that aims to find many different solutions to the same problem. Usually, when presented with a problem of some kind, the "obvious" solution is what we think of first. However, the first idea is not always the best idea, and so by forcing ourselves to come up with other ideas, we increase the likelihood of finding a solution better than what we would otherwise have found.

When it comes to technical interview questions, rather than optimize the first thing that comes to your mind, think of a few alternatives. One of the alternatives might be better than the first idea, and sometimes, mixing the different ideas can lead to an even better solution. This process is called divergent thinking because we intentionally branch out into different solutions.

The diagrams below compare the familiar approach to problem solving with divergent thinking. Here, green circles represent potential answers. In vertical thinking, you start with an idea and improve it to make it a viable solution to the problem. Occasionally, this is met with dead-ends, as represented with the red circle. On the other hand, divergent thinking seeks to widen the possibilities by offering more than one approach. In doing so, you might find other solutions derived from combining previous ones.

In the interview, divergent thinking comes in handy for two reasons.

First, let's say you have no clue how to solve the problem given to you. If you start immediately brainstorming a few ideas and talk through some of their advantages and disadvantages, you might come across some principle that helps you find a real solution. Even if the question is of the sort where only a single solution exists, having multiple approaches can help you find that solution more quickly.

Second, let's say you already know the answer to the question. You can explain your solution to the interviewer and then think of a few different alternatives, explaining why the alternatives are inferior to your proposed solution. In doing so, you have demonstrated to the interviewer that you are open-minded and thorough.

I have seen the quality of answers improve when students are asked to come up with multiple alternatives. I recommend trying divergent thinking on some sample problems and seeing where it takes you.

# Divergent Thinking: An Example

Let's see how we can use divergent thinking in an interview question. I am going to assume you are familiar with arrays and linked lists, and I'm not going to describe all of the details of the solutions I provide here (it would be way too long). Let's say the question was as follows:

How would you implement an infinite grid on a computer? The coordinates (x, y) can only be integers, and each cell in the grid stores a color, with black being the default color.

Immediately, we are tempted to think of arrays. After all, arrays are very good at representing grids. Unfortunately, arrays are limited, and we need an infinite grid. It seems impossible, but perhaps there are ways we can manipulate the array in order to at least simulate the idea of infinity.

Before describing that process, though, let's use divergent thinking and explore at least one other option: linked lists. Using a linked list, we can keep track of only the non-black cells.

Now that both ideas are on the table, we can go into each in a little more detail and explain their pros and cons.

## Array

First, the array. For the array, we would track the colors by initially setting every element in the array to black. Every time we set the color of a coordinate (x, y), we find the corresponding index in the array and set its value. In order for the array to be "infinite", we need to a way to expand the array every time a coordinate outside of its range is accessed. Therefore, when a coordinate out of bounds is accessed, we will expand the array to exactly encompass that coordinate and all of the coordinates it supported before.

• Pros: We initially thought of arrays because they allow us to have instant access to its cells. We can find the color of (x, y) instantly. In computer sciency terms, we say element access is in $O(1)$.
• Cons: Unfortunately, using an array means we have a ton of wasted space. All of those black cells in the array aren't encoding anything useful because black is the default color. In other words, if a cell didn't exist in the array, we would assume the cell was black. Therefore, the array method wastes a ton of space.

Next we will think about the linked list. The list starts off empty. Every time a non-black cell is declared, we add the cell to the list. Therefore, the list only ever stores non-default cells. Oh, and to make adding fast, we don't care about the order of cells in this list. Our list could very well look like:

(1, 2, red) — (-5, 6, orange) — (12, 3, red) — (0, -1, blue)

• Pros: The linked list will only use memory it needs. No cells are labeled as black, and therefore no memory is wasted.
• Cons: Finding the color of a given (x, y) cell is not very simple anymore. To find the color of a cell, we have to look through the entire list to find the cell with the matching (x, y) coordinate. This means that for lists with millions of colored cells, it can take millions of calculations just to find the color of a single cell. In computer science, we say this operation scales in $O(n)$, which is considerably worse than the arrays.

## Chunk List

At this point, the interviewer might ask for which strategy is best. However, let's think of one more idea and see where it takes us. What happens if we combine both arrays and a linked list? Let's call it the chunk list.

In the chunk list strategy, we maintain a linked list of chunks rather than individual cells. Each chunk is a finite $w \times w$ array representing some area of the coordinate field. This can represent an infinite grid since every time we access new territory, we just need to add the appropriate chunk to the chunk list.

• Pros: We inherit the pros of both the array and the linked list. When we need to get the color of a cell, we first need to find the correct chunk which contains the cell. From there, accessing the actual cell itself is simply an array access operation. The number of chunks in the chunk list can be smaller than the number of live cells, and therefore the time it takes to get the color of a cell will be faster than the linked list option but slower than the array.
• Cons: We also inherit the cons of each strategy. For instance, since we now maintain a list of arrays, some memory is going to be wasted storing black cells.

## So which is best?

In the end, the interviewer will ask which we think is the best solution. As is usually the case, selecting the optimal structure depends on the situation, and in the actual interview, you would describe these situations and when you'd use each structure.

In any case, by using some divergent thinking, we were able to analyze multiple solutions and even synthesize a new data structure (the chunk list) from two existing data structures. Notice that we didn't go into several ideas; we chose three and provided some good quality depth. Really, the important thing is that you don't get fixated on one particular solution. Be exploratory!

# Final Remarks

Of course, every interview is different, and what you will be asked depends on the company. I have been to some interviews where all they asked were language-related questions, like how to do certain things in C++. And on the flip side, I've been to interviews where the questions were mostly open-ended, like the ones on this post.

In the end, the interview is about you. Don't be afraid to be you!