Recursion…a slow-learner approach…

 

part-1

I think everyone has topics they pick up quickly. In high school, trigonometry just made sense. I attribute most of that to an amazing teacher, but sometimes you can just “see” the answer as you’re looking at a problem. It’s intuitive and very hard to explain why you know that your approach is going to work. It’s frustrating to your friends who ask “How did you do that?” The token answer is “I’m not really sure. I just followed the steps I was taught.”

I feel that way sometimes when I read others explain certain approaches to algorithms. I was asked once to write an algorithm that finds a sequence of Fibonacci numbers. I had memorized a recursive formula and reproduced it quickly…feeling proud of my mad memorization skills (note: I’m actually horrible at memorizing things. I have a biology teacher in high school that can attest to it…as well as a lit teacher who saw me struggle mightily to recite a monologue from Romeo and Juliet).

Then he asked me to explain what the algorithm was doing. I balked. “uh….well, the program keeps calling itself until it finds the answer.” “How does it know what the answer is?” “Well…..”

To his credit, he could have really lit into me for using a procedure I didn’t fully understand, but he didn’t. He also recommended me for the next round of interviews, so it wasn’t a deal-breaker, but it taught me an important lesson. Memorizing to “fake it while you make it” only works for the short-term. If asked to create another problem using recursion, I’d have had to end the interview. I had no clue.

So here I am a year and some months later, and recursion is still one of those magical concepts that looks like voodoo, but with some extra understanding of memory usage, is not a particularly difficult concept to comprehend, even if implementation still remains a mystery.

Borrowing some explanations from Aditya Bhargava’s “Grokking Algorithms”, I’m going to attempt to explain the mad science of recursion.

My daughter is constantly losing her clothes. She’ll always have items scattered all over the house, but has no idea where everything is. As a seven year old, her sleuthing skills are lacking. She gives a cursory glance of her bedroom, and immediately gives up and declares her clothes lost. So I ask her to make a list of all the rooms she’s been in since taking her clothes off yesterday and putting on her pajamas.

  • kitchen
  • bedroom
  • closet
  • bathroom
  • my office

So I ask her, well, you know the clothes have to be in one or more of the rooms, so how are you going to find everything you need?

  1. Go into room
  2. Look in all nooks and crannies of that room
  3. If all items found, I can go play
  4. If not, go to the next room on my list and repeat

Note: this still only works 1/2 the time because life is super stressful for a seven year old who doesn’t want to look and only wants to play, but still, the process remains true

So she goes into the kitchen, checks the pantry, checks under the table, checks the chairs, and checks the recycling bins (don’t ask, but seven year olds are weird creatures) and finds her socks.

“I found socks.” “Okay, go to the bedroom”

She starts off in the closet, searches under the bed, searches her bathroom she shares with her sister and then her chest of drawers. Lo and behold, she’s found her shoes. The logic behind this eludes me.

Now that she’s properly shoed, she proceeds through additional rooms until she eventually has been able to clothe herself. Finding one item is useful, but she’s not leaving the house with some of her items and not others. Satisfied that she can face her friends without ridicule, she goes off to enjoy her afternoon fun time where she solves big problems and plays in her make believe world.

What she’s really done is a recursive search for her clothes. She has a list of criteria to search, goes through the criteria on her list and stops when she’s found what she needs. Each item found represents the base case. It tells her when the search can stop.

So recursive functions have base cases. In that regard, they aren’t much different than a while loop. While some scenario is false, keep searching. When it’s true, stop the search. The recursion application comes from each item being needed in conjunction with each other item. A shirt is helpful, but a shirt with pants, shoes, socks, and jacket are all necessary before she’s ready to venture out the door.

In programming, something similar happens. But what happens with all those continued recursive calls? Are the numbers magically lost? Do they somehow keep track of themselves in the background? Is it part of the voodoo? Not exactly.

What I didn’t know is that the function is keeping track of its calls in something called a stack. A stack is short-term memory usage. When the function is done, the memory that was allocated for the function is done away with and gone. However, while the function is still calling (not yet completed), it still utilizes space on the stack. With recursive functions, each recursive call puts some new function on the stack. The stack behaves in a “last in, first out” order. Whatever the last allocation was made, it’s the first one back out when the function finally completes and the memory is no longer needed. To put another way, the top function has to finish first before any of the other calls below it in the stack can finish processing. I like to think of a can of Pringles in this case. The last Pringle chip put into the can will be the first one back out when the can is opened.

In this case, every time you call a function, the computers saves the values from its variables in memory on the stack. When you call a function from another function, the first call is on the bottom of the stack, with it’s values still being held. The next call goes on top of it, holding it’s values too. Here is a graphic example for the fibonacci function.

As an example, the first few Fibonacci numbers are: 0, 1, 1, 3, 5, 8, 13, 21

First: the function…

func fib(n int : Int) -> Int {
    if int <= 2 {
        return int
    } else {
        return fib(n: int - 1) + fib(n: int - 2)
    }
}

Note: my code above will not give an accurate answer for fib(0) which should be 0. I purposely did this to simplify my demonstration below.

So if I call fib(4), the resultant answer will be the fourth number in the fibonacci sequence, which is 3. Here is how it works…

This is the first call. fib(4) is typed in and n is assigned the value of 4. Looking through the function, n is not less than or equal to 2, so we go straight to the else statement. We need fib(4-1) + fib(4 – 2)…which we don’t yet have.

Our stack looks like this. fib(4) sits on the stack. In fact, it’s the only thing on the stack. It’s holding the parameter value that we called in the function, fib(4). Well, we don’t have any sort of answer for fib(4-1) handy, and the same holds true for fib(4-2), so we start with fib(4-1) or fib(3) and go through the same process. Now, we’ve kept, fib(4) on the stack to return to later so we can finish out that original problem, so now we evaluate fib(3).

fib(3) is now also placed on the stack, on top of fib(4) in fact, and it goes through the same evaluation process. Our stack now looks like:

fib(3) keeps ahold of its parameter variable on the stack, which may not seem important at the moment, but we’ll get there. The parameter 3 is not less than or equal to 2, so we move to the else statement and we’ve instructed it to return fib(3-1) + fib(3 -2) or rather fib(2) + fib(1). Since we don’t yet know the value for fib(2) or fib(1), we evaluate fib(2) and push another function onto the stack.

As you can see, our stack is starting to grow. If these recursive calls continued, we’d eventually run out of memory and cause a “stack overflow”–meaning there is no more room to put our function calls on the stack. However, every time a function can finally complete, in our case, the base case, it gets popped off the stack. In our case here, fib(2) will pop off the stack because it does satisfy the base case of being less than or equal to 2, so it returns the value of 1. This value can be substituted in the fib(3) call made earlier in place of fib(2) in the return statement and fib(2) gets popped off the stack.

So now our stack contains only fib(3) and fib(4). fib(3) asked us to return fib(2), which we found to be 1. Anytime a function completes, it is removed from the call stack. It’s values that were required by other functions are acquired so they can be used to finish their respective needs. In the case of fib(3), we’ve returned half of what it needs by find fib(2), but it also requires fib(1). This means another function call, fib(1), and another addition to our call stack. So fib(1) goes onto the stack and awaits evaluation.

fib(1)’s evaluation meets the base case, so it returns 1 as well. With evaluations for fib(2) and fib(1), fib(3) can finally be completed and return an answer of 2. fib(3) returns ‘2’ and leaves the call stack so we’re now left with fib(4).

At this point, you think, “Great! I have everything I need”. Not quite. fib(4) requires a return of fib(3) + fib(2). Well, we’ve only evaluated the fib(3) part. fib(2), although evaluated earlier as we travelled down the fib(3) trail, is no longer available to us as it returned its value to fib(3) and was removed from the stack. So now we must evaluate fib(2) again, obtain the returned value of 1 and have that answer returned as part of the fib(3) + fib(2) answer or 2 + 1 which gives us 3. The fourth fibonacci number is indeed 3.

Here is a broader picture of what is going on, step-by-step:

With recursion, small recursive calls aren’t that big of a deal. Yeah, it takes up more memory and repeats calls already made, but with small numbers, the runtime differences aren’t even noticeable. However, if you tried to compute fib(100), you’d run out of space in the call stack. The reason is this repeatedly having to find values you found before. Just to calculate fib(100), you’d have to find fib(99) + fib(98). fib(99) would have to work all the way down to fib(1) and then you could start working on fib(98) and repeat the whole process.

This is a better example of how many calculations must be computed using recursion.

Notice how many times fib(4) has to be computed just to solve fib(7).

There is a work around called a memoization table which stores each compute fib value if it doesn’t already exist and then checks the table first to see if a value exists before trying to compute. If it does exist, it uses the value stored. If not, it computes the value, and stores it in case it’s needed later. It reduces the number of computations needed and is very quick. I won’t be demonstrating it today, but will in a future post.

I blogged about this topic to get to a topic I’ve really been wanting to discuss: sorting algorithms. Merge sort was the first sorting algorithm introduced to me that used recursion and it completely baffled me. Quick sort actually made more sense, but it was introduced later. I wanted to blog about both, more to make sure I could explain it to myself than anything, but also to help those poor souls who suffered as I suffered when trying to wrap my head around what was going on. In order to do that, I needed a better understanding of recursion. It wasn’t until the stack was explained, that recursion made any sort of sense. Up until then, I considered recursion to be magic. It still is magic, just not as baffling as before!

Advertisements

How I wish I had learned algorithms…

algorithms-hire-humans
I’d like to watch Sheldon in an algorithm interview…

It was pretty clear after a couple of phone interviews last year, that coding your way through a problem testing your knowledge of algorithms is a common screening practice for most companies.  Truthfully, I don’t blame them. The quality of instruction in software development varies, whether it’s online tutorials, bootcamps, university courses, or what have you.

So after a few attempts at these questions, and performing my way out of a follow-up interview, I started asking others how to go about learning them. I received various answers from: “Buy ‘Cracking the Code’ and study it” to one interviewer telling me to go through a Algorithms textbook for about six weeks and I should be good to go. Some suggestions were more helpful than others. “How to Solve it by Computer” by R.G. Dromey was actually helpful for some introductory chapters. The person who suggested that also suggested I hold off on Steven Skeina’s “Algorithm Design Manual” until I felt a little more comfortable with understanding the basics.

I purchased a yearly subscription to the website “Interview Cake” and went through 8 or 10 problems over the year, but I always felt lost and didn’t know how to set up the problems, much less solve them.  I felt I was memorizing things without really understanding them.  If the problem changed slightly in an interview, I would probably have been lost.

I even made attempts at Coursera’s offerings.  Stanford, Princeton, and UC San Diego all had Algorithm courses and at one point or another I signed up and promptly forgot about it. It wasn’t until I had to pay for a monthly membership to Coursera that I took it more seriously.

Last week I completed the Algorithm Toolbox course through UC San Diego. Weeks 1 – 3 were pretty straightforward and I had little difficulty completing the required tasks, which a year ago were very difficult for me, which was encouraging!  Weeks 4 – 5 were much more confusing. Part of that was due to my watching the tutorials late at night when my brain was done for the day. Part was due to not really understanding the pseudo-code presented, nor the the mathematics of the algorithm being explained in the video.

I feared at the end of week 4, where I struggled mightily with solving a merge sort problem, that this would be another course I didn’t complete, though not for lack of effort. Try as I might, the recursive tasks being performed were baffling me. The videos, nor pseudo-code made sense and StackOverflow showed answers to similar merge-sort problems, but no real explanations. (Note: my next post will go over the 4 problems that I need to understand, but had difficulty figuring out.)

Week 5 was even worse. The concept of dynamic programming made sense, but implementing it was just baffling. While we normally get a week to solve our homework, the course is 6 weeks long with only 5 weeks of assignments to allow for a cushion to complete any of the weeks’ tasks. Week 5 took me two weeks to get through.

The first week was similar to week 4. Watch video, see the demo, take notes, try to implement the exact problem on my own before even looking at the homework. Sadly, I couldn’t even complete the sample problems they had. The pseudo-code confused me.

Fortuitously, I texted my bootcamp instructor from The Iron Yard just to check in and see how things were going. He and I chatted back and forth for a bit and then our topic landed on algorithm questions.  He mentioned he had just bought a copy of “Grokking Algorithms” by Aditya Bhargava. He said if I was struggling with dynamic programming, that I might want to give this book a try.  It took the math out of the book and used pictures and demonstrations to give just an overview of the topic instead of a deep dive.

I didn’t know this, but ‘grok’ means “to understand intuitively and thoroughly; to communicate sympathetically”. How true it turned out to be as I thought the book was written with me in mind!

Over the weekend between weeks 5 and 6 I flew through my copy of the book.  I started at the beginning even though most of the stuff was familiar with me. This book presented the best explanation of recursion I have seen. It drew pictures, it made me draw pictures, it asked good questions that helped me see the concept better. Finally, I got to the dynamic programming section, and sure enough the example he went through was almost identical to one of my homework problems.  The difference though, was that he offered no code, just a walkthrough of how the algorithm works–again, with pictures and a couple of practice examples for me to complete–also by drawing it out on paper.

I was able to complete the homework assigned for the final week and complete the course. The book didn’t give me the answers, or even any sort of pseudo-code, but it did give me an image to look at to understand what is happening with the memoization table being used to solve the question. As an added bonus, it went through Big-O notation for each chapter. This was something I felt pretty good about before I read it, but it further cemented my understanding.

So if you’re like me and struggle to stay focused when seeing single letter math variables representing pseudo-code that baffles you a bit, then here is what I wish I had known a year ago when I started trying to shore up this deficiency. Again, you may take a different path, but this is what I wish I had done.

  1. Buy and read “Grokking Algorithms” first. Buy a notebook and take ample notes. Attempt the exercises, take your time. Maybe even read the chapters twice. Time requirement: 1 – 2 weeks. Read it, and then read it again and take notes.
  2. Find a pdf or a copy of “How to Solve it by Computer” or a similar guide. It’s a really old book, and the program code is Pascal, but it’s a great transition from Grokking to math-based pseudo-code. It walks through the logic both in setting up the algorithm and how it works after implementing. It starts with small problems and builds from there. Time requirement: 1 – 2 months. I think working through a couple problems per day–AFTER READING THROUGH GROKKING!–would make this last a couple months
  3. Coursera course – The Algorithm Toolbox course was helpful in thinking about about both time and space complexity as the assignment submission did have limits on both. It’s 5 – 6 weeks long but depending on your speed and time commitments, can be completed in less time. (The course has starter files in C++, Java, and Python for each assignment, but will allow any other language as long as you write the tests for it.  I just stuck with Python.)  Time requirement: 6 weeks. This is a subscription-based course so it’ll cost your $49/mo until you finish the course.
  4. Advanced/Practical Algorithm Practice  – I may give Interview Cake another try, or I might start looking at “Cracking the Code” or “Algorithm Design Manual”. I haven’t quite gotten here yet as I’m debating on taking the next course in the sequence that UC San Diego offers “Data Structures” Time requirement: ongoing? I haven’t quite gotten there yet. But starting soon!
  5. Keep those skills sharp by working problems on HackerRank, TopCoder, ProjectEuler, etc…. Time requirement: ongoing…

Some might wonder if all this is worth it. It is entirely possible the companies you interview with pass out a coding assignment rather than a whiteboard challenge, and a good many are headed that way. My take on it is that it’s better to have it and not need it than need it and not have it. And if you have aspirations to land a job at one of the big tech companies like Google or Amazon, you’ll definitely be going through the whiteboard. For me, it’s helped increase my ability to solve problems at work, and I think, made me a more careful programmer.

One final note, this process I described above works for me. Don’t consider it to be the “only way”. I have a family whom I want to spend time with. 8 – 12 hour marathon sessions on algorithms and problem solving just don’t get to happen for me. My time allowed is about an hour at night and a few hours on the weekends. This is what I wish I had done with my nights for the past year instead of fumbling and failing from each half-hearted, overwhelmed attempt. I’ve completed #1 & #3 and currently working on finish #2 (I’ll have a link to a github repo I’m doing this in soon.).  I hope to start #4 by the end of next week as I just received my copy of “Cracking the Code” from Amazon over the weekend.

#fiyf

 

Learning is enjoyable sometimes…

A few weeks ago, I signed up to take an Algorithm and Data Structures course on Coursera. Part of my reason for this is that I like having stuff explained to me, but mostly because the course has deadlines and I find it easier to stay motivated if the threat of a “0” is looming.  The coursework can be completed in any language but they have starter files and tests already set up for C, C++, Java, & Python.  We’re welcome to use other languages, but we’d have to write our own tests.  Fortunately for me, my first language was Python so I’m dusting off those skills to complete the coursework.

I’m in week 4 of 5 in course 1 of six-course series.  While I don’t know if I’ll complete all six, I have gained some pretty nice insight into how to tackle problems.  Greedy strategies, divide-and-conquer, among others are explored and the course requires us to think about the time-limits required when we submit our assignments.  The correctness of the assignment is not only “can you write an algorithm to complete the task, but  also “can you keep the algorithm from going over the time limit?”  No brute-force/naive answers allowed!

Getting back into Python has been entertaining. Initially I had to write out my algorithm in Swift using Xcode’s playground, and then translate it into Python.  After a couple of weeks I’ve been able to transition into just using Python.  I still write it in Swift afterwards just to compare the syntax differences of the two, but it’s nice to be able to pick something back up after not using it for almost two years.

So what problems have I solved? We started with Fibonacci, which I’ve done before but this was the first time I spent really exploring how it is computed recursively vs. iteratively. Even if not optimal from a memory allocation standpoint (most of the time), recursive functions are really beautiful in their simplicity of code. It reminds me of a more elegant while-loop. Initially I begin to wonder why even learn to use recursive functions if they suck memory so quickly when dealing with large numbers, until we got to the Greatest Common Divisor (GCD) problem.

Note: Recursion in programming is a function that continues to call itself until some terminating condition is met.  I write the function and call the function in the same code. For example:

someFunction(parameter A, parameter B) -> Value {
// do some stuff
return someFunction(parameterA, parameterB)
}

Screen Shot 2017-09-22 at 9.23.00 AM

GCD is is comparing 2 (or more numbers) and finding a divisor that both numbers share. For example:

gcd(6,8) -> 2

2 is largest number that six and eight can both be dividing by. 3 works for 6, but not 8, 4 works for 8 and not six; you get the idea.

But what if the numbers are really large? say 2,877,988 and 956,432 ?

can you imagine write a loop that starts at 1 and divides all the way up to those numbers checking to see if both have remainders of 0 when being divided? How long that must take?!

Well the course let us know a secret about large numbers. The remainder taken when dividing the first number by the second number has the same GCD as the original two numbers.

Screen Shot 2017-09-22 at 9.23.52 AM
I didn’t really understand this until I saw it in action. (See below) Also, how did people figure this stuff out?!

So even though the number is smaller, the GCD is still the same.  So basically, to find the GCD of the original numbers, keep dividing the first number by the second number until the remainder is 0.  Once you have that, the first number left is your GCD.

Here is a better visual of “trick”:

Screen Shot 2017-09-22 at 9.29.38 AM.png
This made much more sense to me than the Lemma above.

I have two numbers, A: 3,918,848 and B: 653,264. I divide 3,918,848 by 1,653264 and the remainder is 612,320, which we will call A-prime.  I replace the A with B, and put A-prime in B’s old place and perform the same operation again.  I keep doing so until A-prime is 0.

In this case, recursion actually doesn’t take terribly long as it’s reducing the size of the number pretty quickly, unlike when building numbers up during a Fibonacci sequence (1, 1, 3, 5, 8, 13, 21…).  So an efficient way to find the GCD of two numbers actually is to use recursion, though probably not the only efficient way…

Here is the Python function:

Screen Shot 2017-09-22 at 10.00.43 AM

It amazes me how short it is.

Using that algorithm allowed me to complete another assignment that finds the Least Common Multiple.  I won’t go into it but they provided another tip on how to calculate LCM using GCD and again, it provides a short elegant solution.

I think the decision to take this course, for me, was the correct one.  I’m being exposed to some handy tools, I’m obligated to finish assignments since it is costing me a monthly fee and the assignment are providing a nice warmup to my day for me while I drink my first cup of coffee.  (Note: if I haven’t finished the problem after 10-15 minutes, I wait until my lunch break to finish).

This week we began looking at binary and linear search algorithms.  In the past, when I would look at these, I just tried to memorize it so I could regurgitate it if it came up in an interview. Now, I have a list of questions I ask myself and can look at mathematical explanations and make sense of them, which aids in my understanding all the more.

None of what I’m doing may ever be needed, but I’ve finally gotten to the point where I view learning algorithms as not a means to an end in a job search…which is where I was a year ago.  Instead, it has become “I really want to learn this stuff. I find it interesting.” Perhaps at some point I’ll even do it without having to spend money to motivate myself!

Tripped up on closures…again!

I’ve posted before about learning closures. Earlier this year, I was really making an effort to understand how they work. My examples, though, were contrived, or rehashes of other peoples’ examples. As such, my ability to remember them suffers. Context is so crucial to understanding something. I was working on a problem at work today where I need to sort an array of data.  For some reason, I kept blanking on how to do it.  I could write the code that does it, but I couldn’t explain it to myself.  Here was my problem…

var meetings : [Meeting] = [
Meeting(startTime: 0, endTime: 1), Meeting(startTime: 8, endTime: 11),
Meeting(startTime: 2, endTime: 8), Meeting(startTime: 10, endTime: 12),
Meeting(startTime: 9, endTime: 10)]

I wanted to sort the array by startTime. Had this been just an array of numbers, I could have sorted it pretty quickly. For some reason, though, having instances of a Meeting class was throwing me off. I knew that this code would give me what I needed:

let sortedArray = (meetings.sorted { $0.startTime < $1.startTime }) 

This is really shorthand syntax. I know it works, but I could not explain to myself. So I tried the long hand way. Unfortunately, when I tried to write it in a way that made sense to me, I kept getting errors from the Swift Playground page I was working in. Undaunted, I went looking for answers. The Apple documents offer this when working with closures:

{ (parameters) -> (return type) in (statements) }

Hmmm…okay, the parameters I want to pass in, I thought, were the startTime of the meetings. So I wrote something like this.

let sortedArray = meetings.sorted(by:
 { (s1,e2), (s2, e2) -> Bool 
in return s1 < s2 }
)

What I thought I need to pass into the closure were the start times and end times and sort it that way. I was way off.

As it turns out, when I create a new array like I did with sortedArray, if I declare the type of Array it is, in my case [Meeting], that is the parameter that is passed into the closure, not the properties within the Meeting instance. I didn’t discover this until I explicitly typed it out, and used my old friend, Option-click, which told me what type sortedArray was. When I began typing in the sorted function on the meetings array, Xcode offered this little gem:

Screen Shot 2017-08-28 at 8.02.04 PM

As it turns out, I’m not passing in meeting.startTime or meeting.endTime into the closure. I’m passing the entire Meeting instance. In fact, the closure, as seen in the screenshot, takes two meetings from the array and compares them to return a Boolean value. What it evaluated is everything after in. Once I have the meetings passed in, I can access any of it’s properties to do my comparison.

Screen Shot 2017-08-28 at 8.12.52 PM

What I didn’t understand before is that m1 and m2 are just parameter names for the objects I’m passing in. They represent the meeting instance, not the properties contained within the meeting…which is what I really wanted to evaluate.

So in the end, in order to explain something to myself, my code wound up looking like this:

let sorting : [Meeting] = meetings.sorted(by: 
 { (m1, m2) -> Bool 
in return m1.startTime < m2.startTime}
)

Yes, it’s not very “Swifty” and in the future, I can use the shorthand trailing closure syntax and be able to look at it and know exactly what is going on. However, using code and being able to explain what the code is doing is a better indication of understanding than blindly trusting something I find on the internet, see that it works, but have no idea why.

I realize this topic is pretty junior for many developers, but it further reinforces what I discovered when taking calculus in college. If you don’t use something often, you forget it. Code is no different. It also helps when learning something, you have a problem you are trying to solve rather than seeing someone else’s example and saying “Yeah, that makes sense.” I do not expect this to be my last post on closures. Especially since I still have more functional programming to learn!

On the upside, at least as I see it in my growth as a developer, I went to Apple documentation rather than Googling for an answer in StackOverflow. As tempting as it was to ask my fellow iOS Slack channel mates, I decided to see if I could figure it out first. When time isn’t urgent, it’s amazing how much patience I have when solving a problem!

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!

Adjusting the sails…

Most have heard the quote that I reference in my title.  I remember hearing it at my high school graduation. It’s pithy, memorable, but for a long time, to me, utterly useless.  I had no context to apply it.

That all changed on Memorial Day last month.  For those unfamiliar, the last Monday in May is Memorial Day, a time where we honor the memories of soldiers fallen to defend the United States. For most, it’s a long holiday spent at the lake or a cookout. For others it is remembering loved ones that paid the ultimate sacrifice.

For the past month, I’ve taken a more pro-active role learning delegates and protocols in swift.  Most documentation or how-to videos involved protocols with extension, which provide a default implementation on how to use the protocol.  It’s much harder to find a good tutorial to pass some data from one file to another via a delegate.  I’ve tried to find good examples that help to answer my questions instead of bringing up more.  Much of what I’ve found hasn’t been helpful.  For a couple of weeks, this kept me pretty much at a standstill.

Fast forward to Memorial Day.  It’s a CrossFit tradition to perform the Hero WOD “Murph” on Memorial Day. Michael Murphy was a Navy SEAL who sacrificed himself to get a radio message to help his fellow SEALs.  Part of his story is told in the book & movie “Lone Survivor”.  Murph’s favorite workout when he couldn’t get to a box was a 1 mile run, 100 pull-ups, 200 pushups, 300 air squats, and then finish with a 1 mile run…all while wearing a 20 lb. weight vest.

The-Murph

So I participated in Murph for the first time over Memorial Day. There is nothing glamorous about it, at least from my perspective.  It’s a way to honor his memory as well as others who have fallen to defend the United States.  There is very little fanfare.  We show up, we workout, mostly in silence, and then we encourage others who are still trying to complete the workout.

I’ve been battling shoulder issues for the past few months and was recently allowed to resume so activities that involve the shoulders.  However, I was really worried about the pushups in Murph.  I decided to scale them so as not to face the wrath of physical therapist and endure more therapy (aka torture) at her hands.  So I did pushups from my knees rather than the standard.  At around 120 reps, my shoulders started complaining.  What to do?  End my workout, disappointed in myself and feeling like my contribution towards Murph’s memory didn’t count?   I came really close to calling it.  However, in the midst of the heat, humidity, and mild discomfort (yes, that’s sarcasm), the whole quote about adjusting the sails popped up.  I think there is something spiritual about trying to stretch your physical capabilities.  In this case, I had a moment of clarity.  An “a-ha!” moment.   Rather than just stop the workout, just change what you’re doing.  So I went to sit-ups for the rest of my pushups requirement.   Sure, it’s not the prescribed “Murph” (not that I was anyway as I wasn’t wearing the weight vest), but it’s still a way to honor his workout, and not give up.

So at the hour and twenty minute mark, I finished my final 1 mile run and completed my first Murph.  Of all the accomplishment I’ve had, this wasn’t bound in glory, a sense of accomplishment or any sort of fanfare.  Instead, I felt grateful.  I had the privilege of completing Murph.

The following Tuesday at work, sore from the previous day, I decided to change my approach to learning how to use a delegate pattern with protocols.  Instead of reading and searching for tutorials, I searched for code.  Any sort of delegate paired with a protocol.  How did they use it?  What triggers the delegate?  How do I assign it to View Controller that I need to perform the action.  I stopped waiting to have someone explain it to me, and instead went and found what someone did, and try to explain it to myself.

The end result is that I gained a small foothold in how delegates work.  I’m no expert.  But I was able to accomplish what I wanted, learn to adjust during my learning process, and once again, use a lesson learned in CrossFit in my career.  It never ceases to amaze how I can learn career lessons from a non-career related part of my life.

 

 

What a difference a year makes…

 This week marks a year when I left for Utah to start The Iron Yard Mobile Engineering bootcamp. I remember being worried about not being smart enough or able to comprehend fast enough the knowledge transfer about about Swift, Objective-C and iOS Development. If I’m honest, though, I still worry about that…it’s just the topics are a bit more advanced now than they were then.

Someone asked me the other week, “Would you do it again?”. I answered with an emphatic “YES!”. I took a major chance by quitting a stable job in the hopes of landing one in the tech industry. Corporation, dev shop, non-profit? I wasn’t sure where I’d end up. University never entered my mind though. I’ve now been an iOS Developer for Emory University for 8 months. I’ve helped build two games within the same app. The games could be stand apps in their own right, but we’ve kept them together. We’re also starting the 3rd game this week.

I had the same thought, over and over, as I made the 1900 mile drive out to South Jordan, Utah last year…”What if you make it through the bootcamp, but can’t find a job?” Well, it took a couple months of intense searching, failing (aka learning) at multiple interviews, but that, too, took care of itself.

I’m heading out this week to visit the campus and say my goodbyes to the staff. The Iron Yard – SLC is closing it’s campus so it’s unlikely I’ll cross paths with them very often. I’ll actually be flying out on the same day I left last year, just not with the same worry and anxiety that sometimes overwhelmed me then.

Donuts, catching up with my instructor, seeing the campus director (and beating him at ping pong!), visiting with some of my cohort (if they come visit!), experiencing the gorgeous Utah geography and even seeing my parents, who just happen to be out there as they RV their way through the country are all in my plans. This is definitely a low-stress trip compared to what I embarked on last year.

I don’t think much about the work I put in to get where I am. When you enjoy something, it doesn’t feel much like work. It feels like legos. I used to sit for hours and build stuff out of legos. Whatever my mind could think up, I’d try to build. The same holds true for coding. I put in 60 hours a week at the bootcamp, 60 hours a week during my time being unemployed, and probably still contribute the same both at work, home, and the volunteer organization I’m a part of. The hours fly by. I love learning new topics. Still, had I put the bare minimum in, I’m certain I’d still be searching for that first dev job.

I have a couple posts lined up in the next week or so regarding stuff I’ve been trying to learn so I hope to post soon. I try to let this blogging thing happen naturally rather than try and force something out there.

But of this week, I’m going to enjoy my time in Utah, recharge with fellow coders, eat some fabulous donuts, and reflect on how fun this journey has been.