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 .
- The formula is derived using matrix algebra.
The fact that the computation involves 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.