Algorithms…necessary annoyance

Update: It was mentioned to me over the weekend that my title didn’t really tie into the content I presented (tip of the hat to Abbey Jackson!).  The original title of the post was supposed to discuss why I was continuing A&DS stuff even though I could spend that time learning new Apple APIs from the forthcoming Swift 4 release (the lab I work in does a ton of research using machine learning so I’d like to get a better understanding of how it works and it’s uses in app development).  The necessary annoyance part, to me, means that although I have a developer job, and I managed to get one without having to pass a rigorous A&DS interview, I do realize that potential future moves may require it and that I’m not particularly prepared for it. So rather than devote time to specific iOS-related stuff, I’m working on this instead. It’s interesting, but annoying too! 

A couple weeks ago, I hit the one year anniversary from when I graduate from The Iron Yard.  Since then, (after a couple months of interviewing) I’ve been employed by Emory University’s School of Medicine, seen The Iron Yard announce they’re shutting down, and generally just kept plugging away at learning all I can about Swift and app development.

There is always a general doubt that lingers when I attempt to teach myself new stuff.  Not having a background in CS, I occasionally have reminders about imposter syndrome (that voice that tells you that you aren’t really a developer, you’re faking it).  True, it’s stayed quiet for most of the last six months or so, but when I start learning something new and I’m not getting it, the voice gets a little louder.

When I was in interview mode last year, the common feedback I received after an interview was “your algorithms skills are really weak, you need to work on it.”  Algorithms and Data Structures (A&DS) is a course CS students take fairly early in their major. Bootcamps don’t look at it much.

Still, it’s a rite of passage that basically reminds me of the SATs in high school.  Colleges don’t really know how you are as a student compared with others, so there has to be some sort of fairly objective assessment that might indicate that you can indeed solve problems.  (* NOTE: this isn’t an endorsement of the SAT or ACT, and those scores aren’t an indicator of your success level in college and beyond, but, as imperfect as it is, a college having to decide among 10,000 candidates who may have a 4.0 in high school to fill 500 spots has to use something to distinguish the candidates and the test is the same across the country.)

Anyway, algorithm questions in interviews are just one of those things. I say this as a newer developer, as I have no idea what senior developer interviews are like.  When I was in the job search, a couple friends and I bought a subscription to a website that helps prepare for those type questions.  I used it for a couple weeks, but never made much effort at it (by then I had a job offer).

Fast forward to today and I’m looking over it again to see if some of those questions are easier for me now, than they were a year ago.  The short answer is: “not hardly”.  It’s a skill that must be worked at (at least for me). I’ve started working on one problem every two days during my lunch time to try and train myself to be better at these questions.  I’m in no hurry to change jobs as I really enjoy what I do, but I also don’t want to try and cram for stuff like this when the time does come for me to interview elsewhere.

And really, it doesn’t hurt to know this stuff anyway, regardless of whether I’ll ever be asked questions like this in the future.

So my first problem to solve was this:

Given a list of stock prices over the course of one day, write a function that would calculate the maximum profit you obtain from buying one share of the stocks.

So basically I have an array (list if you’re using Python) of stock prices.

let stockPricesYesterday = [10, 7, 5, 8, 11, 9]

The rules are:

  1. Buy one share and sell later (no shorting the stock)
  2. Account for if the stock price contained any negative numbers (or if all were negative, what’s the best “loss” you have.

Clearly look ing at the 6 prices, it’s easy to see that we need to buy when the price is $5 and sell when it’s $11.  But what if the array contained a price for every minute the market was open?  The function should work regardless of the size of the input.

So, looking at this and knowing the answer, I still had no clue how to get started.  I’ll use the array, look at each element and decide when to buy and when to sell.  Aside from that, I wasn’t really sure how to do this without the need to use multiple loops. (Big O notation is not something I’ll talk about at the moment, but basically it’s a measure of how long an algorithm takes to solve something…the shorter the better)

I’ll be the first to admit, that I had to use the website’s help on this.  I didn’t look at the solution, but I did have to keep choosing the “I need a hint” button.  Eventually I got to a point where I feel like I could get started.  These are the hints I was given.

  1. Maximum profit is the goal. We calculate it by selling at the current price.  It’s the difference between the current price and the lowest price we’ve seen so far.
  2. If the difference between the two (Current Price – Minimum Price) is larger than the current maximum profit that we’re keeping track of, then update the currentMaxProfit to the new profit.

So I have to keep track of several things. The minimumPrice I’ve seen, the maximumProfit I’ve seen thus far, the currentPrice I’m looking at and the currentProfit margin while I’m at the currentPrice.

The website mentioned an idea of using a “greedy” approach to solving this.  The greedy approach is basically keeping a running total of the end result (max profit) while I search through the list of numbers, and updating it along the way if I find a larger max profit.  (more information about greedy algorithms can be found here: Greedy Algorithm Basics

Once I had all this information (hints), I was ready to start writing a function.  I want the function to be able to take an array of prices, process each price and determine if the current price I’m looking at minus the lowest price I’ve seen thus far gives me a better profit than the currently held maximum profit. If the current price I’m looking at is lower than the minimum price, then I need to update that as well.

All my life I’ve never been one to make lists, or to outline. If a paper needed writing, I’d just start typing and edit on the fly.  This isn’t the best approach.  I must have re-written this function quite a few times as I made several mistakes.  As I look back on the answer, an outline might have been helpful.

  1. Find the minimum price (basically the first price in the array to start)
  2. Find the maximum profit (basically the difference between the first two prices in the array to start)
  3. Now, look at each price individually (i.e. Iterate through the array/list)
    1. find the current price (that is the price a that particular iteration array[0] is the first price, array[1] is the second price, etc…)
    2. find the current profit (difference between current price and the minimum price we originally set)
    3. Compare the current profit to our already found max profit.  If current profit is larger, then update max profit to be the current profit
    4. Compare the current price to minimum price set earlier.  If the current prices is lower, update the minimum price to be the current price
  4. Move on to the next price in the list and repeat

Strangely, once the blueprint (outline) is listed, the problem doesn’t seem to be that terrible.  However, my biggest problem was not being able to visualize what variables I’d need to keep track of.  I go back and forth on this.  Sometimes I just jump in and start adding a bunch of variables that I think I’ll need and delete the ones I don’t use.  Other times, I try to add as I go.  Neither way has proven to be very useful.  They’re both hit or miss.

I guess that’s why I need to practice.  Anyway, my final function wound up looking like this:

Screen Shot 2017-08-25 at 9.34.46 AM

Note: stock_prices_yesterday was a global property I declared earlier in the code…it’s just not visible.  I probably should update it to stocks[1] - stocks[0] instead.

This was question 1 of the website.  It took me about a 1/2 hour to work through. I’m trying to keep in mind that I haven’t done this in a while and I’m just getting my brain used to thinking this way.  Algorithms aren’t like riding a bike…yet.

Of course, I might go the rest of my career without every being asked to do this. But problem solving is a skill in constant need of refinement, and despite my outward appearance, I don’t want my brain to be rough around the edges!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s