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...)
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).
To illustrate with an example, let's take the stock ticker of Company Z:
55.39 109.23 48.29 81.59 105.53 94.45 12.24
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.
(in the above example, the ideal solution is to buy at 48.29 and sell at 105.53)
I came up with the naive solution easily enough with O(n2) complexity (implemented in java):
// 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<Double> prices) {
int [] retval = new int[2];
int BUY = 0, SELL = 1;
retval[BUY] = retval[SELL] = -1; // i开发者_如何学编程ndices of buy and sell prices, respectively
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
double difference = prices.get(j).doubleValue() -
prices.get(i).doubleValue();
if (difference > 0.0) {
if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() -
prices.get(retval[BUY]).doubleValue()) {
retval[BUY] = i;
retval[SELL] = j;
}
}
}
}
return (retval[BUY] > 0 ? retval : null);
}
Here's where I screwed up: there's a linear time O(n) solution, 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!
Edit
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. :(
In C#:
static void Main(string[] args)
{
double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
for (int i = 1; i < values.Length; i++)
{
if (values[i] > values[i - 1])
{
//trending upward, append to existing differential
diff += values[i] - values[i - 1];
}
else
{
//trending downward, reset the diff
diff = 0;
}
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
EDIT: New algo based on @Joe's failing test case -- Nice Catch BTW! It's also the same answer as @Doug T's now...
static void Main(string[] args)
{
double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
double bottom = values[0];
for (int i = 1; i < values.Length; i++)
{
diff += values[i] - values[i - 1];
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
if (values[i] < bottom)
{
bottom = values[i];
diff = 0;
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
Here's an attempt (C++). Basically everytime I track a new top, I try to see if thats the best profit thusfar. I know that the "bottom" must have been discovered earlier. At that point I remember the top, bottom, and the current max profit. If a new bottom is discovered later, its AFTER the current top, so we must reset top and see if a slightly lower "top" can yield better profit.
#include <iostream>
int main()
{
double REALLY_BIG_NO = 1e99;
double bottom = REALLY_BIG_NO; // arbirtrary large number
double currBestBuy = 0.0;
double top = 0.0;
double currBestSell = 0.0;
double profit = 0.0;
// array of prices
double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0};
int numPrices = 10;// number of prices
for (int i = 0; i < numPrices; ++i)
{
if (prices[i] < bottom)
{
bottom = prices[i];
// reset the search on a new bottom
top = 0.0;
}
else if (prices[i] > top)
{
top = prices[i];
// calculate profit
double potentialProfit = (top - bottom);
if (potentialProfit > profit &&
bottom != REALLY_BIG_NO)
{
profit = potentialProfit;
currBestSell = top;
currBestBuy = bottom;
}
}
}
std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;
}
So far I've played around with a bunch of different input sets, and so far I haven't had any problems... (let me know if you test this and see anything wrong)
I highly recommend using Austin Salonen's updated answer to this question and adapting it to your language.
The idea is simple. Keep two pointers, lo and hi.
Do a Foor loop
- if price is higher than hi, update hi = price, continue
- if the price is lower than hi. Then lo and hi is one of possible candidates. Calculate the profit, store it if it's bigger than previous profits and reset lo, hi to price
def getBestProfit(prices):
lo = hi = profit = 0
for price in prices:
if lo == 0 and hi == 0:
lo = hi = price
if price > hi:
hi = price
if price < low:
tmpProfit = hi - lo
if tmpProfit > profit:
profit = tmpProfit
lo = hi = price
return profit
That's it
void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++)
{
if (stocks[i] < stocks[min])
{
min = i;
}
int diff = stocks[i] - stocks[min];
if (diff > maxDiff)
{
buy = min;
sell = i;
maxDiff = diff;
}
}}
Just in case you prefer this answer. I found it in another web, but still. source:http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html
public void profit(float stock[], int arlen ){
float buy = stock[0];
float sell = stock[arlen-1];
int bi = 0;
int si = arlen - 1;
for( int i = 0; i < arlen && bi < si ; i++){
if( stock[i] < buy && i < si){
buy = stock[i];
bi = i;
}
if(stock[arlen - i - 1] > sell && (arlen - i -1) > bi){
sell = stock[arlen - i - 1];
si = arlen - i - 1;
}
}
System.out.println(buy+" "+sell);
}
I really have to point out as an interview question expecting you to solve it as O(n) is borderline absurd. Interview questions are meant to prove you can solve a problem, which you were able to solve it. The fact you solved it in O(N^2) vs O(N) should be irrelevant. If a company would pass over hiring you for not solving this in O(N) that's probably not a company you would have wanted to work at anyway.
I'd like to describe how I approached this problem to make it easier to understand my code:
(1) For each day, if I had to sell my stock on that day, what would be the minimum amount I could have paid to buy it? Essentially, I'm keeping track of minimum price before that day
(2) For each day, if I were to sell on that day, how much am I earning? (Stock price on that day - minimum price)
This shows that I have to keep track of two things: (1) minimum stock price so far (2) best earning so far.
The problem becomes choosing which day to sell. I will sell on the day that will give me the best earning. Here is my Java code:
public static void findBestDeal(double [] stocks) {
double minsofar = stocks[0];
double bestsofar = 0.0;
for(int i=1; i< stocks.length; i++) {
// What is the cheapest price to buy it if I'm going to sell it today
if(stocks[i-1] < minsofar) {
minsofar = stocks[i-1];
}
// How much do I earn if I sell it on ith day?
double current_deal = stocks[i] - minsofar;
// Is selling today better?
if(current_deal > bestsofar) {
bestsofar = current_deal;
}
}
System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");
}
Here is my O(n) implementation for this. I am using a change array to calculate the max profit and buy and sell dates. Your comments on this are welcome.
#include<stdafx.h>
#include<stdio.h>
int main()
{
//int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
int change[7];
int n=7;
for(int i=1;i<=n;i++)
{
change[i] = arr[i]- arr[i-1];
}
int i=0,index = 0;
int sum = 0;
int maxsum = 0;
int startpos = 0;
int endpos = 0;
while(index < n)
{
sum = sum + change[index];
if(maxsum < sum)
{
maxsum = sum;
startpos = i;
endpos = index;
}
else if (sum<0) // negative number ,set sum to zero
{
sum = 0;
i=index+1;
}
index++;
}
printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}
In my effort to learn Go, and also to rake my brain on this one, here is my attempt.
func GetMaxProfit2(prices []float64) (float64, float64) {
var min, max, pmin, pmax int
for i, v := range prices {
if v - prices[min] > prices[max] - prices[min] {
pmax = max
max = i
}
// Reset the max when min is updated.
if v < prices[min] {
pmin = min
min = i
pmax = max
max = i
}
}
// If min is ahead of max, reset the values back
if min >= max {
min = pmin
max = pmax
}
return prices[min], prices[max]
}
Here is my attempt using Javascript. The script computes the answer in O(N):
//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];
//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;
//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
if(tmp.minVal > stock[i]) {
tmp.minVal = stock[i];
tmp.minInd = i;
} else {
ans.diff = stock[i] - stock[tmp.minInd];
if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
ans.maxDiff = ans.diff;
ans.maxInd = i;
ans.minInd = tmp.minInd;
ans.minVal = tmp.minVal;
}
}
}
document.write('You should buy your stocks on day ' + ans.minInd + ' and sell on day ' + ans.maxInd);
This is a C solution that actually works:
void bestBuySell() { double prices[] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; double bestBuy = prices[0], bestSell = prices[1], bestPotentialBuy = prices[0]; double potentialProfit = prices[1] - prices[0];
for(int i = 1; i < (arrSize-1); i++)
{
if(prices[i] < bestBuy)
bestPotentialBuy = prices[i];
if((prices[i+1] - bestPotentialBuy) > potentialProfit)
{
bestBuy = bestPotentialBuy;
bestSell = prices[i+1];
potentialProfit = prices[i+1] - bestPotentialBuy;
}
}
printf( "bestBuy %f bestSell %f\n", bestBuy, bestSell );
}
1.We cant simply take the least amount among the values as " Best Buy" and the max amount as "Best Sell" because "Sell" has to happen after "Buy".
2.We must not treat the recorded minimum as the "Best Buy" because the subsequent days may have stock values whose difference with the recorded minimum may yield profit which could be less than the "recorded profit".
3.Best Buy and Best Sell is treated as a single variant,because it is the positive difference between these values that makes max profit.
4.Since any recorded minimum in the past is a potential candidate for buying,the max profit condition must always be checked against the recorded minimum and the current day's stock price.So we always have to keep track of recorded minimum,but just the presence of recorded minimum doesn't constitute "Best Buy" because of reason number 2.
Now have the below code which executes in O(n) times will make sense.
public class BestStockBuyAndSell {
public static void main(String[] args) {
double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
int [] bestBuySellIndex = maxProfit(stockPrices);
System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);
System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));
}
public static int[] maxProfit(double[] stockPrices)
{
int bestBuy=0;
int bestSell=0;
int[] bestCombination ={bestBuy,bestSell};
double recordedMinimum = stockPrices[bestBuy];
int recordedMinimuIndex = bestBuy;
double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];
for(int i=1;i<stockPrices.length;i++)
{
if(stockPrices[i] - recordedMinimum > bestProfitSofar)
{
bestProfitSofar = stockPrices[i] - recordedMinimum;
bestSell = i;
bestBuy = recordedMinimuIndex;
}
if(stockPrices[i] < recordedMinimum)
{
recordedMinimuIndex = i;
recordedMinimum = stockPrices[i];
}
}
bestCombination[0] = bestBuy;
bestCombination[1] = bestSell;
return bestCombination;
}
}
I came up with following algorithm for this problem, seems to work for all inputs. Also, If the Stock value keeps droping, the program would output not to buy this stock:
public class GetMaxProfit
{
double minValue = -1, maxValue = -1;
double maxDiff = 0;
public void getProfit(double [] inputArray){
int i=0, j=1;
double newDiff = 0;
while(j<inputArray.length){
newDiff = inputArray[j]-inputArray[i];
if(newDiff > 0){
if(newDiff > this.maxDiff){
this.minValue = inputArray[i];
this.maxValue = inputArray[j];
this.maxDiff = newDiff;
}
}
else{
i = j;
}
j++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GetMaxProfit obj = new GetMaxProfit();
obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
if(obj.minValue != -1 && obj.maxValue != -1){
System.out.println("Buy Value for the input: "+obj.minValue);
System.out.println("Sell Value for the input: "+obj.maxValue);
System.out.println("Best profit for the input: "+obj.maxDiff);
}
else
System.out.println("Do Not Buy This STOCK!!);
}
}
Is there any catch you could find in this? It's time complexity is O(N)
Here is my solution, same as @Doug T. except I am also keeping track of the day in an index. Please provide feedback.
int prices[] = {4,4,5,6,2,5,1,1};
//int prices[] = {100, 180, 260, 310, 40, 535, 695};
int currentBestSellPrice=0;
int currentBestBuyPrice=0;
int lowindex=0;
int highindex=0;
int low=prices[0];
int high=prices[0];
int profit=0;
int templowindex=0;
for(int i=0; i< prices.length;i++)
{
// buy low
if(prices[i] < low && i+1 < prices.length)
{
low = prices[i];
templowindex=i;
high=0;
}
// sell high
else if(prices[i] > high)
{
high = prices[i];
int potentialprofit = (high-low);
if(potentialprofit > profit)
{
profit = potentialprofit;
currentBestSellPrice = high;
currentBestBuyPrice = low;
highindex=i;
lowindex=templowindex;
}
}
}
System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );
F# solution for those who interested in functional take on this. I wouldn't say though it's that much different.
let start, _, profit =
[55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
|> Seq.fold (fun (start,newStart,profit) i ->
let start = defaultArg start i
let newStart = defaultArg newStart i
let newProfit = i - newStart
if profit < newProfit
then Some newStart, Some newStart,newProfit
else if start > i
then Some start, Some i, profit
else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)
Output:
Best buy: 48.290000; Best sell: 105.530000
Here is my solution in Ruby:
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
max_diff = 0
diff = 0
min = values[0]
max = 0
values.each_with_index do |value, index = 1|
# get an array of the previous values before the current one
lag_values = values[0..index]
# get the minimum of those previous values
min_lag_value = lag_values.min
# difference between current value and minimum of previous ones
diff = values[index].to_i - min_lag_value.to_i
# if current difference is > previous max difference, then set new values for min, max_diff, and max
if diff > max_diff
max_diff = diff
min = min_lag_value
max = values[index]
end
end
min # => 48.29
max # => 105.3
max_diff # => 57
Cheers
I got 100% for the same, here you go.
public int solution(int[] A) {
if (A == null || A.length<=1){
return 0;
}
int minValue = Math.min(A[0], A[1]);
int profit = A[1] - A[0];
for (int i = 2; i < A.length; i++) {
minValue = Math.min(minValue, A[i]);
profit = Math.max(A[i] - minValue,profit);
}
return profit > 0 ? profit : 0;
}
The way I thought about this was, for every index i what would be the ideal index be for selling this stock? This is of course, the index of the maximum value after i. This reduces our problem to finding the maximum element after index i for each i in [1 ... n] If we could do that in O(n) time, then we could find the best choice amongst those and report it.
A way to do this is to start traversing from the end of the array, maintaining two variables, one to save the largest element we have encountered so far max_till_now, and one to save the maximum profit we could get till now, profit. This is just so that we can do this in one pass. We could also use extra space and for each element i, store the index of the largest element in the range [i + 1 ... n] for it and then find the maximum profit.
Here's my python code:
def buyLowSellHigh(L):
length = len(L)
profit = 0
max_till_now = L[length - 1]
for i in xrange(length - 2, -1, -1):
if L[i] > max_till_now: max_till_now = L[i]
else:
if max_till_now - L[i] > profit: profit = max_till_now - L[i]
return profit
Another Ruby solution:
# Here's some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]
# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0
# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|
# Check value in this turn.
puts value
# Check current value is bigger than min or not.
# If not, we find the new min.
if value <= min
min = value
# If current value is bigger than min and
# (value - min) is bigger than previous max_profit,
# set new best_buy_time, best_sell_time & max_profit.
else
if value - min >= max_profit
best_buy_time = min
best_sell_time = value
max_profit = value - min
end
end
end
# Let's see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit
what about this?
min = 100000000
max = 0
for elem in inp:
if elem < min:
min = elem
tempMax = elem-min
if tempMax > max:
max = tempMax
print(max)
Solution in javascript
var stockArr = [13931, 9889, 987, 4, 89, 100];
function getBestTime(sortedArr) {
var min = 0;
var buyIndx = 0;
var saleIndx = 0;
var maxDiff = 0;
for (var i = 0; i < stockArr.length; i++) {
if (stockArr[i] < stockArr[min]) {
min = i;
}
var diff = stockArr[i] - stockArr[min];
if (diff > maxDiff) {
buy = min;
sale = i;
maxDiff = diff;
}
}
return {
buy:buy+1,
sale:sale+1,
diff:maxDiff
}
}
console.log(getBestTime(stockArr));
Heres a javascript solution..
function getMax(arr){
//we need more than at least 3 ints to be able to do this
if(arr.length <= 1) return arr;
// get the minimum price we can sell at to make a profit
var min = arr[0];
//get the first potential maximum profit
var max = arr[1] - arr[0];
//while looping through we must get a potential value,
//we can then compare that using the math.max using the maximum
//and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
for(var i = 1; i < arr.length; ++i){
var current = arr[i];
var potential = current - min;
max = Math.max(max, potential);
min = Math.min(min, current);
}
return max;
}
console.log(getMax([10, 7, 5, 8, 11, 9]));
Runtime on this is O(n)
Solution in scala :
Example : [ 7, 2, 5, 6, 1, 3, 6, 4 ]
Keep a pointer to the last minimum stock price(lastStockPrice) and compare it to the current stock price. When you reach a point where the current stock price < last minimun stock price, you update the lastStockPrice.
While looping through the array, keep a track of the max difference (profit) between the currentPrice and the lastStockPrice as the profit can change when you update the lastStockPrice.
The below scala code works in O(n) time and takes a constant amount of space.
object Solution {
def maxProfit(prices: Array[Int]): Int = {
var lastStockPrice = Int.MaxValue
var maxProfit = 0
for(currentPrice <- prices){
if(currentPrice < lastStockPrice){
lastStockPrice = currentPrice;
}else if(currentPrice - lastStockPrice > maxProfit){
maxProfit = currentPrice - lastStockPrice;
}
}
maxProfit
}
}
The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.
All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.
Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
_currmax = 0
_globalMax = 0
for i in range(1,len(prices)):
_currmax = max(_currmax+(prices[i]-prices[i-1]),0)
_globalMax = max(_globalMax,_currmax)
return _globalMax
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论