17

I got a question on an algorithm question I got in an interview and I can't seem to figure it out. I understand how it should work, but can't get it sorted algorithmically.

So assume a firm trades oil barrels and is only able to retain one oil barrel at a time. Assume the company knows the price per barrel for each and every day in a year. So its passed into as an array. How can one write an algorithm to find when to buy and sell?

Here's an example for just 5 days for simplification: 70 74 73 72 76, for days Monday through Friday respectively.

The best thing to do here is to to buy on Monday (70) sell on Tuesday (74) and then buy on Thursday (72) and sell on Friday (76). Should that be approached recursively? I really want to solve this.

Thanks,

Christian Ammer
  • 7,464
  • 6
  • 51
  • 108
darksky
  • 20,411
  • 61
  • 165
  • 254
  • 1
    this is the most common and obvious question they ask u in any investment firm. If you couldnt answer this in interview, then u didnt research and prepare enough..see the uplicate – Suraj Chandran Sep 14 '11 at 17:28
  • @Suraj Chandran I'm used to more mathematical/CS problems. Now I am trying to get into more financial with CS/Math related problems. How do you find such duplicates that fast I researched for a while on stack overflow for a similar question. – darksky Sep 14 '11 at 17:29
  • 6
    That doesn't look like a duplicate to me, the linked question only has you find one buy/sell. – Mark B Sep 14 '11 at 17:30
  • @Navefc...i work with an investment firm:( ...anyway, just search for "maximize sell buy algo" – Suraj Chandran Sep 14 '11 at 17:31
  • 1
    @Suraj Chandran: This is not a duplicate IIUC. The other question wants to maximise one deal, this one allows more than one. – jpalecek Sep 14 '11 at 17:32
  • similar duplicates: http://stackoverflow.com/questions/7086464/interview-question-maximum-single-sell-profit – Suraj Chandran Sep 14 '11 at 17:34
  • Its not an exact duplicate. I believe a discussion would be nice here. – darksky Sep 14 '11 at 17:35
  • similar duplicates: http://stackoverflow.com/questions/6666776/given-a-series-of-stock-prices-in-an-array-pick-when-to-buy-and-when-to-sell-to – Suraj Chandran Sep 14 '11 at 17:36
  • I take it you're looking for **non-overlapping** holding periods (i.e. you can't buy, then buy more, then sell and finally sell again)? – NPE Sep 14 '11 at 17:38
  • Yes. You can just buy one barrel at at a time. – darksky Sep 14 '11 at 17:41
  • If you can only buy one barrel at a time, then why should we not buy a barrel on every day except the last? So I assume what you really mean here is that you may only hold on to one barrel. – harold Sep 14 '11 at 20:26
  • Yes - sorry I meant you can hold on to one barrel at a time. – darksky Sep 14 '11 at 21:02

6 Answers6

11

I assume you want to maximise your profit, right?

In that case, you just buy at local minima and sell at local maxima, which would be a simple linear search.

Actually, it is that simple. Proof:

Let's denote

p(i) ... the price of oil on day i
have(i) ... 1 if we retain the barrel overnight from day i to day i+1, 0 otherwise

have is only defined for i in [0, N-1]

now, if we buy on day k and sell on day l, we'd have

have(k) = 1
have(l) = 0
have(i) = 1 for k < i < l

the profit would be

p(l)-p(k) = sum over {i from k to l-1} (p(i+1)-p(i))

Let's denote

M(i) = max(p(i+1) - p(i), 0)

For all possible boolean functions have, we have

profit(have) = sum over {i where have(i)==1} (p(i+1) - p(i))
 <= sum over {i where have(i)==1} max(p(i+1) - p(i), 0)
 <= sum over {i where have(i)==1} M(i)
 <= sum over {i in [0, N-1]} M(i)

The second line comes from the fact that max(x, 0) >= x, the third is simple rewrite in terms of M(i), the fourth comes from M(i) >= 0.

Now, if we set have(i) == (p(i+1)>p(i)), it would have the same profit as above, which means it is maximal. Also, that means you buy at local minima and sell at local maxima.

jpalecek
  • 47,058
  • 7
  • 102
  • 144
  • @nayefc - can you explain what the problem is here? this seems like a valid answer to me. – andrew cooke Sep 14 '11 at 18:48
  • 1
    I don't understand how you find the local mins and maxes. Can you provide a sample run of the algorithm for the OP's example please? – IVlad Sep 14 '11 at 20:25
  • is precognition like this allowed in a supposed trading strategy? hindsight is 20-20. – Jimmy Sep 14 '11 at 21:15
  • 1
    If the price is higher on day n+1 than on day n then you wanted to own a barrel on day n - otherwise not. If your desire to own a barrel on a day is different than your desire the day before, then you need to make a transaction to fix that situation. – phkahler Sep 14 '11 at 21:25
  • @jpalecek: okay, what does "sum over" means, and why do we need it? I understood the part till M(i)=max(p(i+1)-p(i),0). Can some one please help with algo to get profit(have)? – Ronak Agrawal May 18 '15 at 13:50
2

Algorithm in O(N) time and O(1) space:

Starting at index 0
If you haven't bought an oil barrel:
    if price[i] < price[i + 1], buy at price[i]
    // if price[i] >= price[i + 1], you will never buy at price[i]
    // as price[i + 1] can bring you more money. So just wait...
If you have bought an oil barrel:
    if price[i] > price[i + 1], sell at price[i]
    // if price[i] <= price[i + 1], you will never sell at price[i]
    // as price[i + 1] can bring you more money. So just wait...

C++ implementation:

#include <iostream>
#include <vector>

int best_profit(const std::vector<int>& prices)
{
  bool buying = true;
  int buying_price = 0;
  int profit = 0;

  for(std::vector<int>::size_type i = 0; i < prices.size() - 1; ++i)
  {
    if(buying)
    {
      if(prices[i] < prices[i + 1])
      {
        buying_price = prices[i];
        buying = false;
      }
    }
    else if(prices[i] > prices[i + 1])
    {
      profit += prices[i] - buying_price;
      buying = true;
    }
  }

  if(!buying) // The last price is the highest one!
  {
    profit += prices[prices.size() - 1] - buying_price;
  }

  return profit;
}

int main()
{
  std::vector<int> prices1{1};
  std::vector<int> prices2{1, 2};
  std::vector<int> prices3{3, 2};
  std::vector<int> prices4{70, 74, 73, 72, 76};
  std::vector<int> prices5{70, 75, 71, 80, 96, 100, 15, 50, 60};

  std::cout << "prices1: " << best_profit(prices1) << std::endl;
  std::cout << "prices2: " << best_profit(prices2) << std::endl;
  std::cout << "prices3: " << best_profit(prices3) << std::endl;
  std::cout << "prices4: " << best_profit(prices4) << std::endl;
  std::cout << "prices5: " << best_profit(prices5) << std::endl;
}

Output:

prices1: 0
prices2: 1
prices3: 0
prices4: 8
prices5: 79
Mu Qiao
  • 6,941
  • 1
  • 31
  • 34
2

Sell at a local maxima, buy at a local minima. Treat the price before you start as infinity and after you end as zero.

MSN
  • 53,214
  • 7
  • 75
  • 105
1

Taking your example or barrel prices: [70, 74, 73, 72, 76].

From the given prices, I can compute the daily price change (i.e. today's price - previous day's price). The "price change array" in this case would be [4, -1, -1, 4].

In the "price change array", a positive number means price has increased and negative number means price has decreased compared to previous day.

The solution would be to find all contiguous sub-arrays out of the "price change array" which contain only positive numbers.

Using this idea, I have written below python code to print the pairs of buying and corresponding selling days:

barrel_price = [70, 74, 73, 72, 76]
trading_days = {} #dictionary for storing {buy_day: sell_day}
buy_day=0
sell_day=buy_day+1

while sell_day < len(barrel_price):
    if barrel_price[sell_day]-barrel_price[sell_day-1]>0:
        #don't sell if price is still increasing
        sell_day=sell_day+1
        trading_days[buy_day] = sell_day-1
    else:
        #don't buy if price is still decreasing
        buy_day=sell_day
        sell_day=buy_day+1

print trading_days

This prints "{0: 1, 3: 4}" For the first pair 0:1, i.e. buying day 0 and selling day 1, the corresponding prices are 70 and 74 in the barrel_price array. For the next pair 3:4, the corresponding buying price is 72 and selling price is 76.

Kumar
  • 194
  • 1
  • 8
0

L[j] represents the profit up to jth day.
L[j] = L[j-1] + MAX (0,Pj-Pj-1)
Pj = stock price on the jth day.
The solution lies in L[n] since each L[j] gives the maximum profit earned till that point and L[n] gives the max profit earned by the final day.
Running Time: O(n)

explorer
  • 15
  • 5
-1

just compare the prices:

search for the lowest price each week 

(loop1)

(if currentPrice < nextPrice) 
currentPrice = nextPrice

and get the highest price between currentPrice(date) and nextLowerSellPrice

(loop2)

(if currentHighPrice<nextHighPrice)
currentHighPrice = nextHighPrice
else
sell(currentHighPriceDay)
tzinne
  • 1