Interview Questions

Stock maximum profit
The question is as follows:
You will be given a list of stock prices for a given day and your goal is to return the maximum profit that could have been made by buying a stock at the given price and then selling the stock later on. For example if the input is: [45, 24, 35, 31, 40, 38, 11] then your program should return 16 because if you bought the stock at \$24 and sold it at \$40, a profit of \$16 was made and this is the largest profit that could be made. If no profit could have been made, return -1.

## Algorithm

We'll solve the challenge the following way:
(1) Iterate through each number in the list. (2) At the ith index, get the i+1 index price and check if it is larger than the ith index price. (3) If so, set buy_price = i and sell_price = i+1. Then calculate the profit: sell_price - buy_price. (4) If a stock price is found that is cheaper than the current buy_price, set this to be the new buying price and continue from step 2. (5) Otherwise, continue changing only the sell_price and keep buy_price set.
This algorithm runs in linear time, making only one pass through the array, so the running time in the worst case is O(n).

## Example

Here is an example of the values that are set through each iteration of the stock prices. input = [45, 24, 35, 31, 40, 38, 11] buy_price = 0 sell_price = 0 max_profit = -1 At i = 0 buy_price = 45 sell_price = 24 max_profit = -1 At i = 1 buy_price = 24 sell_price = 35 max_profit = 11 At i = 2 buy_price = 24 sell_price = 31 max_profit = 11 At i = 3 buy_price = 24 sell_price = 40 max_profit = 16 At i = 4 buy_price = 24 sell_price = 38 max_profit = 16 At i = 5 buy_price = 24 sell_price = 11 max_profit = 16 Loop is done max_profit = 16

## Code

```function StockPicker(arr) {

var max_profit = -1;
var sell_price = 0;

// this allows our loop to keep iterating the buying
// price until a cheap stock price is found

// loop through list of stock prices once
for (var i = 0; i < arr.length-1; i++) {

// selling price is the next element in list
sell_price = arr[i+1];

// we set the buying price equal to the current element

// if the selling price is less than the buying price
// we know we cannot make a profit so we continue to the
// next element in the list which will be the new buying price
continue;
}

// if the selling price is greater than the buying price
// we check to see if these two indices give us a better
// profit then what we currently have
else {
var temp_profit = sell_price - buy_price;
if (temp_profit > max_profit) { max_profit = temp_profit; }
}

}

return max_profit;

}

StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15]);
```
```def StockPicker(arr):

max_profit = -1
sell_price = 0

# this allows our loop to keep iterating the buying
# price until a cheap stock price is found

# loop through list of stock prices once
for i in range(0, len(arr)-1):

# selling price is the next element in list
sell_price = arr[i+1]

# we set the buying price equal to the current element

# if the selling price is less than the buying price
# we know we cannot make a profit so we continue to the
# next element in the list which will be the new buying price
continue

# if the selling price is greater than the buying price
# we check to see if these two indices give us a better
# profit then what we currently have
else:
if temp_profit > max_profit:
max_profit = temp_profit

return max_profit

print StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15])
```

## Sources

mrdaniel published this on 1/3/16 |
• +
• 7
• -
• I am confused as to why the "continue" keyword is used here. It seems to me that the code would (and does) execute just fine without it? Was there a specific reason it was left in there? Thanks so much!
• +
• 3
• -
• The question is a bit misleading. It says "by buying a stock at the given price and then selling the stock later on". The buy price is not given. Would be much clearer to say "buy once and sell once".
• +
• 2
• -
• I'd like to suggest that using array.reduce() is the most streamlined approach for such a problem: ``` function StockPicker(arr) { let trueMax = 0; arr.reduce(function(prev, item){ let max = Math.max(item - prev, 0); max > trueMax ? trueMax = max : null; if (max === 0) { return item; } else { return prev; } }); if (trueMax === 0) { return -1; } return trueMax; } ```
• +
• 2
• -
• ```function stock(arr){ var buy = -1, sell =-1, profit = -1; var changeSellPrice = true; for(var i=0; i< arr.length; i++){ // assigning "buy" value inside the array because if array is empty, buy would be -1 if(buy===-1){ buy= arr[i]; } if(buy> arr[i]){ buy = arr[i]; changeSellPrice = true; } if(changeSellPrice || sell< arr[i+1] ){ sell = arr[i+1]; if(profit< (sell-buy)){ profit = sell - buy; changeSellPrice = false; } } } return profit; }```
• +
• 1
• -
• This is how I did it. var profitArray is map of the agumented array. It takes every value a turns it into the profit one would make if he bought the stocks that day and sold them on the most expensive day left. profitArray.sort(function(a, b){return b-a})[0] simply returns the highest value of profit opportunities ``` function maxProfit(array) { var profitArray = array.map(function(currentValue, index) { return array.slice(index, array.length) .sort(function(a, b){return b-a})[0] - currentValue }) return profitArray.sort(function(a, b){return b-a})[0]; } console.log(maxProfit([45, 24, 35, 31, 40, 38, 11])); ```
• +
• 1
• -
• "If no profit could have been made, return -1." This would return 0 if that was the "max profit", but that's not profit.
```from collections import deque

def stock_max_profit(prices):
max = 0
prices = deque(prices)

for price in prices:

else:

if profit > max:
max = profit

if max:
return max
else:
return -1

prices = [45, 24, 35, 31, 40, 38, 11]
max_profit = stock_max_profit(prices)
print(max_profit)
```
• +
• 1
• -
• Keep track of the lowest i've seen so far (lissf), compare current index to compute profit ``` function StockPicker(arr) { let lissf = arr[0] let profit = -1 for(let i = 1; i < arr.length; i++) { if(arr[i] > lissf) { profit = Math.max(profit, arr[i] - lissf) } else { lissf = arr[i] } } return profit } ```
• +
• 1
• -
• ```def StockPicker(arr): bp=0 sp=0 mp=-1 for r in arr: if arr[arr.index(r)+1] > r: bp=r break sp=max(arr[_] for _ in range(arr.index(bp),len(arr))) if sp-bp > mp: return sp-bp else: return mp print(StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15]))```
• +
• 0
• -
• ``` function maxStock(arr){ if(arr[0] > arr[1]){ var redundant = arr.shift(); var newArr = arr; var maxPrice = Math.max.apply(null, newArr); var minPrice = Math.min.apply(null, newArr); if(newArr.indexOf(maxPrice) > newArr.indexOf(minPrice)){ var maxProfit = maxPrice - minPrice; } else { while(newArr.indexOf(minPrice) > newArr.indexOf(maxPrice)){ newArr.splice(newArr.indexOf(minPrice), 1); } var newMin = Math.min.apply(null, newArr); maxProfit = maxPrice - newMin; } } return maxProfit; } ```
• +
• 0
• -
• ```function test(arr){
let profit = 0;
arr.forEach((currPrice, i) => {
const reducer = (pr, val) => currPrice - val < pr ? currPrice - val : pr;
profit = arr.slice(i).reduce(reducer, profit);
})
return profit < -1 ? -profit : -1;
}

console.log(test([45, 24, 35, 31, 40, 38, 11]));
```
• +
• 0
• -
• The problem descriptions shall be updated, it is not explicit the constraint that you should buy and sell only once. This lead to a misinterpretation and looks like the example with \$16 of proffit is wrong. The natural interpreation of buy and sell stocks for the given set [45, 24, 35, 31, 40, 38, 11] is a max profit of \$20 where you buy by \$24 and sell by \$35 making a profit of \$11 next you buy by \$31 and sell by \$40 making a profit of \$9 and total profit of \$20.
• +
• 0
• -
• ```def stockExchange(stockPrices): buy = stockPrices[0] sell = 0 profit = -1 for n in range(0,len(stockPrices)-1): x = stockPrices[n] if x < buy: buy = x sell = 0 elif x > sell: sell = x profit = sell - buy return profit```
• +
• 0
• -
• // find the max one ``` function StockPicker(arr, max = []) { let cur = arr.slice(0, 1); let last = arr.slice(1); let profits = last.map(item => { let profit = item - cur; if (profit > 0) { return profit; } else { return -1; } }); max.push(Math.max.apply(null, profits)) if (last.length > 1) { return StockPicker(last, max) } return Math.max.apply(null, max); } ```
• +
• -1
• -
• I tried this way... ``` function stock(array){ var min= array[0]; var max= -1; var profit= 0; for(var idx in array){ if(array[idx]<min){ min= array[idx]; max= -1; } if(array[idx]>max){ max= array[idx]; if(max-min>profit){ profit= max-min; } } } return profit; } console.log(stock([44, 30, 24, 32, 35, 30, 40, 38, 15])); ```
• +
• -6
• -
• My version, but I am not quite convinced by this problem. ```var maxArray = arr; maxArray.shift(); var minArray = arr; minArray.pop(); var min = Math.min.apply(null, minArray); var max = Math.max.apply(null, maxArray); return max-min;```