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 = 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.
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
# 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: