Stock Prices

February 14, 2017

Today’s exercise is a classic of both algorithm classes and corporate interviews:

Given a list of daily stock prices for a month, find the day on which you can buy a stock and the day on which you can sell the stock that gives the maximum gain.

Your task is to write a program that finds the optimal starting and ending dates for stock purchase and sale. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

10 Responses to “Stock Prices”

  1. Paul said

    In Python.

    def optimal(rates):
        low, optvalue, optlow, opthigh = float('inf'), 0, None, None
        for curr in rates:
            if curr < low:
                low = curr
            elif curr - low > optvalue:
                optvalue, optlow, opthigh = curr - low, low, curr
        return optlow, opthigh
    
  2. Jussi Piitulainen said

    Quadratic Python, recommends a shortest interval of days.

    from itertools import combinations
    
    def best(prices):
        '''Return the day (a 0-based index to prices) to buy, and the day to
        sell, to gain the most in the given days, in a shortest time.
    
        '''
        def key(be):
            b, e = be
            return prices[e] - prices[b], b - e
    
        return max(combinations(range(len(prices)), 2), key = key)
    
  3. Paul said

    Another (linear) Python solution.

    from itertools import accumulate, tee
    def optimal(rates):
        r1, r2 = tee(rates)
        lows = accumulate(r1, min)
        return max(zip(lows, r2), key=lambda x: x[1]-x[0])
    
  4. Paul said

    A divide and conquer version in Python.

    def divide_and_conquer(rates):
        def opt(rates):
            n = len(rates)
            if n == 1:
                return 0, rates[0], rates[0]
            L, R = rates[:n//2], rates[n//2:]
            left, right = opt(L), opt(R)
            buymiddle, sellmiddle = min(L), max(R)
            middle = (max(0, sellmiddle - buymiddle), buymiddle, sellmiddle)
            return max(left, right, middle)
        return opt(rates)[1:] if rates else (None, None)
    
  5. Here is my implementation in Julia. Interestingly, it worked on the first attempt, so the problem was probably not as challenging as I thought…

    function spa{T best
    best = z
    buy = i
    sell = j
    end
    end
    end

    return best, buy, sell
    end

    One known limitation of this algo is that it is possible to have multiple cases that yield an optimum profit. This algo will only yield the first such solution, however.

  6. Here is my solution again, since the form truncated it for some reason… (if the problem persists, maybe the website is up for some maintenance!)

    function spa{T best
    best = z
    buy = i
    sell = j
    end
    end
    end

    return best, buy, sell
    end

  7. Jussi Piitulainen said

    Zack, try the sourcecode tags (square brackets) around the code, any lang attribute (lang=”text” works, lang=”python” adds funny colours). It’ll preserve indentation and it’ll take less-than, greater-than signs literally. See the HOWTO link on top of the page.

  8. Thomas said

    Your linear solution doesn’t work, and this problem can’t be solved in both linear time and space. To see the problem, add a new low price after the correct solution in the list. For example, given your test data, add a 64 somewhere after the 150. Buy at 65, sell at 150 is still the correct answer, but your linear algorithm will claim you should buy at 64 and sell at 149, which you cannot.

    What you can do is to use an O(n log n) solution: when you find a new possible low price, scan ahead in the list to verify that there exists an element >= (+ buy profit). Alternatively, you could use an optimistic algorithm, and instead of scanning ahead, assume that your new low price will be valid but save a continuation to restart with the old buy price. If you reach the end of the list and never found a sell price to justify your buy price, backtrack to your continuation.

  9. programmingpraxis said

    @Thomas: You are correct that my solution doesn’t work; it resets the minimum buy price when it shouldn’t. But there is a linear-time and constant-space solution:

    (define (buy-sell xs)
      (let loop ((xs (cdr xs)) (lo (car xs)) (hi (car xs))
                 (min-lo (car xs)) (max-d 0))
        (if (null? xs) (values lo hi max-d)
          (let* ((min-lo (if (< (car xs) min-lo) (car xs) min-lo))
                 (d (- (car xs) min-lo)))
            (if (< max-d d)
              (loop (cdr xs) min-lo (car xs) min-lo d)
              (loop (cdr xs) lo hi min-lo max-d))))))
    
    You can see the program in action, with 64 added to the end of the list of stock prices, at http://ideone.com/UvcdJ9.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: