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 `True`

.

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.

### Like this:

Like Loading...

*Related*

## Leave a Reply