Write efficient function takes stock prices yesterday returns best profit

Write efficient function takes stock prices yesterday returns best profit

This is very famous question in banking and hedge fund companies. Particularly hedge fund companies ask this question to the candidate to check his algorithm knowledge and how quickly able to solve problems:

Question: Suppose we could access yesterday’s stock prices as a list, where:

The indices are the time in minutes past trade opening time, which was 9:30am local time.
The values are the price in dollars of Apple stock at that time.
So if the stock cost $500 at 10:30am, stock_prices_yesterday[60] = 500.

Write an efficient function that takes stock_prices_yesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.

For example:

stock_prices_yesterday = [10, 7, 5, 8, 11, 9]

get_max_profit(stock_prices_yesterday)
# returns 6 (buying for $5 and selling for $11)

No “shorting”—you must buy before you sell. You may not buy and sell in the same time step (at least 1 minute must pass).

Solution: Below is very effective algorithm which uses linear time O(n) to resolve the buy and sell price and I believe this answer should be acceptable by the interviewer:

• BuySellStock.java:

package com.buysell;

public class BuySellStock {

	public static void main(String[] args) {
		
		double[] priceArray =  {10, 7, 5, 8, 11, 9};
//		double[] priceArray = { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };
		
		System.out.println("Maximum profit: "+getMaxProfit(priceArray));

	}

	private static double getMaxProfit(double[] priceArray) {
		
		double maxDiff = Double.MIN_VALUE;
		double max = Double.MIN_VALUE;
		double bottom = priceArray[0];
		double diff = 0;		

	    for (int i = 1; i < priceArray.length; i++)
	    {
	        diff += priceArray[i] - priceArray[i - 1];

	        if (diff > maxDiff)
	        {
	            maxDiff = diff;
	            max = priceArray[i];
	        }

	        if (priceArray[i] < bottom)
	        {
	            bottom = priceArray[i];
	            diff = 0;
	        }
	    }
	    
	    double buy = max - maxDiff;
	    double sell = max;
	    double maxProfit = sell-buy;
	    
	    System.out.println("Buy at : "+buy +"  Sell at: "+sell);
	    
	    return maxProfit;
	}
	
}

• Output:

Reference:

• Analysis of Algorithms