Databases
StackOverflow2013
Postsdbo
POFind buy/sell prices in array of stock values to maximize positive difference
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind buy/sell prices in array of stock values to maximize positive difference
    text
    copied!<p>Got this question in an interview today, and its optimized solution stopped me cold (which blows, because I really wanted to work for this company...)</p> <p><b>Given a single array of real values, each of which represents the stock value of a company after an arbitrary period of time, find the best buy price and its corresponding best sell price (buy low, sell high).</b></p> <p>To illustrate with an example, let's take the stock ticker of Company Z:</p> <pre><code>55.39 109.23 48.29 81.59 105.53 94.45 12.24 </code></pre> <p>Important to note is the fact that the array is "sorted" temporally - i.e. as time passes, values are appended to the right end of the array. Thus, our buy value will be (has to be) to the left of our sell value.</p> <p>(in the above example, the ideal solution is to buy at <code>48.29</code> and sell at <code>105.53</code>)</p> <p>I came up with the naive solution easily enough with O(n<sup>2</sup>) complexity (implemented in java):</p> <pre><code>// returns a 2-element array: first element is the index in the argument array // of the best buying price, and the second element is the index of the best // selling price which, collectively, maximize the trading return // // if there is no favorable trading (e.g. prices monotonically fall), null is returned public int[] maximizeReturn(ArrayList&lt;Double&gt; prices) { int [] retval = new int[2]; int BUY = 0, SELL = 1; retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively for (int i = 0; i &lt; prices.size(); i++) { for (int j = i + 1; j &lt; prices.size(); j++) { double difference = prices.get(j).doubleValue() - prices.get(i).doubleValue(); if (difference &gt; 0.0) { if (retval[BUY] &lt; 0 || difference &gt; prices.get(retval[SELL]).doubleValue() - prices.get(retval[BUY]).doubleValue()) { retval[BUY] = i; retval[SELL] = j; } } } } return (retval[BUY] &gt; 0 ? retval : null); } </code></pre> <p>Here's where I screwed up: there's a <b>linear time O(n) solution</b>, and I completely bombed in trying to figure it out (yeah, I know, FAIL). Does anyone know how to implement the linear time solution? (any language you're comfortable with) Thanks!</p> <p><b>Edit</b></p> <p>I suppose, for anyone interested, I just received word today that I didn't get the job for which I interviewed where they asked me this question. :(</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload