Statically Typed

because Hindley-Milner rocks

Interview Questions

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:

  1. If they’re all negative, the greatest subsequence will be a single element.
  2. If they’re all positive, the greatest subsequence will be the entire array.
  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


This entry was posted on April 12, 2010 by in Intervew Questions, Python.
%d bloggers like this: