The Square Root of 5?

Sometimes in a job interview I’m asked to whiteboard some code (or pseudo-code). One such time I was asked to whiteboard code for a function fibonacci(n) to return the nth Fibonacci number, and then discuss its performance.

I declined, and here’s why: I think coding should be informed by knowledge and, you know, thought.

When I got home, I began gathering the knowledge.

Obviously, the function could be crafted using either iteration or recursion. But the first thing I wanted to know is whether it could instead use direct computation. On Wikipedia, I found that the answer is Yes! I also found some things that were to me very surprising:

  • The computation involves \sqrt 5.
  • The formula is derived using matrix algebra.

The fact that the computation involves \sqrt 5 means that floating-point arithmetic is required, not integer arithmetic. That, in turn means that for large n, the result will be incorrect because of rounding error. So the direct computation works only for the smaller values of n.

Then I looked up a list of Fibonacci numbers, where I noticed that:

  • fibonacci(48) does not fit in a 32-bit unsigned integer.
  • fibonacci(94) does not fit in a 64-bit unsigned integer.
  • fibonacci(187) does not fit in a 128-bit unsigned integer.

Now that means that even simple integer arithmetic can produce only the smaller Fibonacci numbers.

At this point, I’d want to get the actual requirement: What’s the maximum n that would be needed. If small, I’d implement a lookup table to immediately return the desired number. If large, I’d continue investigating — perhaps look into a “big num” library.

So, I believe I was right to decline the whiteboard exercise.

But, you might say, they just wanted to get an idea about how you think.

Well, this is how I think.

Advertisements

3 thoughts on “The Square Root of 5?

  1. Hopefully, during the interview you talked about why you declined to go the whiteboard and start writing a solution.

    I’ve had candidates just refuse without giving me the insight you just did in this post. There was no way for me to separate someone who wanted to research this further and would come up with a much better answer and those who just had no idea how to approach the question.

    I have actually had candidates tell me they would research it further and based on the results of the research it would guide their implementation. I then either give them access to the Internet or I ask them to ask me questions. At this point, the questions they ask is more important than the answer they obtain. if they ask the correct questions they will find a good solution.

    1. Yes, exactly… Some of the stupid, hypothetical, no-win scenario questions that are asked in such interviews are maddening. But, I can understand their perspective in trying to weed out incompetent or undesirable persons. Just part of playing the game.

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 )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s