The fibonacci sequence is a sequence of integers beginning with (typically) 0 and 1 such that each subsequent term is the sum of the previous two terms:
{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... }
A popular problem for engineering students, it is also a frequent interview question for new grads. There are sometimes concerns expressed that the problem is so common as to have lost its appeal as an interview question, but the spectrum of solutions and their implementations offers job candidates an opportunity to demonstrate their ability to think critically, beyond the problem at hand.
For stand-out candidates, twists to this question provide more complex challenges before interviews or as a follow on question to interviews, for example:
- Write an application which determines whether or not a given number is in the fibonacci sequence.
- Print out the first n terms of the fibonacci sequence in reverse order.
- For a given number m, find the nearest neighboring fibonacci number and return its distance.
A relatively rare solution involves precalculating a look-up table and then displaying the requested fibonacci number to the user. Look-up tables are relatively common in software engineering as they are fast and easy to implement, although work only when a problem space is well defined so that the trade-offs can be made.
Solution for this is forthcoming.
An uncommon but fast solution involves creating a look-up table, seeding its initial values, and populating it with the fibonacci sequence until the desired term is reached. This solution has the benefit of being quite fast. It can also incorporate elements of the previous solution.
The fibonacci sequence quickly overflows 32-bit and even 64-bit numbers, so good extended questions for this solution involve detecting overflow conditions, extending the solution set to incorporate arbitrarily large numbers, etc.
Perhaps the most common solution, it is also quite slow and introduces risks that can lead to great interview questions. This solution can be completed in very few lines of code.
Recursive functions offer their own challenge and offer opportunities to ask questions regarding how functions work, how the stack works, etc.