It’s no secret that, recently, I’ve been teaching myself Python. A couple of weeks ago, I wrote a Python script to convert a CSV file to an XML file, and that wet my appetite for more.
Earlier today, I discovered Anaconda from Continuum Analytics, which comes with IPython Notebook. Not only is it a really nice tool for learning Python, but you can also plot points! This would have made Calculus way more fun 15 years ago!
At any rate, I started fooling around with some basic list slicing, list comprehension and the functional favorites: filter, map and reduce. IPython Notebook made this incredibly simple. Wanting to tackle something a bit more complicated, I sought out a coding interview problem.
The problem is such that you’re provided an initial collection of integers, and you are to produce a sum of the highest, non-adjacent integers in the collection. It sounds challenging, but when you break it up into smaller pieces, it’s pretty trivial.
I started by building a min heap of the original collection such that I could pop off the largest values in order. A max heap is technically more appropriate, but the Python heapq module that turns a list into a heap only supports min. As for the values themselves, I simply inverted them by multiplying each by -1.
The index of each item is also critical in determining whether adjacent items have already been applied toward the sum. So instead of pushing the raw value onto the heap, I pushed a tuple containing the value and its index.
With the heap fully constructed, the next thing needed was some way of keeping track of which items were used toward the sum. I chose the simple solution of creating a list of boolean values, each initialized to
False, such that when an item at the same index is used toward the sum, its value is changed to
While popping items off the heap, each item’s neighbors are examined to determine whether it’s a candidate for the sum. If it is, its value is added to a final list, from which a sum can easily be reduced.
Here’s the full script:
Could this problem be solved other ways, either by reducing allocations or increasing speed? Quite possibly, but remember, this was just an exercise to flex my new Python muscles.