Coding Interview Problems: Reversing a List (Python)

List or array manipulation questions are quite common in coding interviews. One type of manipulation you may be asked to perform is a reversal of the list: in other words, putting the list in reverse order.

In Python, we actually have a built in method which takes care of reversing a list, so your first step should definitely be to ask if you can make use of the built in reverse method.

base = [1, 2, 3, 4, 5]
base.reverse()

Even if your interviewer says, "no", you've at least demonstrated that you know this method exists.

So, let's imagine the interviewer says they want to see a custom solution. How do we approach this question.

Talking Through the Problem

A big part of interview questions like this is reasoning your way through the problem. What do we have to achieve? What are the steps we'll take to achieve that goal? How do we verify that the solution works?

Let's start by making this into a concrete problem, rather than something abstract. If we have the following list:

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]

What we want, is for it to end up like this:

numbers_reversed = [9, 8, 7, 6, 5, 4, 3, 2, 1]

One perfectly valid way we might want to go about this is to remove items from the beginning of the list and tack them onto the end, until we've repeated this process as many times as items exist in the list. Another option might be to take the items from the end and repeatedly add these final items to a new list.

In the list above we have 9 items, and we can figure out the length using len, which means we can use the list length as a termination condition for a loop.

Python also has a method called pop which both removes an item from a list and returns it. This is clearly very handy for our situation, because we want to use this value again, probably as part of an append method. By default, pop removes the final item in a list, so we won't need to provide any arguments.

Each time we get a value returned from pop, we know it's the current final value of the list, so if we repeatedly append these final values to a new list, we should should end up with a list in reverse order.

Using our concrete example, the first value returned by pop would be 9, so this would be the first value we append. The next pop value we append would be 8, and so on and so forth, until we reach 1, which is the final value added to our new list.

Writing the Code

Now that we've talked about the solution, the actual code isn't too challenging.

We can create a new empty list called reversed_list, but we should also create a copy of the base list so that we can check against it later. Remember that pop will consume values from the original_list, so when we're finished, it will be empty.

For the actual loop, we're going to keep track of the length of the original_list, which, as I just mentioned, will get consumed as we repeatedly call pop on it. We'll keep repeating the loop until there are no more items to pop.

For each iteration, we get a new item returned by pop and store it in a final_item variable, which we then use an an argument to the append method we call on reversed_list.

base = [1, 2, 3, 4, 5]
original_list = list(base)
reversed_list = []

while len(original_list) > 0:
    final_item = original_list.pop()
    reversed_list.append(final_item)

Feel free to test it yourself, but this solution should work perfectly fine.

If you prefer, you can make a little shorter by removing the assignment to final_item, putting the pop method directly inside the append method.

base = [1, 2, 3, 4, 5]
original_list = list(base)
reversed_list = []

while len(original_list) > 0:
    reversed_list.append(original_list.pop())

The result works exactly the same, but you may find this less readable.

Using Black Magic

Our solution above is perfectly fine, but there are some fancy tricks you can use to solve this problem as well. One solution is using slices like so:

original_list = [1, 2, 3, 4, 5]
reversed_list = original_list[::-1]

This is a really cool solution. It's incredibly short, and it doesn't consume our original list. The problem is, this syntax tells you absolutely nothing about what it does if you don't know about slicing. Luckily our variables have names which make everything incredibly explicit, but this isn't always the case.

Please don't ever use this in your actual code, at least not for lists. There is generally no excuse for using this over just using reverse. However, this trick is really useful for strings, or tuples, where you don't have nice built in methods for reversing order. If you want to learn more about how awesome slices are, take a look at our previous posts on this topic: Part 1, Part 2.

Using Sorted

There's also another one-liner solution available to us using sorted, but again, I don't recommend ever using it in the wild.

One benefit that sorted has over something like the slice syntax is that it at least makes a lot of sense conceptually. We're just sorting the list into reverse order.

base = [1, 2, 3, 4, 5]
original_list = list(base)
reversed_list = sorted(original_list, key=lambda x: base.index(x), reverse=True)

Unfortunately, the implementation isn't quite that straightforward. We have to use a lambda function in order to let sorted know we want to sort based on index, rather than the values themselves.

Overall, I don't think this is a good solution to the problem. Our while loop is of comparable length, and is far easier to read and understand. We could take that solution to even a Python beginner and they could figure it out relatively easily. That's not the case here.

Update: One of our readers pointed out something I'd completely overlooked in this article: lists with duplicate elements. Because the index method finds the index of the first instance of a given value, the solution using sorted will become unreliable for lists with duplicate elements.

Thanks, Mark!

Testing Our Solutions

Throughout I've made sure to preserve the original list items in their original order, because this means we can test whether our solutions work. Now we just have to figure out how we do this.

Some useful things to know about lists

Lists are ordered by index, so we can talk about the content of our list by referring to an item at a given index.

Given the lists we had in the beginning:

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
numbers_reversed = [9, 8, 7, 6, 5, 4, 3, 2, 1]

In the numbers list the item at index 0 is an integer object with the value 1, while in numbers_reversed the item at index 0 is an integer object with the value 9.

We can also refer to items in a list using negative indices, where -1 refers to the last item in the sequence, -2 is the penultimate item, and -3 is the antepenultimate item, etc. For a list of length n, the first item can be accessed by using either a reference to index 0 or -n.

There's also a relationship between an item's current index, and its index if the list were reversed. Knowing this will let us programmatically check the results of our list reversal.

For an item at a given negative index, its new positive index will be absolute value of the negative index (how far it is from zero) - 1.

For an item at a given positive index, it's new negative index will be its current positive index plus 1, all multiplied by negative 1.

Written in code, these relationships look like this. Imagine we want to check whether the index 2 (i.e. number 3 inside the list) is in the correct place once the list has been reversed:

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
numbers_reversed = [9, 8, 7, 6, 5, 4, 3, 2, 1]

index_to_check = 2
negative_index = (index_to_check + 1) * -1  # -3
correct = numbers[index_to_check] == numbers_reversed[negative_index]

print(correct)  # True

Creating a Test Function

Using this information, we can write the following function to check everything ended up where it was supposed to go:

def check_reversal(original_list, reversed_list):
    for index, item in enumerate(original_list):
        negative = (index + 1) * -1
        if reversed_list[negative] != item:
            print(f"Element {item} was not located at the expected index")
            break
    else:
        print("List reversed successfully")

We take in two lists as arguments, though it actually doesn't matter which order we pass them in: the reverse of the reversed list is the original list after all, so our checks should work regardless of order.

We take the first list and call enumerate to grab the item and index at the same time. We convert the current positive index to the negative index we expect for the item in the reversed list and assign this values to new_neg.

We perform a check to ensure the item ended up in the correct place in the new list, and break the loop if we find a misplaced item, printing a message in the console at the same time.

If the loop runs to completion, the else block executes, letting us know that the list was reversed successfully. If you're not familiar with this for / else syntax, we have a short Python Snippet post on this topic, but you can also find more information in the official docs.

Read our introduction to unit testing post to see how we would write tests for our list reversal function.

Wrapping up

Thank you for reading. I hope you've learnt something in this post!

Got any questions? Tweet at us. Consider joining our Complete Python Course for more Python goodness, or check out our Automated Software Testing with Python course for a deeper focus on testing Python and web applications.