Solving the Collatz Problem with an Audience

Before my first technical interview (scheduled, unfortunately, at 7:00 PM on a Friday), I spent some time on the interwebs trying to figure out what to expect. My initial google search was actively unhelpful:Image

 

Well, I wasn’t worried about tears before, but I certainly am now. Thanks, Google!

I also spent some time on Interview Cake, which was less Ruby-specific than I’d like, and Project Euler, which is fairly language-agnostic but math-heavy. And, incurable procrastinator that I am, much of my hands-on-keyboard time leading up to my interview was spent down rabbit holes and cleaning my kitchen.

Even so, I made it through my first mock technical interview tear-free; my interviewer was helpful and friendly and gave objective, specific feedback at the end. Maybe I didn’t hit a home run, but I didn’t strike out and it was actually pretty fun. When I signed out of the Google Hangout, I actually went and refactored my code. Here’s the problem and how I solved it the second time around:

The Problem

Image

Starting Out

Since we’re solving this problem in Ruby, we know that we want to construct our answer in an object-oriented way. On a basic level, an object-oriented program is made up of classes and objects; a class is like the recipe that shows you how to make an individual object like a red velvet cake. In other words:

Object-oriented applications are made up of parts that interact to produce the behavior of the whole. The parts are objects; interactions are embodied in the messages that pass between them.

– Sandi Metz, Practical Object-Oriented Design in Ruby (p. 3)

This fits perfectly into my Collatz problem because I want to test a bunch of numbers to see which one produces the longest array. To do this, I’ll put all of the behavior in a Collatz class and then ask it to churn out a million instances.

Image

To move on with this, I’ll have to figure out how to pass my number argument through to any other methods I create. I’ll also have to save each answer in a chain to count its length later. I chose to do this by defining an array as an instance variable – which, by definition, is available to any other methods in a given class – and started out by shoving my argument number into the array I just made. I could have done this one of two ways:

Screen Shot 2014-04-18 at 8.55.10 PM

Making It Do Stuff

Now the hard part: Adding the logic. I won’t go into the gory details of how I arrived at my first answer, because it took me the better part of an hour. It can generally be expressed in psuedocode as “until the last element in my array is 1, check to see what n looks like. Do the first thing if it’s even, the second thing if it’s odd, and give me your answer.”

Image

This solution works, but unfortunately takes a long time:

Collatz benchmarked

Yikes. That’s slow. I’m no computer science expert, but I did some research on calculating the Big O value of this function to see just how slow it is. Here’s the super high-level overview:

1. Multiply the n value for nested loops
2. Add the n value for sequential loops
3. Drop everything but the largest term
5. Conditional checks (e.g., “if n is even” in our case) are constant-time operations, or O(1)

So what really kills me here is the combination of two loops. When you’re counting up to a million, that adds up fast. But how could I do it better?

One option is memoization, which lets us store a computed value in a table and retrieve it later. Since we’re iterating over something a million times (twice!), this could be pretty useful. I can do this by setting up a hash in my class and then writing values to it, like this:

Screen Shot 2014-05-02 at 12.31.27 PM

I can also make my solution faster by taking advantage of Ruby’s attr_reader and attr_accessor (as this blog post demonstrates nicely). Now, my setup looks like this:

Screen Shot 2014-05-02 at 12.34.23 PM

Ultimately, the logic of the solution is very similar, but it does a better job of harnessing some of Ruby’s built-in strengths to move faster:

Screen Shot 2014-05-02 at 1.08.01 PM

How much faster? A lot faster:

Screen Shot 2014-05-02 at 1.07.28 PM

Much better 🙂

Advertisements
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

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 )

w

Connecting to %s