Fluxus Frequency

How I Hacked The Mainframe

Building a Ruby List Comprehension

This post originally appeared on Engine Yard. It was also a featured article in Ruby Weekly.

As developers, we’re in the business of continually bettering ourselves. Part of that process is pushing ourselves to learn and use better code patterns, try new libraries, and pick up new languages. For me, the latest self-learning project has been picking up Python.

As I’ve worked with it, I’ve discovered the joy of list comprehensions, and I’ve been wondering what it would take to implement a similar syntax in Ruby.

I decided to give it a try. This exercise yielded several insights into the inner workings of Ruby, which we’ll explore in this post.

Read More.

Better SOA Development With Foreman and NGINX

This post originally appeared on Engine Yard. It also appeard on the Quick Left Blog.

Everyone knows more is better. More kittens, more money, more apps. Why settle for one Ruby project, when you can have three? We’ll take one Rails app for authorization and one to serve an API. Hey, let’s throw in a Sinatra proxy server serving up an AngularJS app to while we’re at it! Now we’re cookin’!

There are many ways organizations stand to gain by splitting their application into multiple projects running in symphony. If we’re being good programmers and following the Single Responsibility Principle (SRP), it makes sense to embrace it at all levels of organization, from our methods and classes up through our project structure. To organize this on the macro level, we can use a Service-Oriented Architecture (SOA) approach. In this article, we’ll explore some patterns that make it easier to develop SOA apps with a minimum of headaches.

Read More.

Getting Started With Active Job

This post originally appeared on Engine Yard. It was also a featured article in Ruby Weekly.

With the announcement of Rails 4.2 came some exciting news: Rails now has built-in support for executing jobs in the background using Active Job. The ability to schedule newsletters, follow-up emails, and database housekeeping tasks is vital to almost any production application. In the past, developers had to hand-roll this functionality, and configuration varied between different queueing services. With the release of Rails 4.2, setting up jobs to be executed by workers at a later time is standardized. In this article, we’ll take a look at how to set up Active Job and use it to send a follow-up email to a new user.

Read More.

Wrapping Your API in a Custom Ruby Gem

This post originally appeared on Engine Yard.

In the modern web, API-based projects are becoming the norm. Why? For one thing, APIs are necessary to serve Single Page Applications, which are all the rage right now. From a business standpoint, APIs give companies a new way to charge others for access to their data. If you are part of a company that offers such a service, a great way to generate interest in your API is to offer a Ruby gem that makes fetching and consuming your data easy for Ruby developers.

Read more

Using Services to Keep Your Rails Controllers Clean and DRY

This post originally appeared on Engine Yard.

It also appeared in Ruby Weekly.

We’ve heard it again and again, like a nagging schoolmaster: keep your Rails controllers skinny. Yeah, yeah, we know. But easier said than done, sometimes. Things get complex. We need to talk to some other parts of our codebase or to external APIs to get the job done. Mailers. Stripe. External APIs. All that code starts to add up.

Read more

Looking for a Needle in a Haystack! (or Using Ack to Improve Your Development Workflow)

This post originally appeared on the Quick Left Blog.

Every day when I’m programming, I invariably come to a point where I’m looking for a certain line of code in my project. I could just use my editor’s “find in files” feature and look for it, but sometimes I need more fine grained control. What if I want to find all the lines of code that don’t contain a certain phrase? What if I want to search on a Regular Expression? What if I want to easily save the search results to a file?

When I need MOAR POWER in finding something, I turn my favorite command line search tool: ack. In this blog post, we’ll explore the ins and outs of this fantastic application.

Read more

AngularJS Unit Testing, for Real Though

This post originally appeared on the Quick Left Blog.

It also appeared as a featured article in JavaScript Weekly.

When it comes to contemporary web development, AngularJS is the new hotness. Its unique approach to HTML compilation and two-way data binding make it an effective tool for efficiently building client-side web apps. But when it comes to the testing, many tutorials on the interwebs hand-wave testing. This article covers some of the “gotchas” you’ll come across when trying to test Angular. Let’s build our chops, so we can get into a “Red-Green-Refactor” flow when testing Angular.

Read more

Five Capybara Hacks to Make Your Testing Experience Less Painful

This post originally appeared on the Quick Left Blog.

Everyone knows it’s important to test your code. But sometimes, the experience can be a little bit painful. Ok, sometimes it’s very painful. Like when you’re trying to feature test a JavaScript-heavy Rails app.

What to do? Abandon the tests? Never! Smokey, this is not ‘Nam. This is coding. There are rules.

Read more

Service Oriented Architecture

We just finished up our penultimate project at gSchool, an application built using a Service Oriented Architecture (SOA). The project ideas were generated in small groups, and focused a the theme of health and wellness. Once the ideas were decided, our teacher Jeff Casimir generated a randomized list of the students, and we drafted projects.

I went first, and selected an idea that was close to my heart: an app to help home vegetable gardeners plan out their beds for the season. Having spent several years as an organic farm worker, garden company owner, and home garden hobbyist, I was excited to use this app. Every spring, before the ground warms up, my partner and I sit down with a pencel and graph paper to plan out the different beds in my garden: what will go where, how it will be spaced, when it will be harvested, and what we’ll plant there afterwards.

I had big hopes for our project, dubbed Planting Season (code). A user would have several gardens, each with many beds. The app would keep track of her plans from month to month, and she would be able to click on a month to see what she’d planned to plant there, which spots were empty, and which plants were ready for harvest. It would find her USDA Hardiness Zone and suggest plants well-suited to grow there. If there was impending frost, or a bed needed water, it would send her a text message, email, or a Google voice message.

Ah, the dreams of the young and inexperienced…

Planting Season’s Structure

Two of my group members had just completed FooFoBerry, an SOA app that exposed and consumed APIs from various project management tools, such as GitHub, Travis, and Code Climate. With their experience setting up services, I figured that getting the project up and running would be a breeze. In practice, it was more challenging than I expected.

I’m a big fan of a “lean startup” / “minimum viable product” approach in my projects. I like to get a simple product up as fast as possible, then expand on it, adding value. Given that we had three weeks, we planned three iterations for Planting Season:

Week 1 - Put up a landing page where users could enter their email to be notified when the app was ready.

Week 2 - Change the landing page to allow users to sign up or sign in, then send them to a dashboard page, where they could add and remove plants from a single garden.

Week 3 - Add functionality for multiple beds, text and email weather notifications, and a timeline for the garden through the year.

With this functionality in mind, we decided to build the following services:

  1. Landing Page App
  2. User Authentication App
  3. Client-Facing Dashboard (“Coordinator”) App
  4. RESTful JSON API with Bed and Plant data
  5. A gem to facilitate communication between the Dashboard and the API
  6. External Services - Weather and Geolocation APIs

Here’s how the project ended up looking in the end:


A web application diagram

Project Management & Workflow

Over the course of gSchool, I’ve been learning a lot about the social aspect programming. I worked solo in my ealiest projects, then graduated to pairing, and later went on to work in groups of three or four. In the beginning, I was just doing my own thing, but as I started getting into the larger groups, project management became a key skill. I’ve found myself in the role of Project Manager in many successive projects. The first couple of times were messy: I didn’t make enough space for people to express how they were feeling at our standups, our iteration planning was nonexistent, and I didn’t understand how to use Pivotal Tracker at all. As I learned from these experiences, I began to firmly value things like daily standups with technical and emotional checkins, persona and wireframing UX design, iteration planning, proper use of Pivotal Tracker, consistent version control practices, and continuous integration.

We started Planting Season with the best of intentions, but this time around, it proved harder to practice these strategies than I hoped. At our checkins, it was clear that we were all feeling unfocused and pulled in different directions by job applications and interviews, burnout, and Jeff’s absence after his wife gave birth to their latest addition to the family. We planned our iterations, but we didn’t meet the first one because a couple of us were out of town or at interviews. Soon we fell behind. On top of that, Pivotal Tracker stopped letting us edit our stories, because our free trial was expired. The Travis CI specs wouldn’t pass, because the specs couldn’t talk to the API (more on this in a minute). Of all the agile practices we hoped to use, only the UX planning went well.

Nginx, Passenger, and VPS Woes

Our troubles were compounded by the difficulty of getting our services to talk to each other. Our plan was to run Foreman locally, booting our apps onto different ports on localhost, then use Nginx to route everything through different namespaced routes on port 8080. Getting Foreman up and running was easy enough, but Nginx was a bear to configure. Meanwhile, getting Phusion Passenger and Nginx to play nicely on our VPS was also a struggle. It turns out that you have to install Passenger first, then add Nginx as an extension to it. If you install Nginx first, you end up with two conflicting versions. Additionally, one of our team mates was having RVM issues, and had to reinstall Ruby and all of his gems twice.

In the second week, we lost two solid days of of development time to the fight with the Nginx config file, Passenger, and RVM.

For posterity’s sake, here’s a snapshot of the nginx.conf file that finally worked for local production:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
worker_processes  1;

error_log  logs/error.log;
#pid        logs/nginx.pid;

events {
    worker_connections  1024;
}

http {
    include       mime.types;
    default_type  application/octet-stream;
    #passenger_root /usr/local/opt/passenger/libexec/lib/phusion_passenger/locations.ini;
    #passenger_ruby /usr/bin/ruby;

    server {
        listen       8080;
        server_name  localhost;

        # PLANTING SEASON

        # Landing Page
        location / {
          proxy_pass        http://127.0.0.1:3000;
          proxy_set_header  X-Real-IP  $remote_addr;
        }

        # Auth
        location /auth {
          proxy_pass        http://127.0.0.1:3001;
          proxy_set_header  X-Real-IP  $remote_addr;
        }

        # Coordinator
        location /dashboard {
          proxy_pass        http://127.0.0.1:3002;
          proxy_set_header  X-Real-IP  $remote_addr;
        }

        # API
        location /api {
          proxy_pass        http://127.0.0.1:3003;
          proxy_set_header  X-Real-IP  $remote_addr;
        }
   }
}

Testing Troubles

Once we had the services running on a single port, we figured everything would be gravy. We added the VCR gem to save the results of our API calls, and began testing. We covered the landing page, auth app, and our gem.

Then I started to dig in on some Capybara tests for the coordinator app, and had some major headaches. In order to view the dashboard, I needed to set a signed cookie to simulate the authorization app. Easy enough. All you have to do is use:

1
page.driver.browser.set_cookie 'user_id=1'

That is, unless you’re using Poltergeist for a JS driver. Then, you clearly use:

1
page.driver.set_cookie("user_id", 1)

But now, I had a different problem:

1
2
3
Failure/Error: within '#bed-functions' do
     Capybara::ElementNotFound:
       Unable to find css "#bed-functions"

Using the launchy gem and save_and_open_page, #bed-functions was there, all right. I could feel another configuration battle coming on as we headed into the third week.

Getting Back on the Horse

On Monday morning of the week the project was due, we had little to show for our two weeks of work. There were services, but they couldn’t talk to each other on the server. There were mock-ups, but the CSS wasn’t in the views yet. The tests were thin. We had a meeting with Jeff, and told him we planned to bolster the test coverage and solidify what we already had. His advice: “that would be a good idea if you had a thing, but right now you don’t. You might want to make a thing first.”

So we saddled up, and the cowboy coding began.

jQuery Sparkle

The next two days were actually pretty fun, if a little painful (coding without tests makes me uncomfortable). We got the CSS hooked up, integrated with the weather service, and added a healthy dose of JavaScript to the dashboard. Although we would have liked to explore Ember.js, we decided to stick to plain old jQuery in the interest of time. We quickly coded 275 lines of jQuery sparkle, and we had a thing! If you’re interested, go check out what we made!

My favorite part was adding the ability to click and drag on the garden bed squares for multi-selection. Here’s what that looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$(function() {
  window.isMouseDown = false;

  $('td').mousedown(function(e){
    window.isMouseDown = true;
    var element = $(e.currentTarget);
    var thisClass = $(this).attr("class");
    toggleSquare(thisClass, element);
    return false;
  });

   $('td').mouseenter(function(e){
    if (window.isMouseDown){
      var element = $(e.currentTarget);
      var thisClass = $(this).attr("class");
      toggleSquare(thisClass, element);
    }
    return false;
  });

  $(document).mouseup(function () {
    window.isMouseDown = false;
  });

});

If you want to see more of what we did with the JS, you can check out the code on GitHub.

Conclusion

From the beginning of gSchool, the SOA project was one of the things I was looking forward to the most. Although Jeff said he thought that it was probably “not a reasonable thing” to start a project from the beginning with SOA, I set out with the highest of expectations. But the problems along the way were numerous.

The job search was a distraction. But more troubling to me was the difficulty of testing. I’ve gotten really comfortable with using Travis CI, and driving my development with Pivotal Tracker user stories translated into Capybara feature tests. It was really hard to do with services. Between setting up Passenger and Nginx and the testing troubles, we lost a lot of time on configuration.

Reflecting on the experience, I’d say that SOA is probably a practice better left until it is needed. If I were in charge building a new app for a startup, I would still start by iterate on delivering business value with successive MVPs. When I began to feel the pain of scaling, then I would think about splitting off services.

However, it’s possible that I’ve only come to this conclusion because the process was so painful. There’s another way of looking at this.

Here’s a lesson that I’ve learned about programming again and again over the last six months:

1
2
3
The first time you do something it is hard and doesn't make any sense.
The second time you do it, it seems vaguely familiar, and makes a little bit of sense.
From then on, it makes sense and feels natural to do it.

If this is true (which it seems to be for me), then it might actually make sense to build apps using services from the get go, if you expect them to have to scale down the road. I’d love to nail down a workflow for getting Passenger, Foreman, and Nginx set up in less than 30 minutes. I’d also like to learn how to better test services and get them set up with continuous integration. I think that if I understood these things, SOA would be a tool I’d be a lot more likely to reach for.

If you have any tips about these two aspects of services, let’s talk! Tweet at me: @fluxusfrequency.

Building a Binary Search

A couple of days ago I had an interview with a big startup in Boulder. I was really excited about the possibility of working there, because they solve some really hard problems on a daily basis, and because I’ve heard great things about their office culture.

It was just supposed to be a quick interview, but it ended up taking a few hours. First, I met up with the CTO. It all started off innocent enough. We went to a restaurant on Pearl Street for lunch. He asked me about my background and skills, and I asked him about the company. We shared personal stories about the flood last summer. After hearing about the way he treats his workers (like adults), and some of the technical details of what they were working on, I was even more excited about the company. We headed went to a coffee shop for a drink, then went back to the office.

When we got there, he introduced me to the head of the team that the best fit for me if I worked there. The team lead, one of his coworkers and I headed back to the coffee shop. We chatted about Rails, Exercism, TDD, and Ember.js, and life at their company. Pretty soon, the CTO came in again. Seeing that we were still talking, he asked the team lead to take me back and “dig in technically” a little bit.

We went back to the office again, and found a conference room. He asked me to solve FizzBuzz in JavaScript. I fired up Jasmine-Node and built it with tests the whole way. That went fairly well, I thought. Then he asked me a couple of CSS questions. I answered them, and he said that I answered them better than many of the people he interviews.

Finally, we came to some algorithm questions. Although I’ve learned a lot at gSchool in the last five months, algorithms are something that I haven’t spent as much time on, yet. I’ve only had enough programming context to begin understanding them for the last two of those months. I’ve played around with them as much as I could, solving Linked List, the Luhn Algorithm, Nth Prime Factor, Sum of Squares, and Binary Search Tree. I’ve also had a go at writing the MD5 algorithm. But compared to someone with a four year CS degree, I haven’t had much time to get comfortable with them.

My interviewer drew an array on the board, and asked me how I would find a given element’s position within 2-3 queries. I thought about it, made a guess that it had to do with bit operators, and finally conceded that I had no idea. My heart sunk. Things were going so well. When I asked for the solution, he told me that it was to use a Binary Search. I got excited, because I had done a Binary Search Tree. But no, this was just plain old Binary Search.

Bitten that I didn’t know how to do Binary Search, I set out to build it on my own. This rest of this post is a walkthrough of how I solved it.

Research

First, I visited Wikipedia and read up on Binary Search. It was pretty easy to follow. So easy, in fact, I decided to lift some of the text verbatim and translate it into a set of tests to drive my implementation. Here’s what I found:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Searching a sorted collection is a common task. A dictionary is a sorted list of
 word definitions. Given a word, one can find its definition. A telephone book
 is a sorted list of people's names, addresses, and telephone numbers. Knowing
 someone's name allows one to quickly find their telephone number and address.

If the list to be searched contains more than a few items (a dozen, say) a
binary search will require far fewer comparisons than a linear search, but it
imposes the requirement that the list be sorted.



In computer science, a binary search or half-interval search algorithm finds
the position of a specified input value (the search "key") within an array
sorted by key value.

In each step, the algorithm compares the search key value with the key value of
the middle element of the array.

If the keys match, then a matching element has been found and its index, or
position, is returned.

Otherwise, if the search key is less than the middle element's key, then the
algorithm repeats its action on the sub-array to the left of the middle element
or, if the search key is greater, on the sub-array to the right.

If the remaining array to be searched is empty, then the key cannot be found in
the array and a special "not found" indication is returned.

A binary search halves the number of items to check with each iteration, so
locating an item (or determining its absence) takes logarithmic time. A binary
search is a dichotomic divide and conquer search algorithm.

I decided to take this step-by-step description and turn each step into a test.

Setting Up the Binary Search Test & Class

The first step was to create an object that knew about “an array sorted by key value”, or as I like to call it, a list. I wrote a test:

1
2
3
4
5
6
7
8
class BinarySearchTest < MiniTest::Test

  def test_it_has_list_data
    binary = BinarySearch.new([1, 3, 4, 6, 8, 9, 11])
    assert_equal [1, 3, 4, 6, 8, 9, 11], binary.list
  end

end

And a class to make it pass:

1
2
3
4
5
6
7
8
class BinarySearch
  attr_reader :list

  def initialize(data)
    @list = data
  end

end

That was easy! Next, it needed to be able to check whether the list was actually sorted, so I wrote a test to make sure it would throw an error if it wasn’t:

1
2
3
4
5
def test_it_raises_error_for_unsorted_list
  assert_raises ArgumentError do
    BinarySearch.new([2, 1, 4, 3, 6])
  end
end

To make it pass, I implemented the following check: compare the input with itself in sorted form. Not that elegant, but it worked:

1
2
3
4
5
6
7
8
9
class BinarySearch
  attr_reader :list

  def initialize(data)
    raise ArgumentError unless data.sort == data
    @list = data
  end

end

According to the Wikipedia article, the algorithm was going to have to find “the key value of the middle element of the array”. So I wrote a test to make sure that it knew where the middle of its list was:

1
2
3
4
def test_it_finds_position_of_middle_item
  binary = BinarySearch.new([1, 3, 4, 6, 8, 9, 11])
  assert_equal 3, binary.middle
end

This was fairly trivial to solve:

1
2
3
4
5
6
7
8
9
10
class BinarySearch
  attr_reader :list

  # Code omitted

  def middle
    list.length/2
  end

end

With the class all set up, I turned my attention to the actual search algorithm itself.

Building the Search Algorithm

The goal was to search for the index of a specific element, so I wrote a test for a method that did that:

1
2
3
4
def test_it_finds_position_of_search_data
  binary = BinarySearch.new([1, 3, 4, 6, 8, 9, 11])
  assert_equal 5, binary.search_for(9)
end

Next came the hard part. I took the text from Wikipedia and broke it down into pseudo-code:

  • Get the search value
  • Find the middle element in the list
  • Check if they are equal
  • If they are equal, return the position of the middle element in the list
  • If they are not equal, branch:

If the search key is less than the middle index:

  • Cut the list we’re searching in half
  • Instantiate a new BinarySearch
  • Pass the first half of the list into it
  • Call the search method on the new object, with the same search key
  • Repeat until the keys are equal
  • If they’re never equal, raise “Not Found”

If the search key is more than the middle index:

  • Cut the list we’re searching in half
  • Instantiate a new BinarySearch
  • Pass the second half of the list into it
  • Call the search method on the new object, with the same search key
  • Repeat until the keys are equal
  • If they’re never equal, raise “Not Found”

With this plan in place, I started to build the method. First, I created the method and passed in the search key:

1
2
3
def search_for(key)

end

Then I checked it against the middle element in the list, returning the index if they were equal:

1
2
3
def search_for(key)
  return middle if list[middle] == key
end

The next thing on my to do list was to branch for the other two conditions: whether the key was less than or greater than the middle value:

1
2
3
4
5
6
7
8
9
10
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    # ???
  else
    # ???
  end

end

Then I filled in the branches some more of my pseudo-code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    # Cut the list we're searching in half
    # Instantiate a new BinarySearch
    # Pass the first half of the list into it
    # Call the search on the new object, with the same search key
  else
    # Cut the list we're searching in half
    # Instantiate a new BinarySearch
    # Pass the second half of the list into it
    # Call the search on the new object, with the same search key
  end

end

I filled them in with real code, one step at a time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    # Cut the list we're searching in half
    sublist = list[0..middle]

    # Instantiate a new BinarySearch
    # Pass the first half of the list into it
    search = BinarySearch.new(sublist)

    # Call the search on the new object, with the same search key
    return search.search_for(key)
  else
    # Cut the list we're searching in half
    sublist = list[middle..-1]

    # Instantiate a new BinarySearch
    # Pass the first half of the list into it
    search = BinarySearch.new(sublist)

    # Call the search on the new object, with the same search key
    return search.search_for(key)
  end

end

Seeing some duplication here, I went ahead and refactored:

1
2
3
4
5
6
7
8
9
10
11
12
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    sublist = list[0..middle]
  else
    sublist = list[middle..-1]
  end

  return BinarySearch.new(sublist).search_for(key)

end

Time to run the tests.

1
2
Expected: 5
  Actual: 2

Fail.

Why? I did some pry action and discovered that I was getting back the index of the new list’s middle element, not the original list’s middle element. To fix this, I added the current list’s middle to the recursive call. That meant undoing my refactor. I guess I refactored too soon.

1
2
3
4
5
6
7
8
9
10
11
12
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    sublist = list[0..middle]
    return BinarySearch.new(sublist).search_for(key)
  else
    sublist = list[middle..-1]
    return BinarySearch.new(sublist).search_for(key) + middle
  end

end

The tests were now passing. Good. Time to try with another example. This time looking for keys on both sides of the middle.

1
2
3
4
def test_it_finds_position_in_a_larger_list
  binary = BinarySearch.new([1, 3, 5, 8, 13, 21, 34, 55, 89, 144])
  assert_equal 1, binary.search_for(9)
end

Whoops! stack level too deep! I forgot to change value of the search on line 3. I was getting an infinite loop when I searched for a bad value. I skipped this test and wrote one for the bad search condition, instead:

1
2
3
4
5
def test_it_raises_error_for_data_not_in_list
  assert_raises RuntimeError do
    BinarySearch.new([1, 3, 6]).search_for(2)
  end
end

To make this pass, I had to validate that the search wasn’t stuck looking through the same sublist over and over:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def search_for(key)
  return middle if list[middle] == key

  if list[middle] > key
    sublist = list[0..middle]
    raise "Not Found" if sublist == list
    return BinarySearch.new(sublist).search_for(key)
  else
    sublist = list[middle..-1]
    raise "Not Found" if sublist == list
    return BinarySearch.new(sublist).search_for(key) + middle
  end

end

It passed! I went back and rewrote the other test:

1
2
3
4
5
def test_it_finds_position_in_a_larger_list
  binary = BinarySearch.new([1, 3, 5, 8, 13, 21, 34, 55, 89, 144])
  assert_equal 1, binary.search_for(3)
  assert_equal 7, binary.search_for(55)
end

Passed again! How about one more for good measure? I also wanted to check if the middle was still coming out right when I passed in a list with an even number of elements. All the others had been of an odd length.

1
2
3
4
5
def test_it_finds_correct_position_in_a_list_with_an_even_number_of_elements
  binary = BinarySearch.new([1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377])
  assert_equal 5, binary.search_for(21)
  assert_equal 6, binary.search_for(34)
end

Ok! Green!

Conclusion

Even if I didn’t know my stuff in the conference room at that moment, I’m glad that my interviewer asked me about Binary Search. It was fun to learn, and it turned out to be a little easier than I expected. I always expect algorithms to be really hard to grasp, but maybe now that I’ve done a few algorithms that use recursion, it’s not such a jump for me to understand it.

At any rate, it’s pretty cool to be able to find an element in a list with so few queries. Lately, I’ve really been enjoying pure math programming problems like this one. I’m going to try to find a few more like this to do in the near future.

Footnote

Since I had already done all of the work, I went ahead and submitted this as a new exercise for Exercism.io. So, if you use Exercism, and you enjoy doing algorithms, I’d suggest giving Binary Search a go yourself. If you get stuck, you know where to find the answer!