I’ve been toiling away these past few months learning the inner workings of Bitcoin, as well as brushing up on Rust, Flask, Django, and pure Python. I bought a book called Elements of Programming Interviews in Python and boy is it terrible. Half explanations, bad explanations, obfuscated code labeled “Pythonic”. I think if you found a way to publish just the prompts, you’d have extracted the last bit of value in this book.
That being said, I’d like to show you one of the problems and how hilariously bad this book is. The prompt is to come up with a function that returns true or false based on whether a passed in singly-linked list is palindromic. If you haven’t worked with singly linked lists, they’re made up of nodes that have a Data property that can hold anything and they have a Next property, which points to the next node in the list. It’s a pretty poor data structure, I think, but does make for some very difficult problems since they are self-contained objects. You can’t easily index or work on the entire list; you have to manage individual nodes. Anyways, onto the solution.
from ListNode import ListNode
#You need to create the ListNode class yourself but like I said,
#it doesn't inherit from anything and just has a Data and Next field.
#the List terminates when you hit a node with None as its Next property.
def is_linked_list_a_palindrome(L: ListNode) -> bool:
slow = fast = L
while fast and fast.next:
fast, slow = fast.next.next, slow.next
first_half_iter, second_half_iter = L, reverse_list(slow)
while second_half_iter and first_half_iter:
if second_half_iter.data != first_half_iter.data:
return False
second_half_iter, first_half_iter = (second_half_iter.next, first_half_iter.next)
return True
I could give you some test cases so you can figure out the problem but I think it’s fairly obvious. There’s no fucking reverse_list function defined. They just made up a function name and threw it in. I thought maybe it was a typo, because there was a previous exercise on reversing a sublist of the entire list called reverse_sublist, but that can’t be it for a number of reasons:
- That function requires the start and end points of the reversed sublist, so if we want to reverse the entire sublist, we need to first find the index of the tail node.
- That function (as well as most of the functions for singly-linked lists) modifies the list in place by altering the Next property. So you most definitely can not iterate over it frontways and backways using that.
Nope, they just straight up said who cares and claimed they achieved O(n) time and O(1) space. Such a ridiculous thing to do and they still put their name on it lol. Anyways. The rest of the function will work if you can implement a reverse_list that duplicates before reversing. That will of course put us into O(n) space and O(2n) time. I don’t think there’s any other way to do it that doesn’t go into O(n2) time.