14 Fibonacci Interview Questions (SOLVED) To Brush Before Coding Interview

The Fibonacci Sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Fibonacci sequence characterized by the fact that every number after the first two is the sum of the two preceding ones:

Fibonacci(0) = 0, 
Fibonacci(1) = 1,
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)  

Fibonacci sequence, appears a lot in nature. Patterns such as spirals of shells, curve of waves, seed heads, pinecones, and branches of trees can all be described using this mathematical sequence. The fact that things as large as spirals of galaxies, and as small as DNA molecules follow the Golden Ratio rule suggests that Fibonacci sequence is one of the most fundamental characteristics of the Universe.

Recursive solution looks pretty simple (see code).

Let’s look at the diagram that will help you understand what’s going on here with the rest of our code. Function fib is called with argument 5:

Basically our fib function will continue to recursively call itself creating more and more branches of the tree until it hits the base case, from which it will start summing up each branch’s return values bottom up, until it finally sums them all up and returns an integer equal to 5.

The easiest solution that comes to mind here is iteration:

function fib(n){
  let arr = [0, 1];
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1])
  }
 return arr[n]
}

And output:

fib(4)
=> 3

Notice that two first numbers can not really be effectively generated by a for loop, because our loop will involve adding two numbers together, so instead of creating an empty array we assign our arr variable to [0, 1] that we know for a fact will always be there. After that we create a loop that starts iterating from i = 2 and adds numbers to the array until the length of the array is equal to n + 1. Finally, we return the number at n index of array.

When we take any two successive (one after the other) Fibonacci Numbers, their ratio is very close to the Golden Ratio φ which is approximately 1.618034.... In fact, the bigger the pair of Fibonacci Numbers, the closer the approximation. Let us try a few:

3/2 = 1.5
5/3 = 1.666666666...
...
233/377 = 1.618055556...

This also works when we pick two random whole numbers to begin the sequence, such as 192 and 16 (we get the sequence 192, 16, 208, 224, 432, 656, 1088, 1744, 2832, 4576, 7408, 11984, 19392, 31376, ...):

16/192 = 0.08333333...
208/16 = 13
...
11984/7408 = 1.61771058...
19392/11984 = 1.61815754...

If your language supports iterators (like in Python) you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

or using iterators:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

Consider:

function fibs(n){
  let [a, b] = [0, 1]
  while (n > 0){
    [a, b] = [b, a + b]
    n -= 1
  }
  return a
}

This solution is in linear O(n) time complexity, and constant O(1) space complexity. The number of loops it takes to calculate the nth fib number will still increase at a linear rate as n increases, but we are overriding the previous numbers in the sequence as we build it out, making the space complexity constant for any input n. It's also called Iterative Top-Down Approach.