I originally shared this story on medium.com
This is the first installment of what will be a series of Python coding practice problems, my approach to them and lessons learned from them. The ideas are based on the principles of practicing for coding interviews laid out by Parker from https://www.interviewcake.com/.
First problem:
Greedy algorithmic pattern, e-mail #2 example pattern #2
https://www.interviewcake.com/question/python/stock-price
The example given:
stock_prices = [10, 7, 5, 8, 11, 9]
get_max_profit(stock_prices)
# Returns 6 (buying for $5 and selling for $11)
This example problem is for the “Greedy” algorithmic pattern, so we need to keep track of the best answer “so far.”
I felt that I needed to know the indices of the list to compare them, so I used enumerate. I needed to compare each item to the items that come later and find the best number. I knew I only had to compare to the items that come AFTER each item because you have to buy FIRST and THEN sell. Each index of the list represents the price of the stock at a given minute.
This is the solution I came up with, and it’s kind of a go to style of problem solving for me when it comes to this kind of problem (comparison of items within a list), I’ll almost always use a nested for loop. Even most of the StackOverflow answers for Python list comparisons that I looked at used them. When I had finished this solution I went to answer the question, but when they mentioned that it could be done without nested for loops, I was really thrown for a loop. I had no idea how to handle it any other way. What I learned from Parker is that nested for loops are not the most time efficient solution because they take O(n2) time instead of O(n) time. After spending a little time trying to figure it out, I finally gave up and took a look at his solution:
The difference between our solutions is that because my solution loops through the list, and then loops through the list again FOR EVERY ITEM in the list, it would take exponentially longer to implement my solution than his solution which just loops through the list one time. My solution is fine for relatively small lists, but gets problematic as they grow larger.
The lesson here is that by thinking a bit more about the problem, and understanding which variables to keep track of, we can save a lot of computation time when dealing with big lists. In this case, I knew I needed to keep track of the max profit as I went, and I could have avoided looping through the list twice by simply keeping track of the lowest price I had seen so far, and checking to see if subtracting it from the current price would give me a new max profit. The next time I encounter a problem like this, I’m definitely going to think a bit harder about which variables I could keep track of to keep processing time at O(n), and just pass through the list once.
If you have any thoughts or feedback, please don’t hesitate to leave a comment! I’m doing this to learn and grow, so if you have insights, let me know!