Blogging About Code and Giving Zero Fucks
Technical Interviewing 101: Merging 2 lists in Python
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”.
“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!
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:
- Check the number at the beginning of both lists
- Remove the smaller of the two items
- 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 < l2):
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!
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”.
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 :)