C interview questions with

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:

  1. the same as the at the last time step, or
  2. the max profit we can get by selling at the current_price


Share this article





Related Posts



Latest Posts
Psychometric sample questions
Psychometric…
For the statements below say whether…
Technical Ability Test
Technical Ability…
Taken with a Nikon D80. * Exposure: 0.003…
How to answer weakness interview question?
How to answer…
What s your greatest weakness? is the…
Applications developer Interview questions
Applications…
Many software developers I have talked…
Top 10 most Popular interview questions
Top 10 most Popular…
Here are the most commonly asked interview…
Search
Featured posts
  • Financial Analyst technical Interview questions
  • Technical interview questions for Mechanical design engineers
  • Software developer technical Interview questions
  • Technical Interview questions for Programmers
  • Python technical interview questions
  • SAP Basis technical interview questions
  • Basic technical interview questions
  • Interview questions technical
  • QA technical interview questions and answers
Copyright © 2022 l www.floydfairnessfund.org. All rights reserved.