In a recent interview, I was asked the following question:
Write a program to determine the 10th Fibonacci number.
Without further specification, this problem is worthless. Depending on the scope and nature of the program, the solution to this problem will vary wildly. For example, will this function get called in a tight inner loop? What are the memory constraints? What are the concerns with respect to reusability? I’ll make this more concrete below.
Naive solution
def F(n):
if n == 1 or n == 0:
return 1
return F(n-1) + F(n-2)
Why this is completely wrong: What happens when you pass a fractional value to F(n)? You break. What happens if you pass a negative value? You break. You could fix this by checking if n <= 1 in the base case, but then you still have unneeded redundancy. Without explicitly defining the interface by which you generate a series, you've broken your code completely. Expect bugs, and expect huge memory waste. These results could be memoized, but consider the initial problem statement. Was there any implication that anything other than F(10) would need to be computed? No. This gives us a rather smart-ass solution.
Efficient Solution
Consider the following:
#define Fib10 89
If you can’t trust the compiler, memory constraints are tight, or performance is an issue, precomputation is clearly the solution. You KNOW F(10) without any programming whatsoever. You can compute it by hand and yield the above result. A more scrupulous reader might notice that F(10)==89 isn’t easily verifiable without writing code. A better solution might look like this.
Verifiable Efficient Solution
#define Fib10 (1+1+2+3+5+8+13+21+34+55)
It’s still sloppy, but it’s as efficient as the previous solution and easier to verify. This solution, however, has a fatal flaw: it only works for one value of N (although you could define more), and it’s not reusable at all. A compromise between efficiency and reusability might give you the following.
The Compromise Solution
Fib = [1,1] for i in range(2,100): Fib.append( Fib[i-1]+Fib[i-2] )
This has no edge cases, it’s rather easy to verify, and you can adjust the maximum required value as necessary. This requires a fixed max size, though, which means it’s sure to break at some point. At best, you’re stuck with documenting this limitation. Once again, we consider memoization, but we can remember to avoid the unnecessary recursion to keep the solution a bit more efficient.
So, then, what do you do? Create something reusable.
The Reusable Solution
The code is getting funkier, so I’ll leave this as an exercise to the reader for now. Essentially, we can encapsulate the compromise solution in a class. If a client requests a Fibonacci number greater than that which we’ve precomputed, we compute up to the given value and store the intermediate computations. This solution, however, ignores the fact that most would ignore when approaching this problem.
The Math Solution
Namely, Fibonacci numbers can be generated in constant time with Binet’s formula.
For reasonable values of N, the rounding formula provides exact values.
The Real Solution
So what, then, is the right answer? It really depends on information left out of the problem statement. In the real world, you would probably just use a math library to get the values, knowing that someone has gone through the same thought process through which you’ve just gone. If this isn’t possible, then you have to consider one of the above methods.
One might argue that this reasoning ability is what an interviewer should be looking for, but that was not the emphasis of the question. Really, there are just better questions you can ask a person to figure out if they’re worth their salt, unless, of course, you’re really just pre-screening, at which point you’re just looking for the response “89.”
