Interview Questions

  • View all algorithm tutorials
  • blank
    • 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 buy_price = 0;
  var sell_price = 0;
  
  // this allows our loop to keep iterating the buying
  // price until a cheap stock price is found
  var change_buy_index = true;
  
  // 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]; 
    
    // if we have not found a suitable cheap buying price yet
    // we set the buying price equal to the current element
    if (change_buy_index) { buy_price = arr[i]; }
    
    // 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
    if (sell_price < buy_price) {
      change_buy_index = true; 
      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; }
      change_buy_index = false;
    }
    
  }
  
  return max_profit;
         
}

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

    def StockPicker(arr): 
  
  max_profit = -1
  buy_price = 0
  sell_price = 0
  
  # this allows our loop to keep iterating the buying
  # price until a cheap stock price is found
  change_buy_index = True
  
  # 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]
    
    # if we have not found a suitable cheap buying price yet
    # we set the buying price equal to the current element
    if change_buy_index: 
      buy_price = arr[i]
    
    # 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
    if sell_price < buy_price:
      change_buy_index = True 
      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:
      temp_profit = sell_price - buy_price
      if temp_profit > max_profit:
        max_profit = temp_profit
      change_buy_index = False
      
  return max_profit

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

    Sources

    https://www.glassdoor.com/Interview/You-have-all-of-the-prices-for-a-given-stock-for-the-next-year-You-can-buy...
    mrdaniel published this on 1/3/16 | javascript, bootcamp, Fullstack Academy, Hack Reactor, Google
    Comments
  • +
    • 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)
    buy_price = prices.popleft()


    for price in prices:


        if price < buy_price:
            buy_price = price


        else:
            profit = price - buy_price


            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;
    Log in to submit a comment.