Hacker News had a nice link the other day to some dynamic programming practice problems. I think they’re fair game for an interview question. Personally, I wouldn’t remember everything from my algorithms course and I wouldn’t expect them to do so. That’s why we’re allowed to research things on the internet at work.

One thing I do remember is my Greedy algorithm and my dynamic programming (I love optimization problems.) Let’s tackle the first problem (it’s straightforward and easy.) Given an array of integers, find the contiguous subsequence with the greatest sum. First, consider the edge cases:

- If they’re all negative, the greatest subsequence will be a single element.
- If they’re all positive, the greatest subsequence will be the entire array.
- They’re all zero, any subsequence is a greatest subsequence.

Taken together they mean I can’t do any pre-optimization to reduce my work. I need an exhaustive search to find the maximum subsequence for each subsequence of length 1 to N. But in order to reduce the number of total calculations I do, I should also save each subsequence for reuse.

Here’s a naive solution:

def subsequence( myList, length ): amount = lambda index: (index, sum( myList[ index : index + length ] ) ) return imap( amount, xrange( 0, len( myList ) - length + 1 ) ) def maxSubsequence( myList ): maxVal = (1, 0, myList[0]) for length in xrange( 1, len( myList ) + 1 ): for start,value in subsequence( myList, length ): if( value > maxVal[2] ): maxVal = (length, start, value) return myList[ maxVal[1]: maxVal[1]+maxVal[0] ]

Perfectly acceptable in an interview. In a memory intensive problem this could very well be the ideal solution as we’re not caching previous results. Here’s a rendition of a dynamic programming answer:

def createTable( myList ): sequences = { 1:dict( enumerate( myList ) ) } makePair = lambda offset,start: (offset, sequences[start-1][start+offset] + myList[start+offset-1] ) extract = lambda length: ( makePair(i,length) for i in xrange( 0, len(myList + 1 - length) ) ) for i in xrange( 2, len( myList ) ): sequences[i] = dict( extract(i) ) #caching commences return sequences def maxSubsequence( myList ): maxVal = ( 1, 0, myList[0] ) for length, items in createTable( myList ).iteritems(): for start, value in items.iteritems(): if( value > maxVal[2] ): maxVal = (length, start, value) return myList[ maxVal[1]:maxVal[1]+maxVal[0] ]

Coincidentally, it appears that the naive approach is the “smaller” solution. (And yes, there’s probably a more concise functional approach to this problem.) As always, I’ll update a Scala solution shortly.

Advertisements

%d bloggers like this: