July 31, 2022

Programming technical interview questions

To start, try writing an example value for stock_prices_yesterday and finding the maximum profit "by hand." What's your process for figuring out the maximum profit?

The brute force approach would be to try every pair of times (treating the earlier time as the buy time and the later time as the sell time) and see which one is higher.

def get_max_profit(stock_prices_yesterday): max_profit = 0 # go through every time for outer_time in xrange(len(stock_prices_yesterday)): # for every time, go through every OTHER time for inner_time in xrange(len(stock_prices_yesterday)): # for each pair, find the earlier and later times earlier_time = min(outer_time, inner_time) later_time = max(outer_time, inner_time) # and use those to find the earlier and later prices earlier_price = stock_prices_yesterday[earlier_time] later_price = stock_prices_yesterday[later_time] # see what our profit would be if we bought at the # earlier price and sold at the later price potential_profit = later_price - earlier_price # update max_profit if we can do better max_profit = max(max_profit, potential_profit) return max_profit

But that will take time, since we have two nested loops—for every time, we're going through every other time. Also, it's not correct: we won't ever report a negative profit! Can we do better?

Well, we’re doing a lot of extra work. We’re looking at every pair twice. We know we have to buy before we sell, so in our inner for loop we could just look at every price after the price in our outer for loop.

That could look like this:

def get_max_profit(stock_prices_yesterday): max_profit = 0 # go through every price (with its index as the time) for earlier_time, earlier_price in enumerate(stock_prices_yesterday): # and go through all the LATER prices for later_price in stock_prices_yesterday[earlier_time+1:]: # see what our profit would be if we bought at the # earlier price and sold at the later price potential_profit = later_price - earlier_price # update max_profit if we can do better max_profit = max(max_profit, potential_profit) return max_profit

What’s our runtime now?

Well, our outer for loop goes through all the times and prices, but our inner for loop goes through one fewer price each time. So our total number of steps is the sum n + (n - 1) + (n - 2) ... + 2 + 1, which is still time.

We can do better!

If we're going to do better than , we're probably going to do it in either or . comes up in sorting and searching algorithms where we're recursively cutting the set in half. It's not obvious that we can save time by cutting the set in half here. Let's first see how well we can do by looping through the set only once.

Since we're trying to loop through the set once, let's use a greedy approach, where we keep a running max_profit until we reach the end. We'll start our at $0. As we're iterating, how do we know if we've found a new ?

At each iteration, our is either: