The task of Apple shares
This task was given to candidates during the interviews at Apple. You need to create a function that returns that maximum profit from a single deal with one share (firstly purchase, then sale). The input data is an array of yesterday quotations with Apple shares’ prices.
Here is the info about the array:
The index is equal to the number of minutes since the beginning of the trading session (9:30 am).
The value in the array is equal to the value of the share at this time.
For example: if a share at 10:00 am costs $ 20, then
stock_prices_yesterday  = 20.
Suppose we have some conditions:
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
profit = get_max_profit (stock_prices_yesterday)
# returns 6 (bought for 5, sold for 11)
The array can be any, even for the whole day. It is necessary to write the function get_max_profit as efficiently as possible – with the least runtime and memory expenses.
To solve the problem, it is not enough just to take the maximum and minimum prices, since you must first buy at the lowest price and then sell at the highest price that will be after the purchase price. In addition, if the stock price falls all day, then the best answer is a negative number.
For each price we will check:
the opportunity to get big profits when buying at min_price and selling at current_price.
whether min_price updated with new value after iteration.
min_price is equal to the first price of the day.
max_profit is equal to the first profit that we get.
Solution code (in Python):
def get_max_profit (stock_prices_yesterday): # make sure that the number of prices in the array exceeds 2 if len (stock_prices_yesterday) <2: raise IndexError ('Making a profit requires at least two prices in the array') # initialize min_price and max_profit min_price = stock_prices_yesterday  max_profit = stock_prices_yesterday  - stock_prices_yesterday  for index, current_price in enumerate (stock_prices_yesterday): # skip the 0th element of the array, since min_price is initialized. # Also sell in the 0th position can not if index == 0: continue # calculate potential profit potential_profit = current_price - min_price # update maximum profit max_profit = max (max_profit, potential_profit) # update minimum price min_price = min (min_price, current_price) return max_profit
The efficiency of the obtained algorithm is O(n) in time and O(1) in memory. The loop goes through the array only once.