Tag Archives: ruby

Interesting Programming Challenge–FIFO Queue

I recently came across an interesting programming challenge, which I can summarise here.

Develop a first-in/first-out (FIFO) queue in a programming language of your choice. The following constraints apply:

  1. You must use a linked-list, and can’t use arrays, hashes or other sophisticated enumerations;
  2. The queue must be able to accept and store arbitrary objects;
  3. If the queue is empty, popping should raise an exception
  4. Each method/function can only be one line long (and using multi-statement separators such as ‘;’ is cheating);
  5. Each line can be at most 80 characters long;
  6. You can’t use an external or additional libraries – core language features only.

The queue should implement the following public interface:

  • size() –> returns an integer representing the number of elements in the queue
  • push(object o) –> pushes an arbitrary object o onto the end of the queue
  • pop() –> returns the next object from the head of the queue; raises an exception if there are no objects on the queue

While implementing a FIFO queue as a linked list is a fairly typical first year CS undergraduate problem, the additional constraints, in particular #4, make it much more interesting.

I chose to implement the solution in Ruby. Here’s the test spec for the solution:

As an added challenge, although it’s almost dictated by the problem statement, I tried to minimise (or indeed, ideally, eliminate) the use of ‘if’ statements.

Check-out my solution by clicking through.

Continue reading

Related Posts:

Migrating Rails 2.3 to Snow Leopard

Earlier this year I blogged about installing Rails 2.2 on Leopard. I recently upgraded my MacBook to Snow Leopard, so it was time to do the MySQL dance all over again.

Rather than reiterating what I did, here are the three resources that I found most useful in getting things sorted:

As with my previous experience, the most difficult & frustrating part of the exercise turned out to be getting the MySQL gem working properly. I found the commentary in the last post to be particularly helpful in getting the MySQL resolved.

Related Posts:

Installing Rails 2.2 on OSX Leopard

In my few spare moments, I like to hack Ruby on Rails. Non programmers are free to tune out at this point.

I recently tried to install and configure the recently released Rails 2.2. Among the changes therein, the MySQL driver is no longer included – you need to install the mysql gem.

The standard gem installation did not work:

$ sudo gem install mysql
Building native extensions.  This could take a while...
ERROR:  Error installing mysql:
	ERROR: Failed to build gem native extension.

/System/Library/Frameworks/Ruby.framework/Versions/1.8/usr/bin/ruby extconf.rb install mysql

After a bit of googling, it turns out you need to give a bit more information for this gem:

$ sudo bash -c "ARCHFLAGS='-arch i386' gem install mysql -- \
Building native extensions.  This could take a while...
Successfully installed mysql-2.7
1 gem installed

While this installed the gem, it still did not fix the problem:

!!! The bundled mysql.rb driver has been removed from Rails 2.2.
Please install the mysql gem and try again: gem install mysql.
rake aborted!
dlopen(/Library/Ruby/Gems/1.8/gems/mysql-2.7/lib/mysql.bundle, 9):
  Library not loaded: /usr/local/mysql/lib/mysql/libmysqlclient.15.dylib
  Referenced from: /Library/Ruby/Gems/1.8/gems/mysql-2.7/lib/mysql.bundle
  Reason: image not found - /Library/Ruby/Gems/1.8/gems/mysql-2.7/lib/mysql.bundle

Some further googling later, it transpires that you need to muck about with the dynamic link libraries:

$ sudo install_name_tool -change /usr/local/mysql/lib/mysql/libmysqlclient.15.dylib \
	/usr/local/mysql/lib/libmysqlclient.15.dylib \
$ sudo install_name_tool -change /usr/local/mysql/lib/mysql/libmysqlclient.15.dylib \
	/usr/local/mysql/libmysqlclient.15.dylib \

These last two commands look very similar, but there’s a subtle difference between them: there are two different paths to separate instances of the libmysqlclient.15.dylib file.

And low and behold:

$ irb
>> require 'mysql'
=> true

And there was great rejoicing. Note that this solution is specific to Mac OSX Leopard. It will work for Tiger, apparently, but you need to change some of the paths in the last two commands.

We will now return you to your regular programming.

Related Posts: