Longest profitable trading algorithm
Got this question during an interview. Wanted to know if there was a better solution:
Given the sequence of stock prices as [p1, p2, p3, p4, .... nNo]. Trader Joe is asked to buy 1 share of the stock at time i and sell the same share at time j. Its purpose is to maximize the time gap between buy time and sell time, but still profitable. For example, Trade Joe gets a sequence of prices over time:
Time, price
10: 00,10.3
10: 01,10.1
10: 02.11
10: 03.13
10: 04.9.5
10: 05,7.3
10: 06.8
10: 07,10.2
10: 08,9.8
If he buys the stock at 10:01, the price is 10.1 and sells it at 10:07, the price is 10.2. He will make a profit of 0.1 and the time between buying and selling is 6 minutes. And this is the maximum time for this example.
Input
The first line contains the length of the sequence N. The next N lines contain the pair (time, price): N Time1, price1 Time2, price2 ...
Output
The maximum time between a winning buy-then-sell stock pair using a given price sequence
Sample input (using file or stdin):
7
10: 01.7
10: 02.4
10: 03.5
10: 04.10
10: 05.5
10: 06.2
10: 07.6
Output example:
5 (This is a buy at 10:02 ($ 4) and a sell at 10:07 ($ 6), the time delta is 10:07 - 10:02 = 5 minutes)
The solution I suggested was O (N 2 ), with a little optimization:
for(int i = 0; i < lines.size(); i++){
for(int j = lines.size()-1; j >= 0; j--){
try
{
String[] partsFirst = lines.get(i).split(",");
String[] partsLast = lines.get(j).split(",");
String firstPriceString = partsFirst[1];
String lastPriceString = partsLast[1];
String firstDateString = partsFirst[0];
String lastDateString = partsLast[0];
double firstPriceInt = Double.parseDouble(firstPriceString);
double lastPriceInt = Double.parseDouble(lastPriceString);
Date date1 = format.parse(firstDateString);
Date date2 = format.parse(lastDateString);
long difference = date2.getTime() - date1.getTime();
//optimization
if(difference <= maxDuration)
continue;
if(lastPriceInt > firstPriceInt && (difference) > maxDuration)
maxDuration = difference;
}
catch (ParseException ex)
{
System.out.println("Exception "+ex);
}
}
}
Is there a better solution?
source to share
Yes, there is an O (n) -time algorithm.
Scan prices ahead (from beginning to end), storing prices in an auxiliary array that are less than all previous prices, together with time. Do something similar to find all prices above all subsequent prices. These arrays are naturally sorted.
The optimal trade is bought from the first array and sold to the second. A variant of a sorted merge of the two arrays will identify all O (n) operations that are profitable and as far apart as possible, provided one endpoint is fixed.
The way the merge works is that we initialize an index into the "buy" (first) array and another index into the "sell" (second) array, starting with the lowest prices. If the current buy prices are below the current sell price, then consider that trade and move on to the next highest buy price. Otherwise, proceed to the next highest selling price.
source to share
Here's an explanation for the O (n) solution mentioned in David Eisenstat Answer .
The main point to note here is that if point A has a shorter time and a lower price than another point B, then A is a better buy point than B. For example, if you have prices [2, 3, 4, 1, ...] (sorted by time), then there is no point in testing 3 and 4 as buy points if you have already tested 2. We can conclude that for the starting point we only need to test prices that are less than all previous prices. This can be done by scanning prices and storing points that match this condition.
This will give us an array buy_points = [p 1, p 2, p 3, ...]
Second remark for any sell point, if it is not higher than the price than the buy point p i, then it will not be higher than any previous point p jwhere j <i. This is due to the fact that each item in the purchase points is smaller than all the previous points.
Given these observations, we can construct an algorithm as follows:
We scan the buy point array and the sell point array (original price array) back. For each pair of selling price and purchase price:
- If the sell price is higher then this is a valid trade and we must check if it is better than our current one. We also go to the previous point of purchase, as this is the best we can get for this moment.
- If the sell price is lower, we can skip this point, as it will not work from any of the previous buy points.
Here's a sample code in python:
def get_max_distance(prices):
min_price_so_far = None
buying_points = []
for time, price in prices:
if min_price_so_far is None or price < min_price_so_far[1]:
min_price_so_far = (time, price)
buying_points.append(min_price_so_far)
selling_points = reversed(prices)
buying_points = reversed(buying_points)
buying_point = next(buying_points, None)
selling_point = next(selling_points, None)
best = 0
while buying_point and selling_point:
buying_time, buying_price = buying_point
selling_time, selling_price = selling_point
if selling_price > buying_price:
if selling_time > buying_time:
best = max(best, selling_time - buying_time)
buying_point = next(buying_points, None)
else:
selling_point = next(selling_points, None)
return best
source to share