Blogging About Code and Giving Zero Fucks

Technical Interviewing 101: Merging 2 lists in Python

Amy Tsai
Amy Tsai
Sep 28, 2013 · 3 min read

To preface this post, I’d like to thank Garann, who’s blog post “How to Blog About Code and Give Zero Fucks” really pushed me to write about my code. Before reading this post, I never thought it was important for me to share my experiences as a developer. Every piece of code I’ve ever written, I’m pretty sure someone else has done in the past. I assumed that I couldn’t possibly have any valuable contributions as a developer/blogger since everything there is to know about Python, Java or any other coding language was already only a Google Search or a Stack Overflow post away.

I have spent the last month or so searching for the elusive “perfect internship” for Summer 2014 and I’ve already done in the ballpark of 15 interviews so far. I hope to share some of the wisdom I’ve gained from these interviews in a series of “Technical Interviewing 101 posts”.


The Question:

“Given 2 sorted lists of integers, can you merge them into one sorted list? Try to do this as optimally as possible”

Merging 2 sorted lists is one of those things that every programmer is supposed to know how to do, and most competent programmers can, in theory. Even though this seems like a really basic and overused programming test, I’ve been asked to do it way more often than expected. Knowing how to do this quickly and error-free in an interview can show that you’re prepared and also give you a confidence boost!

The Code:

First lets define our function mergeLists which will take 2 lists as input and output a new list.

def mergeLists(l1, l2):
output = [] // defining an empty list as output

To construct this new list, we will use a while loop to walk through each list. The condition I’m using is:

keep looping while both of the lists still contain something.

Then inside the while loop:

  1. Check the number at the beginning of both lists
  2. Remove the smaller of the two items
  3. Append that item onto the output list; repeat

We can do this because both of the input lists are already sorted, so to maintain that sorted order, we always want to always put the smallest number before any larger number.

while l1 and l2:
if (l1[0] < l2[0]):
output.append(l1.pop(0))
else:
output.append(l2.pop(0))

What do you do when one of the lists is empty? Append the non-empty list onto the end of your output. You know the list is already sorted, and all the numbers left must be larger than any numbers already in your output. And you’re done!

  if l1:
output.extend(l1)
elif l2:
output.extend(l2)
return output

Lessons Learned:

extend() vs append():

Python append() is used to add a single item to the end of the list and extend() is to concatenate two lists. I made the mistake of trying to append() the lists together at the end and got output like this:

(1, 2, 3, (4, 5, 6))

implicit booleanness of lists:

In Python, empty lists are implicitly “False” and non empty lists implicitly “True”. I did not know this when I first wrote my code, and was using a “hackier” method to check whether my list was empty or not.

if len(somelist) == 0:

But then, I read on Stack Overflow about implicit booleanness in Python! With this new found knowledge, I was able to make my code a lot cleaner and more “Pythonic”.

Conclusion

When I wrote this code, Python was not my strongest language. I had merged lists many times in Java which is actually more complicated. This was a really good exercise for me and I recommend, even with a strong understanding of how to merge two lists, to practice doing it in ALL of the languages you list on your resume. Happy coding :)

On Coding

Thoughts about writing code

    Amy Tsai

    Written by

    Amy Tsai

    Vivid-hair-hacker-extraordinaire | UC Berkeley non-grad | currently obsessing over fine writing instruments and dogs.

    On Coding

    On Coding

    Thoughts about writing code

    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade