Programming Challenge: Nth Fibonacci Number

I did a quick Google search for "favorite whiteboard interview problems" and came up with a few interesting possibilities. The one I've chosen here is Nth Fibonacci Number.


My last challenge was pretty near the upper limit in terms of complexity. It was effectively a four-parter:

  1. Ingest data
  2. Deserialize
  3. Validate
  4. Format output

Now, obviously a lot of working programmers are going to call all of these steps trivial, and even a lot of beginning programmers are going to see each individual step as trivial, but the fact remains that it was non-trivial in the sense that it took me two or three weeks to get off my butt and actually write the program that spat out the solution. :)

Anyway, if you thought the last challenge was a little complex, I have good news! This one is effectively a one or two part problem.

The challenge

Write a program that prints the Nth value of the Fibonacci sequence. For example...

$ nth-fibonacci 6

Note: Yeah, it's kind of weird that the sixth Fibonacci number is five. Bite me. Also note that I started counting from 1, not from 0.

There really isn't any input for this program, per se, but a quick search online should reveal various lists of numbers similar to this.

The input

That's it. Just get me the 93rd Fibonacci number (counting from 1).

The solution

Here it is! No cheating.

$ nth-fibonacci 93 | base64

For an added challenge, ask yourself if your solution was recursive or iterative. If your solution was recursive, rewrite it in an iterative form or vice versa.

For those of you who are interested in how I approached this problem, see the video here.