Why Do I Need to Know How to Reverse an Array?

The Technical Software Engineering Interview

Imagine you are a candidate for a software engineering job at a startup. Someone at your interview asks you to write a function that will reverse an array. Your immediate gut-response is "Why do I need to do that? I have array_reverse stupid!". As true and as pragmatic as this response may feel, it is the wrong attitude to have in the interview. Allow me to explain why.

The interviewer isn't asking you to re-invent the wheel here. Quite to the contrary. They are asking if you understand how the wheel works. If you have a modicum of common sense you might be wondering "Why don't they just come out and ask me that then?!". Well, because they also want to test your coding ability as well as your technical knowledge. Since writing code will likely be the primary role of your job, this makes a lot of sense from the interviewer's perspective.

Joel Spolsky puts this quite concisely in his article The Joel Test: 12 Steps to Better Code...

Would you hire a magician without asking them to show you some magic tricks? Of course not.

Writing good code requires a well rounded understanding of computer science fundamentals like data structures and algorithms. This common question is actually a pretty trivial data structures and algorithms question and if you can't solve it you really don't have a strong enough grasp of basic concepts that any good software engineer should. If you just don't want to solve it because you feel your resume should speak for itself then you really aren't doing yourself any justice in the interview. If you disagree, I strongly encourage you to keep reading and revisit your position by the end of the article.

It's not a trick question and it's not intended to trip you up. It's really just used in preliminary technical screenings to weed out the really low-quality candidates so that the interviewer can move on and focus their time on the more prominent candidates.

What's probably most important about this question is that the interviewer couldn't care less about you knowing how to write a function that will reverse an array. At a very high level, the question is aimed to establish a number of important base lines, which will allow the interviewer to thoroughly asses your qualifications.

  1. It begins to outline your technical knowledge surrounding the fundamental problems the code will solve
  2. It allows the interviewer to poke at your logic in deconstructing a given problem and constructing its solution
  3. You are presented with an opportunity to demonstrate your curiosity for learning and innovating

So just presenting a working set of code isn't actually the answer the interviewer is driving at, but merely the basis for opening a dialogue and commencing or stopping the interview.

Knowledge is passive

The interviewer can choose to take this question in multiple directions depending on the candidate's level of expertise and experience. Though to be fair the interviewer first needs some baseline for what that level is with each individual candidate and what matters most in the opening for which you are applying.

Since knowledge is passive - you may acquire it regardless of having taken action - it's apt to get you moving in order to see your knowledge at work. This is much like observing an athlete at a try out. Just having the athlete tell you what they would do on the field isn't likely as impactfull as seeing them in action.

For example, imagine I am applying for a job at Facebook where I am very likely to be dealing with problems at scale and where efficiency matters. The interviewer could ask me questions like...

  • What is the big O of this function?
  • How could you make this function more efficient?
  • Does an array of odd or even size change the implementation?
  • Does the arity of your function effect its performance characteristics (and if so how)?

Being able to answer these questions based on the code I've written will only solidify the interviewer's judgement. So be prepared for this part.

It's not enough to know which function/method call, in the standard library, you should use in order to solve such a well-solved problem. They could hire anyone with access to Google and a rudimentary understanding of the programming language to do that. Clearly that's not their ideal candidate.

The ideal candidate demonstrates both smarts and humility in the process of writing code. So let's say I write the following function to reverse an array in PHP...

function reverseArray(Array $array)
{
    for($i = count($array) - 1; $i; $i--) {
        $newArray[] = $array[$i];
    }
    return $newArray;
}

Yes, it works. It does the job effectively. However, that doesn't mean you've passed. That code only begins the dialogue the interviewer intends to open up through the interview process. Only now does the road unwind as they begin asking you question about what you've just written.

It's important not to take the interviewers questions as a personal attack from here on out. They are only trying to gather facts at this point and not necessarily making conclusive judgements. Being snobbish at this stage of the interview will likely get you a quick handshake and an escort to the elevator.

The first question they might ask you here is what is the computational cost (or big O notation) of this function? Your response had better be O(n) or a linear time. Next, the interviewer may ask you how you think you could reduce this cost, assuming they care about efficiency. Some may not. Some may be more concerned with just getting it to work well, first.

First, let's address the big O. The answer is yes, you can make the function O(n / 2) by transposing opposite ends of the array inwardly.

function reverseArray(Array $array)
{
    $s = count($array);
    $n = floor($s / 2);
    for($i = 0; $i < $n; $i++) {
        $x = $i;
        $y = $s - 1 - $i;
        $a = $array[$x];
        $b = $array[$y];
        $array[$x] = $b;
        $array[$y] = $a;
    }
    return $array;
}

What this does is demonstrate that you can refactor code and optimize for efficiency. It also demonstrates that you understand and know about the computational cost of your code. Again, this is putting passive knowledge into an active state in order to observe, within the confines of an artificial problem, how you might perform on the job.

Logic requires failure

Here's where your logic really comes into swing, however.

What happens if I hand you an array like this: array('foo' => 'bar', 'baz' => 'quix') where the keys are not numbered at all. Remember, in PHP the keys don't represent offsets since they are implemented as ordered hashmaps and not vectors. Albeit, this is a language-specific question, but the interviewer may be focused on this were this a highly specialized position that requires an expert understanding of a specific language.

The solution they are likely looking for is going to be something along these lines...

function reverseArray(Array $array)
{
    $left = $right = $array;
    reset($left);
    end($right);
    $x = true;
    $y = false;
    while ($x !== $y) {
        $x = key($left);
        $y = key($right);
        $a = $array[$x];
        $b = $array[$y];
        $array[$x] = $b;
        $array[$y] = $a;
        $x = next($left);
        $y = prev($right);
    }
    return $array;
}

OK, so now I get the elements in reverse order correctly, but the keys are different. Or at least, the values to which those keys belong is what's swapped. Still O(n / 2), but if I were the interviewer I could dive a little deeper with the candidate to explore the trade offs of this approach for efficiency vs. the less efficient approach which might give you more expected results, as in traversing the array backwards.

Though this depends on how much the interviewer feels it is beneficial to grill you on your understanding versus what they can already derive from your code. Clearly this isn't the code of someone who lacks an understanding of PHP, but someone that may or may not view a PHP array as an ordered hashmap vs a vector or contiguous block of memory.

We could dive even further into the memory implications of this function like does this function make three copies of the array? The answer in PHP is no, they are not deep copies, since $left and $right remain copies of the hashtable whereas $array will invoke copy on write.

Specifics of the language are not always what interests an interviewer, however. Sometimes just demonstrating a basic understanding of certain computer science fundamentals is enough. Other times they're looking for a lot more. If they provide specific guidance, like "if I told you your function copies $array how would you change it to not copy but modify the original array in place?", then you might want to take that and run with it. They are likely providing some underlying wisdom that will help you demonstrate to them that you do or do not posses a specific understanding/skill that they are looking to asses and/or can apply fastidious logic to existing or newly founded technical knowledge.

For example, you could answer by explaining that your function is non-destructive, meaning it does not modify the original input and instead returns a new array. The destructive version of that could take the array input as a reference, for example...

function reverseArray(Array & $array)
{
    $left = $right = $array;
    reset($left);
    end($right);
    $x = true;
    $y = false;
    while ($x !== $y) {
        $x = key($left);
        $y = key($right);
        $a = $array[$x];
        $b = $array[$y];
        $array[$x] = $b;
        $array[$y] = $a;
        $x = next($left);
        $y = prev($right);
    }
}

This not only demonstrates to the interviewer that you have an understanding of the memory implications involved in your code, but that you also have a strong understanding of the language itself, and the functional paradigmatic concept of destructive vs. non-destructive functions.

Curiosity certainly did not kill the cat

Have you ever heard the proverb "Curiosity killed the cat"? Surely this is as true as the notion that a cat has nine lives. The phrase actually originates from British playwright Ben Jonson in his 1598 play, Every Man in His Humour, as saying "...Helter skelter, hang sorrow, care will kill a cat, up-tails all, and a pox on the hangman.", unlike the modern spin that curiosity is to blame. I posit that curiosity is actually what allowed the feline to become the king of the jungle.

In the same regard, I believe that curiosity is what allows an engineer to venture far, and challenge the prevailing wisdom, arriving at innovation. Innovative thinking is typically derived from an engineer's curiosity and logic being applied well to their deep technical know-how given an interesting enough problem set.

This part is extra, but if you really want to win over your interviewer you have an opportunity to stake out and defend a position of innovative thinking by being curious enough to seek a better implementation.

Allow me to elaborate by expounding on the aforementioned destructive vs. non-destructive versions of the function and hypothesizing that there can be a non-destructive version that does not invoke copy-on-write semantics in PHP and allows for both keys and values to be reversed with an O(n / 2) time constraint and without the memory implications.

Shit, now I actually have to prove it? Can't you just take me for my word and believe that I am an innovative engineer? Fine...

function reverseArray(Array $array)
{
    end($array);
    while (($k = key($array)) !== null) {
        yield $k => $array[$k];
        prev($array);
    }
}

Wait a minute... How is this O(n / 2), the brilliant interviewer asks? Well, this is my opportunity to defend my position of innovation as I explain that now the function no longer behaves like a regular function, requiring us to first store the output somewhere and then consume it, thereby requiring additional O(n) time. With a generator implementation you can actually consume the output of the function as you traverse the result, but without preventing you from storing the result and reusing it somewhere else. Since the original version of this function was really O(n + n / 2) when you iterated over the result, by eliminating the extra n, we have technically reduced its cost by O(n / 2). Actually, more so, since calling it n times will have no real residual cost beyond iteration. There is also no copy-on-write semantics or more added memory beyond each iteration.

If you've already gotten here on your own then congratulations! You have accomplished interview nirvana.

Wait a minute... did I just re-invent a better wheel? Well, I suppose I did. Now ask yourself, if you were the interviewer and you had one candidate who felt array_reverse is the obvious answer to this question and writing this function is a waste of their time, and another more open minded candidate walked in and came up with the generator implementation, who would you hire?

This is not to say that you will and should have to re-invent every wheel on the job, but it's important to recognize that knowing how to use the wheel, and understanding how the wheel works enough to the point that you could potentially design a better wheel for a specific use case, are very different things.

return true;

By now, if you haven't already, I would hope, you have realized that the question "Can you write a function that reverses an array?", actually has far more depth and holds a lot more weight about your abilities as a software engineer than you may have originally thought. Now, obviously this isn't the only question an interviewer would ask you, but questions like these are narrowly focused for a reason.

I've seen many candidates under the misled impression that these questions are too contrived or too "impractical". Just read the interview reviews on Glassdoor for the ones complaining about how they felt the company was too focused on the "computer science way of doing things" and not practical enough. Almost all of them don't get an offer. There's a reason for that.

It turns out such questions are actually very effective at weeding out the low quality candidates in the interview process. A candidate that pursues a solution in the interview with this same vigor and steadfast logic will more than likely do that on the job. A candidate that can't or doesn't want to isn't likely to perform any better on the job.

It is painfully obvious to the interviewer that you are not a good fit if questions like this dissuade you, because the solution is the smallest tip of the iceberg. What remains hidden underneath is what's really going to make the difference between you and the other guys or gals competing for that open seat.